Table of Contents¶

1 大分類1 基礎理論中分類2 アルゴリズムとプログラミング

1.1 データ構造

1.1.1 スタックとキュー

1.1.1.1 スタック構造 stack structure

1.1.1.2.2 リングバッファでの実装

1.1.1.2.3 参考（キュー）

大分類1 基礎理論中分類2 アルゴリズムとプログラミング¶

データ構造¶

スタックとキュー¶

スタックとキュー

スタックとキューの特徴，基本的な操作を理解する。

用語例

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¶

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]

s = Stack(max_size=3)
s.pop()

stack is empty.

s.push(1)
s.push(2)
s.push(3)
s.push(4)
s.pop()

stack is full.

3

s.print()

[1, 2]

参考（スタック）¶

参考：

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

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]

q = Queue_simple(max_size=3)
q.dequeue()

queue is empty

q.print()

[]

q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.print()

queue is full
[1, 2, 3]

q.dequeue()

1

q.print()

[2, 3]

リングバッファでの実装¶

配列によってキューを実装すると、上図に示すように、データの追加と取り出し操作を繰り返すことによって、head と tail に挟まれたキューのデータ本体が配列の末尾に向かって（図の右側に）移動していく。

このままでは、tail と head が配列の容量をすぐに超えてしまう。tail が配列の領域を超えた時点でオーバーフローとして追加を諦めてしまっては、まだ使える配列の領域を無駄にしてしまう。しかし、それを防ぐために dequeue() が実行されたときに head を常に 0 に保つようにデータ全体を配列の先頭に（左に）向かって移動していては、その度に $O(n)$ の計算が必要になってしまう。

この問題を解決するために、配列によるキューの実装では次のように、配列をリングバッファとみなしてデータを管理できる。

引用：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)

とすると，

(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番が空く．

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

q = Queue(max_size=4)
q.dequeue()

queue is empty

q.enqueue(0)
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.print()

[0, 1, 2, 3, None]
head: 0 tail: 4

q.enqueue(5)

queue is full

q.dequeue()
q.print()

[None, 1, 2, 3, None]
head: 1 tail: 4

q.enqueue(4)
q.print()

[None, 1, 2, 3, 4]
head: 1 tail: 0

q.enqueue(6)
q.print()

queue is full
[None, 1, 2, 3, 4]
head: 1 tail: 0

q.dequeue()
q.print()

[None, None, 2, 3, 4]
head: 2 tail: 0

参考（キュー）¶

参考：

キュー | アルゴリズムとデータ構造 | Aizu Online Judge

はしくれエンジニアもどきのメモ

情報系技術・哲学・デザインなどの勉強メモ・備忘録です。

データ構造スタックとキューの実装メモ

データ構造スタックとキュー実装メモ

Table of Contents¶

大分類1 基礎理論中分類2 アルゴリズムとプログラミング¶

データ構造¶

スタックとキュー¶

スタック構造 stack structure¶

実装メモ（スタック）¶

code¶

参考（スタック）¶

キュー構造¶

実装メモ（キュー）¶

リングバッファでの実装¶

参考（キュー）¶

データ構造 スタックとキュー実装メモ

Table of Contents¶

大分類1 基礎理論 中分類2 アルゴリズムとプログラミング¶

データ構造¶

スタックとキュー¶

スタック構造 stack structure¶

実装メモ（スタック）¶

code¶

参考（スタック）¶

キュー構造¶

実装メモ（キュー）¶

リングバッファでの実装¶

参考（キュー）¶

データ構造スタックとキュー実装メモ

大分類1 基礎理論中分類2 アルゴリズムとプログラミング¶