Queue(佇列)這種資料結構就像排隊一樣，先來的先出去(FIFO，First in First Out)，後來的後出去(LILO，Last in Last Out)。和Stack一樣，他們都不適合需要隨機取資料結構中資料的情況。

這裡一樣，給大家展示四種在做queue的方法: python list(without capacity limit), linked list, python list (with capacity limit), python module: deque.

Queue with python list (without capacity limit)

class Queue:
    # 時間複雜度:O(1)，空間複雜度:O(1)
    def __init__(self):
        self.items=[]
        
    # 時間複雜度:O(N)，空間複雜度:O(1)    
    def __str__(self):
        values=[str(x) for x in self.items]
        return ' '.join(values)
        
    # 時間複雜度:O(1)，空間複雜度:O(1)  
    def isEmpty(self):
        if self.items==[]:
            return True
        else:
            return False
      
    # 時間複雜度:O(1)，空間複雜度:O(1)  
    def enqueue(self,value):
        self.items.append(value)
        return 'The element is inserted at the end of Queue'
        
    # 時間複雜度:O(N)，空間複雜度:O(1)
    def dequeue(self):
        if self.isEmpty():
            return 'There is no element in the Queue'
        else:
            return self.items.pop(0)
            
    # 時間複雜度:O(1)，空間複雜度:O(1)    
    def peek(self):
        if self.isEmpty():
            return 'The is no element in the Queue'
        else:
            return self.items[0]
    
    # 時間複雜度:O(1)，空間複雜度:O(1)
    def delete(self):
        self.items=[]
        return 'The Queue is sucessfully deleted!'

customQueue=Queue()
customQueue.isEmpty()
>> True
customQueue.enqueue(5)
customQueue.enqueue(1)
customQueue.enqueue(3)
print(customQueue)
>> 5 1 3
print(customQueue.dequeue())
>> 5
print(customQueue)
>> 1 3
print(customQueue.peek())
>> 1
customQueue.delete()
custom.isEmpty()
>>True

Queue with python list (with capacity limit，有大小限制的queue)
有大小限制的Queue，畫圖會比較好理解:

class Queue:
    # 時間複雜度: O(1)，空間複雜度: O(N)
    def __init__(self,maxsize):
        self.items=maxsize*[None]
        self.maxsize=maxsize
        self.start=-1
        self.top=-1
        
    # 時間複雜度: O(N)，空間複雜度: O(1)
    def __str__(self):
        values=[str(i) for i in self.items]
        return ' '.join(values)
        
    # 時間複雜度: O(1)，空間複雜度: O(1)
    def isFull(self):
        #due to the dequeue, this is possible
        if self.top + 1 == self.start:
            return True
        #is there is no dequeue happened
        elif self.start==0 and self.top+1 == self.maxsize:
            return True
        else: 
            return False
            
     # 時間複雜度: O(1)，空間複雜度: O(1)
    def isEmpty(self):
        if self.top==-1:
            return True
        else:
            return False
            
    # 時間複雜度: O(1)，空間複雜度: O(1)
    def enqueue(self,value):
        if self.isFull():
            return 'The queue is full'
        else:
            if self.top+1==self.maxsize:
                self.top=0
            else:
                self.top+=1
                #for the beginning case
                if self.start==-1:
                    self.start=0
            self.items[self.top]=value
            return 'Successfully enqueue the element!'
            
    # 時間複雜度: O(1)，空間複雜度: O(1)       
    def dequeue(self):
        if self.isEmpty():
            return 'There is no element in the Queue'
        else:
            firstElement=self.items[self.start]
            start=self.start
            # queue裡只有一個元素的case
            if self.start==self.top:
                self.start=-1
                self.top=-1
                
            # 如果start pointer已經在list的最末端
            elif self.start+1==self.maxsize:
                self.start=0
            # 一般的case
            else:
                self.start+=1
            self.items[start]=None
            return firstElement
    # 時間複雜度: O(1)，空間複雜度: O(1)
    def peek(self):
        if self.isEmpty():
            return 'There is no element in the queue'
        else:
            return self.items[self.start]
        
    # 時間複雜度: O(1)，空間複雜度: O(1)
    def delete(self):
        self.items=self.maxSize*[None]
        self.top=-1
        self.start=-1

customQueue=Queue(3)
customQueue.enqueue(3)
customQueue.enqueue(5)
customQueue.enqueue(6)
print(customQueue)
>> 3 5 6
print(customQueue.isFull())
>> True
print(customQueue.dequeue())
>> 3
print(customQueue)
>> 5 6
print(customQueue.peek())
>> 5

class Node:
    def __init__(self,value=None):
        self.value=value
        self.next=None
    
    def __str__(self):
        return str(self.value)
    
class Queue:
    # 時間複雜度: O(1)，空間複雜度: O(1)
    def __init__(self):
        self.head=None
        self.tail=None
        
    # 時間複雜度: O(N)，空間複雜度: O(1)
    def __str__(self):
        result=''
        temp_node=self.head
        while temp_node:
            result+=str(temp_node.value)
            result+=' '
            temp_node=temp_node.next
        return result
    
    # 時間複雜度: O(1)，空間複雜度: O(1)
    def enqueue(self,value):
        new_node=Node(value)
        if self.head==None:
            self.head=new_node
            self.tail=new_node
        else:
            self.tail.next=new_node
            self.tail=new_node
            
     # 時間複雜度: O(1)，空間複雜度: O(1)
    def isEmpty(self):
        if self.head==None:
            return True
        else:
            return False
        
     # 時間複雜度: O(1)，空間複雜度: O(1)
    def dequeue(self):
        if self.isEmpty():
            return 'The queue is empty!'
        else:
            popped_value=self.head
            if self.head==self.tail:
                self.head = None
                self.tail = None
            else:
                self.head=self.head.next
            return popped_value
    # 時間複雜度: O(1)，空間複雜度: O(1)   
    def peek(self):
        if self.isEmpty():
            return 'The queue is empty!'
        else:
            return self.head
    
    def delete(self):
        self.head=None
        self.tail=None

custQueue=Queue()
custQueue.enqueue(1)
custQueue.enqueue(2)
custQueue.enqueue(3)
custQueue.enqueue(4)
print(custQueue)
>> 1 2 3 4 
print(custQueue.dequeue())
>> 1
print(custQueue)
>> 2 3 4
print(custQueue.peek())
>> 2
print(custQueue)
>> 2 3 4

Use python module:deque 建queue

from collections import deque

customQueue=deque(maxlen=3)
print(customQueue)
>> deque([], maxlen=3)
customQueue.append(1)
customQueue.append(2)
customQueue.append(3)
print(customQueue)
>> deque([1, 2, 3], maxlen=3)
customQueue.popleft()
>> 1
print(customQueue)
>> deque([2, 3], maxlen=3)

參考資料:
The Complete Data Structures and Algorithms Course in Python from Udemy