如何实现链队列的数据结构,包括入队和出队操作?并提供一个main()函数作为示例来调用这些方法。
时间: 2024-12-08 12:22:59 浏览: 7
链队列是一种基于链表实现的先进先出(FIFO)数据结构。它由两部分组成:节点(Node)和队头指针(front)。入队(enqueue)操作通常添加元素到链表的尾部,而出队(dequeue)操作则移除并返回链表头部的元素。
以下是使用Python实现一个简单的单向链表队列的基本步骤:
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
# 入队操作 - Enqueue (add an element at the rear)
def enqueue(self, item):
new_node = Node(item)
if not self.is_empty():
self.rear.next = new_node
else:
self.front = new_node
self.rear = new_node
# 出队操作 - Dequeue (remove and return the front element)
def dequeue(self):
if self.is_empty():
return "Queue is empty"
temp = self.front
self.front = self.front.next
if self.front is None:
self.rear = None
return temp.data
# 检查队列是否为空
def is_empty(self):
return self.front is None
# 示例 main() 函数
def main():
q = Queue()
q.enqueue(1) # 入队1
q.enqueue(2) # 入队2
q.enqueue(3) # 入队3
print("队列:", [q.dequeue(), q.dequeue(), q.dequeue()]) # 出队并打印结果
if __name__ == "__main__":
main()
```
在这个例子中,`enqueue()` 方法将新元素添加到队尾,`dequeue()` 方法移除并返回队首元素。如果队列空,`dequeue()` 将返回提示信息"Queue is empty"。
阅读全文