スタックを使う

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

Miriam Antona

Software Engineer

スタック

LIFO: 先入れ後出し
- 最後に挿入した要素が最初に削除される

本の積み重ねの画像。

スタック

LIFO: 先入れ後出し
- 最後に挿入した要素が常に最初に削除される
追加は頂上のみ
- スタックにプッシュ

頂上に新しい本が追加された本の山の画像。

スタック

LIFO: 先入れ後出し
- 最後に挿入した要素が常に最初に削除される
追加は頂上のみ
- スタックにプッシュ
取り出しは頂上のみ
- スタックからポップ

積んだ本の山の一番上から本を取った画像。

スタック

LIFO: 先入れ後出し
- 最後に挿入した要素が最初に削除される
追加は頂上のみ
- スタックにプッシュ
削除は頂上のみ
- スタックからポップ
読めるのは最後の要素のみ
- スタックをピーク

本の積み重ねの一番上の表紙を指す矢印がある画像。

スタックの実例

元に戻す（Undo）機能

要素が1つのスタック。

スタックの実例

元に戻す（Undo）
- 各キー入力をpush

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

スタックの実例

元に戻す（Undo）
- 各キー入力をpush

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

スタックの実例

元に戻す（Undo）
- 各キー入力をpush

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

スタックの実例

元に戻す（Undo）
- 各キー入力をpush

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

スタックの実例

元に戻す（Undo）
- 各キー入力をpush
- 最後に挿入したキー入力をpop

スタックの頂上から要素が1つ削除された図。

スタックの実例

記号チェック: ( [ { } ] )
- 開き記号をpush

開き記号があるスタック。

スタックの実例

記号チェック: ( [ { } ] )
- 開き記号をpush

頂上に新しい開き記号が追加されたスタック。

スタックの実例

記号チェック: ( [ { } ] )
- 開き記号をpush

頂上に新しい開き記号が追加されたスタック。

スタックの実例

記号チェック: ( [ { } ] )
- 開き記号をpush
- 閉じ記号をcheck

開き記号があり、"check "}"" と書かれたスタック。

スタックの実例

記号チェック: ( [ { } ] )
- 開き記号をpush
- 閉じ記号をcheck
- 対応する開き記号をpop

頂上から開き記号が1つ削除されたスタック。

スタックの実例

関数呼び出し
- メモリブロックをpush
- 実行終了後にpop

スタック - 単方向リストでの実装

連結リストで表したスタック。

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で学ぶデータ構造とアルゴリズム