數據結構之——Python實現循環隊列

• 2020 年 1 月 7 日
• 筆記

棧是先入後出，與之相反的是隊列，隊列是先進先出的線性結構。隊列是只允許在一端進行插入操作，而在另一端進行刪除操作的線性表。允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。

圖1 隊列的定義 隊列的存儲結構中使用的最多的是循環隊列。循環隊列包括兩個指針， front 指針指向隊頭元素， rear 指針指向隊尾元素的下一個位置。 隊列為空的判斷條件是： front == rear

隊列滿的判斷條件是： (rear+1)%maxsize == front

隊列長度的計算公式： (rear-front+maxsize)%maxsize

具體的python實現程式碼如下：

class SqQueue(object):      def __init__(self, maxsize):          self.queue = [None] * maxsize          self.maxsize = maxsize          self.front = 0          self.rear = 0        # 返回當前隊列的長度      def QueueLength(self):          return (self.rear - self.front + self.maxsize) % self.maxsize        # 如果隊列未滿，則在隊尾插入元素，時間複雜度O(1)      def EnQueue(self, data):          if (self.rear + 1) % self.maxsize == self.front:              print("The queue is full!")          else:              self.queue[self.rear] = data             # self.queue.insert(self.rear,data)              self.rear = (self.rear + 1) % self.maxsize        # 如果隊列不為空，則刪除隊頭的元素,時間複雜度O(1)      def DeQueue(self):          if self.rear == self.front:              print("The queue is empty!")          else:              data = self.queue[self.front]              self.queue[self.front] = None              self.front = (self.front + 1) % self.maxsize              return data        # 輸出隊列中的元素      def ShowQueue(self):          for i in range(self.maxsize):              print(self.queue[i],end=',')          print(' ')  # 測試程式  if __name__ == "__main__":      # 建立大小為15的循環隊列      q = SqQueue(15)      # 0~9入隊列      for i in range(10):          q.EnQueue(i)      q.ShowQueue()      # 刪除隊頭的5個元素：0~4      for i in range(5):          q.DeQueue()      q.ShowQueue()      # 從隊尾增加8個元素：0~7      for i in range(8):          q.EnQueue(i)      q.ShowQueue()

程式輸出的結果為：

0,1,2,3,4,5,6,7,8,9,None,None,None,None,None, None,None,None,None,None,5,6,7,8,9,None,None,None,None,None, 5,6,7,None,None,5,6,7,8,9,0,1,2,3,4,