假设以一维数组Sq[m]存储循环队列的元素,若要使这m个存储空间全部都得到利用,需另设一个标志tag,以标志tag为0或1来区分队头指针和队尾指针相同时队列是空还是满。编写与此结构相对应的入队列和出队列的程序示例。
时间: 2024-11-22 09:36:19 浏览: 8
在使用一维数组作为循环队列的实现时,我们通常需要维护两个索引:`front`表示队首,`rear`表示队尾。当队列为空(即 `front == rear` 或 `tag == 0`)时,可以开始插入新元素;当队列已满(即 `(rear + 1) % m == front` 或 `tag == 1`),则无法再插入,需要先删除队首元素。
以下是一个简单的Java程序示例,展示了如何实现入队 (`enqueue`) 和出队 (`dequeue`) 的操作:
```java
public class CircularQueue {
private int[] Sq; // 存储数据的一维数组
private int front, rear; // 队首和队尾
private boolean tag; // 标志队列是否满或空
public CircularQueue(int m) {
Sq = new int[m];
front = rear = -1;
tag = false;
}
// 入队函数,检查队列状态并插入元素
public void enqueue(int value) {
if (isFull()) { // 队列已满
System.out.println("Queue is full.");
return;
}
if (isEmpty()) { // 队列为空
rear = 0; // 如果队列初始为空,更新 rear
front = rear;
} else {
rear = (rear + 1) % m; // 循环队列处理,将 rear 向后移动一位
}
Sq[rear] = value;
tag = false; // 无论队列是否满,都需要重置 tag
}
// 出队函数,返回并移除队首元素
public int dequeue() {
if (isEmpty()) { // 队列为空
System.out.println("Queue is empty.");
return -1; // 返回特殊值表示队列空
}
int removedValue = Sq[front]; // 获取队首元素
if (front == rear) { // 队列只有一元素,更新队首和队尾
front = rear = -1;
} else {
front = (front + 1) % m; // 更新队首
}
tag = true; // 队列减少了一个元素,设置 tag 为 true
return removedValue;
}
// 检查队列是否为空
private boolean isEmpty() {
return front == rear && tag != 0;
}
// 检查队列是否已满
private boolean isFull() {
return (rear + 1) % m == front && tag == 1;
}
}
// 使用示例
CircularQueue queue = new CircularQueue(5);
queue.enqueue(1); // 入队
queue.enqueue(2);
queue.dequeue(); // 出队,此时 front = 1
```
阅读全文