#!/usr/bin/env python # coding: utf-8 # # Table of Contents #
# # 大分類1 基礎理論 中分類2 アルゴリズムとプログラミング # ## データ構造 # ### スタックとキュー # - [Gist](https://gist.github.com/Cartman0/1ab25e1c8d5b782201847331983f9a23) # - [nbviewer](http://nbviewer.jupyter.org/gist/Cartman0/1ab25e1c8d5b782201847331983f9a23) # スタックとキュー # # スタックとキューの特徴,基本的な操作を理解する。 # # 用語例 # - FIFO # - LIFO # - プッシュ # - ポップ # # #### スタック構造 stack structure # 1次元配列に格納されたデータにおいて, # あとから入れたものを先に出す構造. # # - スタックにデータを格納」pushプッシュ # - 格納したデータを取り出す pop ポップ # # スタックの格納(push)と取り出し(pop)は,ともにリストの先頭に対して行われ,最も新しく格納されたデータが最初に取り出される.: **LIFO(Last-In First-Out)** 後入れ先出し # # ``` # 3 データを積む push # ↓ # |2| # |1| # --- # ``` # # Fig.データをpush # # ``` # 3 データを取り出す pop # ↑ # |2| # |1| # --- # ``` # # Fig.データをpop # ##### 実装メモ(スタック) # - コンストラクタで `tail` を `0` とすることでスタックを空にする。 # このとき配列(メモリ)の中に要素は残ったままですが、以降の push 操作によって上書きされる。 # # ``` # |Null| <- tail = 0 # ``` # # データが1つ入ると,`tail`は1を指す. # 配列のindexと対応させると, # `array[index] -> tail = index+1` # ``` # |data0| <- tail = 1 # ``` # # - `isEmpty` 関数は `tail` が `0` かどうかを調べスタックが空かどうかを判定します。 # # ``` # |Null| <- tail = 0 # ``` # # - `isFull` 関数はスタックが満杯かどうかを判定します。 # 例えば、容量が `MAX` で定義されている場合は、`tail >= MAX` のときにスタックが満杯の状態になる。 # # ``` # |dataMax-1| <- tail=Max # | | # |data1 | # |data0 | # ``` # # - `push` 関数では tailの場所にデータを追加し,tail を1 つ増やす. # ただし、スタックが満杯の場合はなんらかのエラー処理を行う。 # # - `pop` 関数では、`tail-1` が指す要素、つまりスタックの頂点の要素を返しつつ、`tail` の値を1つ減らすことで、頂点の要素を削除する。 # ただし、スタックが空の場合はなんらかのエラー処理を行う。 # ##### code # In[1]: class Stack: def __init__(self, max_size=100): self.tail = 0 self.array = [None] * max_size self.bufferMax = max_size def isEmpty(self): return self.tail == 0 def isFull(self): return self.tail >= self.bufferMax def push(self, data): if self.isFull(): print("stack is full.") return self.array[self.tail] = data self.tail += 1 def pop(self): if self.isEmpty(): print("stack is empty.") return data = self.array[self.tail-1] self.tail -= 1 return data def print(self): print(self.array[:self.tail]) def get_array(self): return self.array[:self.tail] # In[2]: s = Stack(max_size=3) s.pop() # In[3]: s.push(1) s.push(2) s.push(3) s.push(4) s.pop() # In[4]: s.print() # ##### 参考(スタック) # 参考: # # - http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=ALDS1_3_A # #### キュー構造 # 平成22年 基本情報技術者 # # 1次元配列で格納されたデータにおいて, # 一夫の端からデータを入れ他方の端からデータを利出す構造. # **待ち行列**ともいう. # # - キューにデータを格納:**enqueue エンキュー** # - キューからデータを取り出す:**dequeue デキュー** # # もっとも古いデータから取り出される. # **FIFO: First-In First-Out 先入れ先出し** # # ``` # ------------------- # データ1 <- データ1 | データ2 | <- データ3 # -------------------- # 取り出すdequeue 入れる enqueue # ``` # Fig, キューのイメージ # # # ##### 実装メモ(キュー) # - データを格納するための整数型 1 次元配列 : `Q` # 配列 `Q` の各要素に `enqueue` されたデータを格納する。 # 問題に応じた十分な記憶領域を確保することが必要。 # 上図では、既にいくつかの要素が格納されている。 # # - 先頭ポインタである整数型変数:`head` # キューの先頭の場所を指し示す変数。 # `dequeue` されると `head` で指されている要素が取り出される。キューの先頭の要素のインデックスが常に `0` とは限らないことに注意。 # # - 末尾ポインタである整数型変数:`tail` # キューの末尾`+1` の場所(最後の要素の隣)を指し示す変数。tail は新しい要素が追加される場所を示す。 # `head` と `tail` で挟まれた部分(tail が指す要素は含まない)が、キューの中身を表す。 # # - キューに要素 x を追加する関数 `enqueue(data)` # `Q[tail]` に `data` を格納し、`tail` を1つ増やす。 # # - キューの先頭から要素を取り出す関数 `dequeue()` # `Q[head]` の値を返し、`head` を1つ増やす。 # 流れ: # # (1). 初期 # # ``` # 0 1 2 3 4 5 # # h # t # ``` # # (2). enqueue(3) # ``` # q[tail=0] = 3 # tail + 1 = 1 # ``` # ``` # 0 1 2 3 4 5 # 3 # h # t # ``` # # (2). enqueue(7) # ``` # q[tail=1] = 7 # tail + 1 = 2 # ``` # ``` # 0 1 2 3 4 5 # 3 7 # h # t # ``` # # (3). enqueue(8) # ``` # q[tail=2] = 8 # tail + 1 = 3 # ``` # ``` # 0 1 2 3 4 5 # 3 7 8 # h # t # ``` # # (4). dequeue() # ``` # return q[head=0]:3 # head + 1 = 1 # ``` # ``` # 0 1 2 3 4 5 # 3<- 7 8 # h # t # ``` # # (5). enqueue(1) # ``` # q[tail=3] = 1 # tail + 1 = 4 # ``` # ``` # 0 1 2 3 4 5 # 7 8 1 # h # t # ``` # # (6). dequeue() # ``` # return q[head=1] = 7 # head + 1 = 2 # ``` # ``` # 0 1 2 3 4 5 # 7<---- 8 1 # h # t # ``` # # (7). dequeue() # ``` # return q[head=2] = 8 # head + 1 = 3 # ``` # ``` # 0 1 2 3 4 5 # 8<------ 1 # h # t # ``` # In[5]: class Queue_simple: ''' simple buffer ''' def __init__(self, max_size=100): self.bufferMax = max_size self.head = 0 self.tail = 0 self.index = -1 self.array = [None] * max_size def enqueue(self, data): if self.isFull(): print("queue is full") return self.array[self.tail] = data self.tail += 1 def isEmpty(self): return self.head == self.tail def isFull(self): return (self.tail + 1) > self.bufferMax def dequeue(self): if self.isEmpty(): print("queue is empty") return data = self.array[self.head] self.array[self.head] = None self.head += 1 return data def print(self): print(self.array[self.head:self.tail]) def get_array(self): return self.array[self.head:self.tail] # In[6]: q = Queue_simple(max_size=3) q.dequeue() # In[7]: q.print() # In[8]: q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) q.print() # In[9]: q.dequeue() # In[10]: q.print() # ##### リングバッファでの実装 # 配列によってキューを実装すると、 # 上図に示すように、データの追加と取り出し操作を繰り返すことによって、`head` と `tail` に挟まれたキューのデータ本体が配列の末尾に向かって(図の右側に)移動していく。 # # このままでは、`tail` と `head` が配列の容量をすぐに超えてしまう。`tail` が配列の領域を超えた時点でオーバーフローとして追加を諦めてしまっては、まだ使える配列の領域を無駄にしてしまう。 # しかし、それを防ぐために `dequeue()` が実行されたときに # `head` を常に `0` に保つようにデータ全体を配列の先頭に(左に)向かって移動していては、その度に $O(n)$ の計算が必要になってしまう。 # # この問題を解決するために、配列によるキューの実装では次のように、配列を**リングバッファ**とみなしてデータを管理できる。 # # >![](http://judge.u-aizu.ac.jp/onlinejudge/IMAGE1/Commentary/ALDS1_3_B_3.png) # > 引用:AOJ, キュー http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=ALDS1_3_B # # 上の図は既にいくつかのデータが格納されたキューにデータを出し入れしている様子を示している。 # 最初に `enqueue(1)` によって 1 を追加したときに、tail の値が1 つ増えますが、既に `tail` が 7 であったため配列の領域を超えてしまうので `tail` を `0` に設定します。 # リングバッファを時計回りに見ると、キューにデータがある場合はポインタが `head` → `tail` の順番に並ぶ。 # # - **キューが空のときと満杯のときを区別するために `tail` と `head` の間には常に1つ以上の空きを設ける** # - 格納されるデータ数が4の場合 # # バッファサイズは `MAX`: $4+\text{空き}1=5$ とする. # # (1): # ``` # 初期状態 # 0 1 2 3 4 # h # t # ``` # if `head == tail` -> Empty # # # (2): # # ``` # enqueue(0) # enqueue(1) # enqueue(2) # enqueue(3) # ``` # # とすると, # # ``` # 0 1 2 3 4 # 0 1 2 3 N # h # t # ``` # # `(tail + 1) % MAX = 5 % 5 = 0` # # if ((`head` = 0) == (`tail` + 1) % `MAX` = 0) -> Full # # (3):`dequeue()`すると,0番目 # # ``` # dequeue() # ``` # # ``` # 0 1 2 3 4 # 0 <- N 1 2 3 N # h # t # ``` # # if ((`head` = 1) != (`tail` + 1) % `MAX` = 0) -> not Full # # # (4): # # ``` # enqueue(5) # ``` # # ``` # 0 1 2 3 4 # 0 <- N 1 2 3 5 # h # t # ``` # # headとtailの間の0番が空く. # # In[11]: class Queue(Queue_simple): ''' using ling buffer ''' def __init__(self, max_size=100): Queue_simple.__init__(self, max_size=max_size+1) def isFull(self): return (not self.isEmpty()) and (self.head == ((self.tail+1) % (self.bufferMax))) def dequeue(self): if self.isEmpty(): print("queue is empty") return data = self.array[self.head] self.array[self.head] = None # update head if self.head + 1 >= self.bufferMax: self.head = 0 else: self.head += 1 return data def enqueue(self, data): if self.isFull(): print("queue is full") return self.array[self.tail] = data # update tail if self.tail + 1 >= self.bufferMax: self.tail = 0 else: self.tail += 1 def print(self): print(self.get_array()) print("head:", self.head, "tail:", self.tail) def get_array(self): return self.array # In[12]: q = Queue(max_size=4) q.dequeue() # In[13]: q.enqueue(0) q.enqueue(1) q.enqueue(2) q.enqueue(3) q.print() # In[14]: q.enqueue(5) # In[15]: q.dequeue() q.print() # In[16]: q.enqueue(4) q.print() # In[17]: q.enqueue(6) q.print() # In[18]: q.dequeue() q.print() # ##### 参考(キュー) # 参考: # # - http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B&lang=jp