只用两个顺序栈S1, S2(S1、S2的大小分别为Max1、Max2)模拟一个顺序队列时,不能用到其它的辅助空间。设计用栈的运算实现队列的插入(在可能的条件下,要保证队列元素要能插入成功)、删除以及队列判空运算。并在main函数中验证如下示例。 示例: 1) S1、S2的大小分别为5;S1栈顶用于模拟队列的队尾,S2栈顶用于模拟队列的队头 2) 队列分别有5个元素1、2、3、4、5入队,再来5个元素6、7、8、9、10入队,输出当前队列中的所有元素 3) 队列出队1个元素,输出当前队列中的所有元素 4) 队列再来一个元素11入队 5) 队列出队4个元素,输出当前队列中的所有元素 6) 队列出队5个元素,再次出队一个元素
时间: 2024-02-19 18:04:03 浏览: 66
好的,我理解了你的问题。下面是使用两个栈模拟队列的代码实现,可以满足你的需求:
```c++
#include <iostream>
using namespace std;
const int Max1 = 5; // 栈1的大小
const int Max2 = 5; // 栈2的大小
class StackQueue {
private:
int S1[Max1], S2[Max2];
int top1, top2;
public:
StackQueue() {
top1 = -1;
top2 = -1;
}
bool isEmpty() {
return top1 == -1 && top2 == -1;
}
bool isFull() {
return top1 == Max1 - 1 && top2 == Max2 - 1;
}
bool enqueue(int x) {
if (isFull()) {
return false;
}
if (top1 == Max1 - 1) {
while (top2 != -1) {
int temp = S2[top2--];
S1[++top1] = temp;
}
}
S1[++top1] = x;
return true;
}
bool dequeue() {
if (isEmpty()) {
return false;
}
if (top2 == -1) {
while (top1 != -1) {
int temp = S1[top1--];
S2[++top2] = temp;
}
}
top2--;
return true;
}
void printQueue() {
if (isEmpty()) {
cout << "Queue is empty!" << endl;
return;
}
cout << "Current queue: ";
int i;
for (i = top2; i >= 0; i--) {
cout << S2[i] << " ";
}
for (i = 0; i <= top1; i++) {
cout << S1[i] << " ";
}
cout << endl;
}
};
int main() {
StackQueue sq;
int i;
for (i = 1; i <= 5; i++) {
sq.enqueue(i);
}
for (i = 6; i <= 10; i++) {
sq.enqueue(i);
}
sq.printQueue(); // 1 2 3 4 5 6 7 8 9 10
sq.dequeue();
sq.printQueue(); // 2 3 4 5 6 7 8 9 10
sq.enqueue(11);
sq.printQueue(); // 2 3 4 5 6 7 8 9 10 11
for (i = 0; i < 4; i++) {
sq.dequeue();
}
sq.printQueue(); // 6 7 8 9 10 11
for (i = 0; i < 5; i++) {
sq.dequeue();
}
sq.printQueue(); // Queue is empty!
sq.dequeue();
sq.printQueue(); // Queue is empty!
return 0;
}
```
这段代码使用两个栈 `S1` 和 `S2` 来模拟队列。其中,`S1` 栈顶用于模拟队列的队尾,`S2` 栈顶用于模拟队列的队头。插入元素时,先检查队列是否已满,如果是,则返回 `false`;如果 `S1` 栈已满,则需要将 `S1` 中的元素移到 `S2` 中,然后再将新元素插入到 `S1` 中。删除元素时,先检查队列是否为空,如果是,则返回 `false`;如果 `S2` 栈为空,则需要将 `S1` 中的元素移到 `S2` 中,然后再从 `S2` 中删除元素。队列为空时,输出 "Queue is empty!"。
阅读全文