只用两个顺序栈S1, S2(S1、S2的大小分别为Max1、Max2)模拟一个顺序队列时,不能用到其它的辅助空间。设计用栈的运算实现队列的插入(在可能的条件下,要保证队列元素要能插入成功)、删除以及队列判空运算。
时间: 2023-05-26 12:03:49 浏览: 83
首先需要明确一点,栈在模拟队列时,两个栈的作用是不同的。一个栈用来存储入队的元素,另一个栈用来辅助出队操作。
具体实现如下:
1. 队列的插入操作:
将元素插入到S1栈中即可,如果S1已经满了则队列已满,无法插入。
2. 队列的删除操作:
先检查S2栈是否为空,如果不为空则直接弹出栈顶元素。如果S2为空,则将S1栈中的所有元素依次弹出并压入S2栈中,然后再弹出S2中的栈顶元素。
3. 判空操作:
队列为空当且仅当S1和S2栈都为空。
代码实现如下(以int类型为例):
```c++
#include <cstdio>
#define Max1 10
#define Max2 10
struct queue {
int S1[Max1];
int S2[Max2];
int top1, top2;
queue() {
top1 = -1;
top2 = -1;
}
};
void push(queue &q, int x) {
if (q.top1 >= Max1 - 1) {
printf("Queue is full.\n");
return;
}
q.S1[++q.top1] = x;
}
int pop(queue &q) {
if (q.top2 >= 0)
return q.S2[q.top2--];
if (q.top1 < 0) {
printf("Queue is empty.\n");
return -1;
}
while (q.top1 >= 0)
q.S2[++q.top2] = q.S1[q.top1--];
return q.S2[q.top2--];
}
bool empty(queue &q) {
return q.top1 < 0 && q.top2 < 0;
}
int main() {
queue q;
printf("%d\n", empty(q)); // 1
push(q, 1);
push(q, 2);
push(q, 3);
printf("%d\n", pop(q)); // 1
printf("%d\n", pop(q)); // 2
printf("%d\n", pop(q)); // 3
printf("%d\n", empty(q)); // 1
return 0;
}
```