Algorithm & Data Structure - Queue(1)

Queue

Qはスタックと同様に,資料構造に不可欠な代表的な資料構造であり,線形構造の資料構造である.しかし、スタックとは逆に、FIFOの先入先出の特徴を有する.先入先出という意味はコンビニでアルバイトをしていればわかりますが、先入先出という意味は先出という意味で、アトラクションを考えるのは簡単です.アトラクション列(単線や予約は含まれていません...)先に来た人が先にアトラクションに乗って出てくる仕組みは、FIFOといってもいいでしょう.

キューの基本演算

キューはデフォルトでenqueue/dequeueを実行し、enqueueはスタックの最後にデータ要素を追加し、dequeueはスタックの一番前に削除してデータ要素を返します.

Q.enqueue(A) # A
Q.enqueue(B) # A -> B
r1 = Q.dequeue() # return A / B
Q.enqueue(C) # B -> C

上のコードのようにデータ入出力が可能です.

キューの実装

キュー抽象データ構造を実装する方法は、次の2つです.

アレイ実装

接続リスト(双方向)を用いて

を実施する.
あります.まずスタックのように、キューの演算を定義して実現します.

キュー内の演算

size():現在のキューのデータ要素数

isEmpty():現在のキューが空の

enqueue(x):キューの最後の

にデータ要素xを追加する

dequeue():

を返し、キューの一番前のデータ要素を削除します.

peek():

を返しますが、キューの一番前のデータ要素は削除されません.
演算がある.

アレイ別キュー

class ArrayQueue:
    def __init__(self):
    	self.data = []
        
    def size(self):
    	return len(self.data)
        
    def isEmpty(self):
    	return self.size() == 0
        
    def enqueue(self, item):
    	self.data.append(item)
        
    def dequeue(self):
    	return self.data.pop(0)
    
    def peek(self):
    	return self.data[0]

このように、popを使用してdequeue時に0番インデックスの値を削除し続けるため、実装は簡単です.
配列によって実現されるキューの演算の複雑さは、次のとおりです.
計算複雑度size()O(1)isEmpty()O(1)enqueue()O(1)Dequeue()O(n)peek()O(1)

双方向接続リストを使用したキューの実装

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

class DoublyLinkedList:
    def __init__(self):
    	self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.tail.next = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.nodeCount = 0
    
    def getLength(self):
    	return self.nodeCount
    
    def getAt(self, pos):
    	if pos < 1 or pos > self.nodeCount:
        	return None
        if pos > self.nodeCount // 2:
            i = self.nodeCount + 1
            curr = self.tail
            while i > pos:
            	curr = curr.prev
                i -= 1
        else:
            i = 0
            curr = self.head
            while i < pos:
            	curr = curr.next
                i += 1
        return curr
    
    def insertAfter(self, prev, newNode):
    	next = prev.next
        next.prev = newNode
        prev.next = newNode
        newNode.next = next
        newNode.prev = prev
        self.nodeCount += 1
    
    def insertAt(self, pos, newNode):
    	if pos < 1 or pos > self.nodeCount+1:
        	return False
        prev = self.getAt(pos-1)
        return self.insertAfter(prev, newNode)
    
    def popAfter(self, prev):
    	curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data
    
    def popAt(self, pos):
    	if pos < 1 or pos > self.nodeCount:
        	raise IndexError()
        prev = self.getAt(pos-1)
        return popAfter(prev)


class LinkedListQueue:
	def __init__(self):
        self.data = DoublyLinkedList()
    
    def size(self):
    	return self.data.nodeCount
    
    def isEmpty(self):
    	return self.size() == 0
    
    def enqueue(self, item):
    	node = Node(item)
        self.data.insertAt(self.size()+1, node)
    
    def dequeue(self):
    	return self.data.popAt(1)
    
    def peek(self):
    	return self.getAt(1).data

として表すことができる簡単な双方向接続リストの観点から復習したが、詳細については下一篇を参照してください.
接続リストを用いてキューを実現する演算の複雑さが同じである場合には,キュー部分をO(1)に改良することができ,popat(1)は常に固定されているので,キューを実現するためには,接続リストのpopat部分でpopAfterを用いずにprevを直接head訪問質問とすればよい.

from pythonds.basic.queue import Queue

同様に、Pythonは基本的にキューを提供しているので、直接導入して使用することができます.

整理する

今回はQしか知りませんでしたが、次はQを利用したリングQについてお話しします.可能であれば、できるだけ簡単なアルゴリズムの問題を解いてみます.