实现顺序队列的各种基本运算,并在此基础上设计一个主程序完成以下功能: (1)初始化队列S。 (2)进队列操作 (3)出队列操作 (4)取队列顶元素
时间: 2024-10-11 08:17:31 浏览: 24
数据结构栈和队列
在计算机科学中,顺序队列是一种线性数据结构,它按照先进先出(First In First Out, FIFO)的原则存储元素。常见的顺序队列可以用数组或链表实现:
**1. 初始化队列S**:如果用数组实现,可以设定一个固定大小的数组,然后将所有元素置为null或者最大值表示队列为空。如用链表实现,则创建一个新的空链表。
**2. 进队列操作(enqueue或push)**:对于数组队列,找到最后一个位置并插入新元素;对于链表队列,新建一个节点并将新元素链接到队列尾部。
**3. 出队列操作(dequeue或pop)**:从队列头部移除并返回第一个元素。如果是数组队列,删除首元素并更新下一个元素的位置;链表队列则直接访问头节点并删除。
**4. 取队列顶元素(peek或front)**:查看但不删除队列的第一个元素,对于数组队列,可以直接获取第一个元素;链表队列同样访问头节点即可。
**主程序示例(Python风格)**:
```python
class Queue:
def __init__(self):
self.queue = []
# 进队列操作
def enqueue(self, item):
self.queue.append(item)
# 出队列操作
def dequeue(self):
if not self.is_empty():
return self.queue.pop(0)
else:
return None
# 取队列顶元素
def peek(self):
return self.queue[0] if not self.is_empty() else None
# 判断队列是否为空
def is_empty(self):
return len(self.queue) == 0
# 主程序
def main():
s = Queue()
# 初始化队列S
s.enqueue(None) # 队列默认初始化为非空
# 进队列操作
s.enqueue('A')
s.enqueue('B')
# 出队列操作
print(s.dequeue()) # 输出 'A'
# 取队列顶元素
print(s.peek()) # 输出 'B'
if __name__ == "__main__":
main()
```
阅读全文