Stack

13053 ワード
python algorithm テキストリンク

スタックのプロパティ

  • を積むように資料を積む形式の資料構造です.
  • スタックに格納された資料は線形構造を有する.
  • 線形構造:資料間の関係は1:1である.
  • 非線形構造:資料間の関係は1対Nである.(ex. Tree)
  • スタックに資料を挿入したり、スタックから資料を取り出したりすることができます.
  • 最後に挿入された資料を取り出し、入力します.
    例えば、スタックに1、2、3の順に資料を挿入して取り出し、逆の順である3、2、1の順に取り出すことができる.

    • スタックの実装


  • スタックに必要なデータ構造と演算を計画で実施します.
  • データ構造:線形ストレージ用リポジトリ
  • 配列を使用できます.
  • リポジトリ自体もスタックと呼ばれています.
  • スタックでは、最後に要素を挿入する位置をtopと呼ぶ.
  • 演算
    挿入
  • :リポジトリにデータを格納します.一般的にpushと呼ばれます.
    • 削除
  • :リポジトリから資料を取り出します.取り出した資料は挿入した資料の逆順で取り出す.一般的にpopと呼ばれます.
  • スタックが空の演算であるかどうかを決定します.is Empty
  • スタックの上部アイテムの演算(peek)
    • を返します.

  • スタックの挿入削除プロセス
  • の空のスタックに要素A、B、Cを順次挿入し、1回の演算プロセス
    • を削除する.

  • スタックのpushアルゴリズム
  • append法によりリスト末尾にデータ
    • を挿入する.
    def push(item) :
    s.append(item)

  • スタック内のpopアルゴリズム
    def pop() :
    if len(s) == 0 :
        #underflow
        return
   	else :
        return s.pop(-1)
    def push(item,size) :
    global top
    top += 1 
    if top == size :
        print('overflow') #push가 너무 크거나, size가 너무 작거나 
       else :
        stack[top] = item
size = 10
stack = [0]*size
top = -1

push(10,size)
top += 1     #push (20)
stack[top] = 20
    def push(item,size) :
    global top
    if top == -1 :
        print('underflow') #push가 너무 크거나, size가 너무 작거나 
       else :
        top -=1
        return stack[top+1]
print(pop())

if top > -1 :
    top -= 1 
    print(stack[top+1])
    • class Stack:
    
    def __init__(self, size):
        self.size = size
        self.top = -1 
        self.items = [None] *size

    def is_empty(self) :
        return True if (self.top == -1 ) else False

    def is_full(self) :
        return True if (self.size == self.top+1) else False
    
    def push(self, data) :
        if self.is_full() :
            raise Exception('가득참!')
        else :
            self.top += 1 
            self.items[self.top] = data

    def pop(self) :
        if self.is_empty() :
            raise Exception('stack is empty')
        else : 
            value = self.items[self.top]
            self.items[self.top] = None 
            self.top -= 1 
            return value

    def peek(self) :
        if self.is_empty() :
            raise Exception('stack is empty')
        else : 
            value = self.items[self.top]
            return value

    
        
my_stack = Stack(5)

my_stack.push(1)
my_stack.push(2)

my_stack.pop()
my_stack.push(2)
my_stack.push(3)

print(my_stack)
    白駿1105号[pal|python]
    Vue-吸い上げ効果を実現