スタックを使う

Pythonで学ぶデータ構造とアルゴリズム

Miriam Antona

Software Engineer

スタック

LIFO： 後入れ先出し
- 最後に追加されたものが、最初に取り出される

本の山の画像

スタック

LIFO： 後入れ先出し
- 最後に追加されたものが、最初に取り出される
一番上にのみ乗せられる
- スタックへプッシュする

本の山の上に新しい本が1冊追加された様子

スタック

LIFO： 後入れ先出し
- 最後に追加されたものが、最初に取り出される
一番上にのみ乗せられる
- スタックへプッシュする
一番上からのみ取り出せる
- スタックからポップする

本の山の上から1冊を取った図

スタック

LIFO： 後入れ先出し
- 最後に追加されたものが、最初に取り出される
一番上にのみ乗せられる
- スタックへプッシュする
一番上からのみ削除できる
- スタックからポップする
最後の要素のみを読むことができる
- スタックからピークする

本の山の一番上にある本の表紙を指す矢印が描かれている

スタック - 実際の用途

元に戻す（Undo）機能

要素が1つあるスタック。

スタック - 実際の用途

元に戻す（Undo）機能
- キー入力のたびにプッシュする

スタックの上部に新しい要素が追加されたスタック。

スタック - 実際の用途

元に戻す（Undo）機能
- キー入力のたびにプッシュする

スタックの上部に新しい要素が追加されたスタック。

スタック - 実際の用途

元に戻す（Undo）機能
- キー入力のたびにプッシュする

スタックの上部に新しい要素が追加されたスタック。

スタック - 実際の用途

元に戻す（Undo）機能
- キー入力のたびにプッシュする

スタックの上部に新しい要素が追加されたスタック。

スタック - 実際の用途

元に戻す（Undo）機能
- キー入力のたびにプッシュする
- 最後に挿入されたキー入力をポップする

スタックの上部から要素が削除されたスタック。

スタック - 実際の用途

記号チェッカー：( [ { } ] )
- 開き括弧をプッシュする

開いている記号のあるスタック。

スタック - 実際の用途

記号チェッカー：( [ { } ] )
- 開き括弧をプッシュする

スタックの上部に新しい開始記号が追加されたスタック。

スタック - 実際の用途

記号チェッカー：( [ { } ] )
- 開き括弧をプッシュする

スタックの上部に新しい開き括弧が追加されたスタック。

スタック - 実際の用途

記号チェッカー：( [ { } ] )
- 開き括弧をプッシュする
- 閉じ括弧を確認する

開き括弧と「check "}"」という単語があるスタック。

スタック - 実際の用途

記号チェッカー：( [ { } ] )
- 開き括弧をプッシュする
- 閉じ括弧を確認する
- 一致する開き括弧をポップする

スタックの上部から開始括弧が取り除かれた状態。

スタック - 実際の用途

関数呼び出し
- メモリブロックをプッシュする
- 実行終了後にポップする

単方向連結リストを使ったスタックの作成

リンクリストとして表現されたスタック。

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

単方向連結リストを使ったスタックの作成

ノードの各部分の名称を示した連結リストとして表現されたスタック。

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

単方向連結リストを使ったスタックの作成

「TOP」という単語がスタックの先頭を指す連結リストとして表現されたスタック。

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

スタック - push

要素のないスタックと要素のあるスタックの図。

def push(self, data):

スタック - push

要素のないスタックと、要素を持つスタックに新しいノードを挿入しようとしている様子を示す図。

def push(self, data): 
  new_node = Node(data)

  if self.top:

スタック - push

空のスタックと要素を含むスタック。新しいノードが、スタックの最上部にある要素に接続されている。

def push(self, data): 
  new_node = Node(data)
  if self.top:

    new_node.next = self.top

スタック - push

要素のないスタックと、要素があり新しいノードが挿入されたスタックの図。

def push(self, data): 
  new_node = Node(data)
  if self.top:
    new_node.next = self.top
  self.top = new_node

スタック - pop

def pop(self):

  if self.top is None:

    return None

  else:

「TOP」という単語が、最上部にあるノードを指しているスタックの図。

スタック - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top

スタックの表現で、"popped_node" という語がスタックの最上部にあるノードを指している。

スタック - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next

スタックの図。単語「popped_node」がスタックの最上部にあるノードを指し、単語「TOP」が2番目のノードを指している。

スタック - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None

スタックの表現。 "popped_node" という語がスタックから切り離されたノードを指し、"TOP" という語がスタックの最上部にあるノードを指している。

スタック - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None
    return popped_node.data

スタックの図。スタックの最上部にあるノードを指す「TOP」という語。

スタック - peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None

PythonのLifoQueue

LifoQueue：
- Pythonのqueueモジュール
- スタックと同じように動作する

import queue


my_book_stack = queue.LifoQueue(maxsize=0)

my_book_stack.put("The misunderstanding")
my_book_stack.put("Persepolis")
my_book_stack.put("1984")


print("The size is: ", my_book_stack.qsize())

The size is: 3

print(my_book_stack.get())
print(my_book_stack.get())
print(my_book_stack.get())

1984
Persepolis
The misunderstanding

print("Empty stack: ", my_book_stack.empty())

Empty stack: True

練習しましょう！

Pythonで学ぶデータ構造とアルゴリズム