読者です 読者をやめる 読者になる 読者になる

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

情報・Web系技術の勉強メモ・備忘録です。

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

 

 

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

 

大分類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

 
実装メモ(スタック)
 
  • コンストラクタで tail0 とすることでスタックを空にする。 このとき配列(メモリ)の中に要素は残ったままですが、以降の push 操作によって上書きされる。
|Null| <- tail = 0

データが1つ入ると,tailは1を指す. 配列のindexと対応させると, array[index] -> tail = index+1

|data0| <- tail = 1
  • isEmpty 関数は tail0 かどうかを調べスタックが空かどうかを判定します。
|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()
 
stack is empty.
In [3]:
s.push(1)
s.push(2)
s.push(3)
s.push(4)
s.pop()
 
stack is full.
Out[3]:
3
In [4]:
s.print()
 
[1, 2]
 
参考(スタック)
 

キュー構造

 

平成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 は新しい要素が追加される場所を示す。 headtail で挟まれた部分(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()
 
queue is empty
In [7]:
q.print()
 
[]
In [8]:
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.print()
 
queue is full
[1, 2, 3]
In [9]:
q.dequeue()
Out[9]:
1
In [10]:
q.print()
 
[2, 3]
 
リングバッファでの実装
 

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

このままでは、tailhead が配列の容量をすぐに超えてしまう。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 であったため配列の領域を超えてしまうので tail0 に設定します。 リングバッファを時計回りに見ると、キューにデータがある場合はポインタが headtail の順番に並ぶ。

  • キューが空のときと満杯のときを区別するために tailhead の間には常に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()
 
queue is empty
In [13]:
q.enqueue(0)
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.print()
 
[0, 1, 2, 3, None]
head: 0 tail: 4
In [14]:
q.enqueue(5)
 
queue is full
In [15]:
q.dequeue()
q.print()
 
[None, 1, 2, 3, None]
head: 1 tail: 4
In [16]:
q.enqueue(4)
q.print()
 
[None, 1, 2, 3, 4]
head: 1 tail: 0
In [17]:
q.enqueue(6)
q.print()
 
queue is full
[None, 1, 2, 3, 4]
head: 1 tail: 0
In [18]:
q.dequeue()
q.print()
 
[None, None, 2, 3, 4]
head: 2 tail: 0
 
参考(キュー)