1.list实现 enqueue append() dequeue pop(0) 或 enqueue insert(0,item) dequeue pop()
MAX_SIZE = 100 class MyQueue1(object): """模拟队列""" def __init__(self): self.items = [] self.size = 0 def is_empty(self): """判断是否为空""" return self.size == 0 def size(self): """返回队列的大小""" return self.size def enqueue(self, item): """入队(加入元素)""" self.items.append(item) self.size += 1 def dequeue(self): """出队(弹出元素)""" if self.size < MAX_SIZE and self.size >= 0: self.size -= 1 return self.items.pop(0) else: print("队列已经为空") return None def getFront(self): if not self.is_empty(): return self.items[0] else: return None def getRear(self): if not self.is_empty(): return self.items[self.size-1] else: return None def __str__(self): return str(self.items) class MyQueue2(object): """模拟队列""" def __init__(self): self.items = [] self.size = 0 def is_empty(self): """判断是否为空""" return self.size == 0 def size(self): """返回队列的大小""" if self.size <= MAX_SIZE: return self.size def enqueue(self, item): """入队(加入元素)""" if self.size <= MAX_SIZE: self.items.insert(0, item) self.size += 1 def dequeue(self): """出队(弹出元素)""" if self.size > 0 and self.size <= MAX_SIZE: self.size -= 1 return self.items.pop() else: print("队列已经为空") return None def getFront(self): """返回队头元素""" if not self.is_empty(): return self.items[0] else: return None def getRear(self): if not self.is_empty(): return self.items[self.size-1] else: return None def __str__(self): return str(self.items) def test(obj): i = obj() for x in range(0,6): i.enqueue(x) print(i) i.dequeue() print(i, i.getFront(), i.getRear(), i.size) if __name__ == "__main__": test(MyQueue1) test(MyQueue2)
运行结果:
2.链队 前文已介绍
# 首尾指针实现 # 链队 首尾指针实现链队 class Node(): def __init__(self, value=None): self.value = value self.next = None class StcakQueue(): def __init__(self): self.front = Node() self.rear = Node() self.size = 0 def enqueue(self, value): node = Node(value) if self.size == 0: self.front = node self.rear = node else: self.rear.next = node self.rear = node self.size += 1 def dequeue(self): if self.size == 0: raise Exception('queue is empty') else: temp = self.front.value self.front = self.front.next self.size -= 1 return temp def is_empty(self): if self.size == 0 : return False else: return True def top(self): if self.size == 0 : raise LookupError('queue is empty') else: return self.front.value def size(self): return self.size def __str__(self): if self.size == 0: return None else: stack_list = [] temp, count = self.front, self.size while count > 0 : stack_list.append(temp.value) temp = temp.next count -= 1 return str(stack_list) if __name__ == "__main__": i = StcakQueue() for x in range(0,6): i.enqueue(x) print(i) i.dequeue() print(i, i.size)
# 尾插有头结点实现链队 # 链队 尾插法 有头结点实现链队 class Node(): #结点类 def __init__(self,elem): self.elem = elem # 数据域,用来存放数据元素 self.next = None # 指针域,指向下一个结点 def __str__(self): return str(self.elem) class Queue(): # 队列 def __init__(self): # 队列初始化 self.head = None # 构造私有头结点 def is_empty(self): return self.head == None def enqueue(self,elem): # 进队列(正常向后填元素) node = Node(elem) # 创建新结点 if self.is_empty(): # 如果为空, 新建head结点 self.head = Node self.head.next = node node = self.head else: current = self.head while current.next is not None: current = current.next current.next = node def dequeue(self): # 出队列(头出) if not self.is_empty(): current = self.head.next self.head.next = self.head.next.next return current.elem else: raise IndexError('pop from a empty stack') def size(self): current = self.head count = 0 while current.next is not None: current = current.next count += 1 return count def __repr__(self): stack_list = [] current = self.head while current.next is not None: stack_list.append(current.next.elem) current = current.next return str(stack_list) __str__ = __repr__ if __name__ == "__main__": i = Queue() for x in range(0, 6): i.enqueue(x) print(i) i.dequeue() print(i, i.size())
3.两个栈实现一个队列 O(1)
# 两个栈实现一个队列 list栈 class CQueue: def __init__(self): self.stack1 = [] self.stack2 = [] def append_tail(self, elem): self.stack1.append(elem) def delete_head(self): if not self.stack2: if self.stack1: while self.stack1: elem = self.stack1.pop() self.stack2.append(elem) else: raise Exception("Queue is empty.") elem = self.stack2.pop() return elem def unitest(): # Create an instance of class CQueue que = CQueue() print("Push 1, 2, 3 successively into CQueue.") for i in range(1, 4): que.append_tail(i) print("Pop the head of the queue:", que.delete_head()) print("Pop the head of the queue:", que.delete_head()) print("Push 4, 5, 6 successively into CQueue.") for i in range(4, 7): que.append_tail(i) # Pop the rest elements in the queue for i in range(4): print("Pop the head of the queue:", que.delete_head()) if __name__ == '__main__': unitest()