编程实现循环队列的操作:循环队列的初始化、入队、队列长度、出队、取队头元素。
时间: 2024-10-27 18:08:44 浏览: 8
循环队列是一种特殊的线性数据结构,它在队列的两端设立了哨兵节点,使得元素可以在“满”状态下继续添加到队尾,而在“空”状态可以从队首开始读取,避免了普通队列需要频繁移动元素的问题。以下是循环队列的主要操作:
1. **初始化**:创建循环队列时,首先需要设定队列的容量n,并创建一个数组作为存储空间。队列的头和尾指针初始化为0和-1,表示第一个有效位置。
```python
class CircularQueue:
def __init__(self, capacity):
self.queue = [None] * capacity
self.front = -1
self.rear = -1
```
2. **入队(enqueue)**:如果队列为满,则增加队尾指针,然后将元素添加到数组的下一个位置;否则,直接将元素放在rear+1处,并更新rear。
```python
def enqueue(self, item):
if (self.rear + 1) % len(self.queue) == self.front: # 队满
print("Queue is full")
else:
self.rear = (self.rear + 1) % len(self.queue)
self.queue[self.rear] = item
```
3. **队列长度(queue_length)**:检查队列是否为空,如果非空则返回 rear - front + 1(因为队尾指针加1),如果队尾超过队首,则加上总容量。
```python
def queue_length(self):
if self.front == -1:
return 0
elif self.rear >= self.front:
return self.rear - self.front + 1
else:
return len(self.queue) - self.front + self.rear + 1
```
4. **出队(dequeue)**:若队列为空,则打印错误信息;否则,将队头元素移除并更新front。
```python
def dequeue(self):
if self.front == -1:
print("Queue is empty")
else:
item = self.queue[self.front]
self.queue[self.front] = None
self.front = (self.front + 1) % len(self.queue)
return item
```
5. **取队头元素(get_front)**:同出队操作,如果队列为空,返回空值或抛出异常。
```python
def get_front(self):
if self.front == -1:
raise IndexError("Queue is empty")
else:
return self.queue[self.front]
```
阅读全文