打牢地基-隊列
- 2020 年 4 月 8 日
- 筆記
章節
- 隊列的特性 & 圖示
- 數組隊列簡介與實現
- 循環隊列簡介與實現
隊列的特性 & 圖示
隊列是一種FIFO的線性數據結構
數組隊列簡介與實現
實現一個數組隊列
Queue def enqueue(val): # 入隊列 從隊尾入隊列 def dequeue(): # 出隊列 從隊首出隊列 def get_front(): # 獲取 隊首元素 def get_size(): # 獲取隊列元素個數 def is_empty(): # 隊列是否為空
ArrayQueue – 基於動態數組實現
#!/usr/bin/env python # -*- coding: utf-8 -*- """ # @Time : 2020/2/4 下午4:58 # @Author : bofengliu@tencent.com # @Site : # @File : queue.py # @Software: PyCharm # 隊列 ， 底層同樣使用動態數組 # 缺陷: 使用動態數組實現的隊列，dequeue 時間複雜度是 O(n) """ from array.Array import Array class ArrayQueue: def __init__(self, capacity=None): if capacity is None: self.array = Array() else: self.array = Array(capacity) def enqueue(self, val): """ 隊尾入隊 :param val: :return: """ self.array.add_last(val) def dequeue(self): """ 隊首出隊 :return: """ return self.array.remove_first() def get_front(self): return self.array.get_first() def get_size(self): return self.array.get_size() def is_empty(self): return self.array.is_empty() def to_string(self): res_queue_arr = [] res_queue_arr.append('Queue: front [') for i in range(0, self.get_size()): val = self.array.get(i) if isinstance(val, int): val = str(val) res_queue_arr.append(val) if i != self.get_size() - 1: res_queue_arr.append(',') res_queue_arr.append('] tail') return "".join(res_queue_arr) if __name__ == '__main__': arrayQueue = ArrayQueue() for i in range(0, 10): arrayQueue.enqueue(i) print(arrayQueue.to_string()) arrayQueue.dequeue() print(arrayQueue.to_string()) arrayQueue.enqueue(1) print(arrayQueue.to_string()) arrayQueue.enqueue(12) print(arrayQueue.to_string())
循環隊列簡介與實現
數組隊列 dequeue 的時間複雜度是 o(n) ,因每次刪除隊首元素，後面的元素都得進行前移操作 使用循環隊列可以將dequeue的時間複雜度降至o(1)
LoopQueue – 基於python list 實現
#!/usr/bin/env python # -*- coding: utf-8 -*- """ # @Time : 2020/2/5 上午11:29 # @Author : bofengliu@tencent.com # @Site : # @File : LoopQueue.py # @Software: PyCharm # 不使用動態數組、自己從底層實現循環隊列 # 先實現查詢、後實現增、刪、改, 取余成環 """ class LoopQueue: def __init__(self, capacity=None): if capacity is None: self._data = [None] * 10 else: self._data = [None] * (capacity + 1) # 隊首索引 self._front = 0 # 隊尾索引 self._tail = 0 # 元素個數 self._size = 0 def get_capacity(self): # capacity 浪費一個空間，用來區分 隊列空 & 隊列滿 return len(self._data) - 1 def is_empty(self): return self._front == self._tail def get_size(self): return self._size def enqueue(self, val): # 判斷隊列是否滿, 取余，讓隊列索引循環起來 if (self._tail + 1) % len(self._data) == self._front: self.resize(self.get_capacity() * 2) self._data[self._tail] = val self._tail = (self._tail + 1) % len(self._data) self._size += 1 def dequeue(self): if self._tail == self._front: raise (Exception, 'cannot dequeue from an empty queue.') ret = self._data[self._front] self._data[self._front] = None self._front = (self._front + 1) % len(self._data) self._size -= 1 if self._size == self.get_capacity() / 4: self.resize(self.get_capacity() / 2) return ret def get_front(self): if self.is_empty(): raise (Exception, 'queue is empty') return self._data[self._front] def resize(self, new_capacity): new_data = [None] * (new_capacity + 1) for i in range(0, self._size): # 原始隊列隊首元素放在新隊列的隊首 new_data[i] = self._data[(i + self._front) % len(self._data)] self._data = new_data self._front = 0 self._tail = self._size def to_string(self): res_queue_arr = [] res_queue_arr.append('Queue: size = %d, capacity = %d front [' % (self._size, self.get_capacity())) index = self._front while index != self._tail: val = self._data[index] if isinstance(val, int): val = str(val) res_queue_arr.append(val) if index != self._tail - 1: res_queue_arr.append(',') index = (index + 1) % len(self._data) res_queue_arr.append('] tail') return "".join(res_queue_arr) if __name__ == '__main__': loopQueue = LoopQueue(1) print(loopQueue.to_string()) for i in range(0, 5): loopQueue.enqueue(i) print(loopQueue.to_string()) print(loopQueue.to_string()) loopQueue.dequeue() print(loopQueue.to_string()) loopQueue.dequeue() print(loopQueue.to_string())
