运用循环队列和链队列银行排队叫号系统
时间: 2023-05-27 20:03:25 浏览: 101
银行排队叫号系统是一个典型的队列应用场景,可以使用循环队列或者链队列来实现。
1. 循环队列实现
循环队列的特点是可以利用数组首尾相连的特性来实现循环利用队列空间,同时可以通过取余运算计算队头和队尾指针的值,避免队列满时浪费空间。
下面是使用循环队列实现银行排队叫号系统的示例代码。
```python
class CircularQueue:
def __init__(self, capacity):
self.queue = [None] * capacity
self.capacity = capacity
self.head = 0
self.tail = 0
def enqueue(self, item):
if (self.tail + 1) % self.capacity == self.head:
return False # 队列满了
self.queue[self.tail] = item
self.tail = (self.tail + 1) % self.capacity
return True
def dequeue(self):
if self.tail == self.head:
return None # 队列为空
item = self.queue[self.head]
self.head = (self.head + 1) % self.capacity
return item
def is_empty(self):
return self.head == self.tail
def is_full(self):
return (self.tail + 1) % self.capacity == self.head
class BankQueue:
def __init__(self):
self.queue = CircularQueue(100)
self.current_number = 0
def get_number(self):
self.current_number += 1
return self.current_number
def enqueue(self):
number = self.get_number()
result = self.queue.enqueue(number)
if result:
print("顾客" + str(number) + "排队成功!")
else:
print("队列已满,无法排队!")
def dequeue(self):
number = self.queue.dequeue()
if number is None:
print("队列为空,无法出队!")
else:
print("当前叫号:" + str(number))
def display(self):
if self.queue.is_empty():
print("队列为空!")
else:
print("当前排队情况:", end="")
for i in range(self.queue.head, self.queue.tail):
print(str(self.queue.queue[i]) + " ", end="")
print()
```
2. 链队列实现
链队列的特点是利用链表来存储队列元素,因此可以动态地分配内存空间,避免了循环队列可能出现的空间浪费问题。
下面是使用链队列实现银行排队叫号系统的示例代码。
```python
class Node:
def __init__(self, data):
self.data = data
self.next_node = None
class LinkedQueue:
def __init__(self):
self.head = None
self.tail = None
def enqueue(self, item):
new_node = Node(item)
if self.tail is None:
self.head = new_node
else:
self.tail.next_node = new_node
self.tail = new_node
def dequeue(self):
if self.head is None:
return None # 队列为空
item = self.head.data
self.head = self.head.next_node
if self.head is None:
self.tail = None
return item
def is_empty(self):
return self.head is None
def is_full(self):
return False
class BankQueue:
def __init__(self):
self.queue = LinkedQueue()
self.current_number = 0
def get_number(self):
self.current_number += 1
return self.current_number
def enqueue(self):
number = self.get_number()
self.queue.enqueue(number)
print("顾客" + str(number) + "排队成功!")
def dequeue(self):
number = self.queue.dequeue()
if number is None:
print("队列为空,无法出队!")
else:
print("当前叫号:" + str(number))
def display(self):
if self.queue.is_empty():
print("队列为空!")
else:
print("当前排队情况:", end="")
node = self.queue.head
while node is not None:
print(str(node.data) + " ", end="")
node = node.next_node
print()
```