设已知有两个堆栈S1和S2,请用这两个堆栈模拟出一个队列Q。 所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S):判断堆栈S是否已满,返回1或0; int IsEmpty (Stack S ):判断堆栈S是否为空,返回1或0; void Push(Stack S, ElementType item ):将元素item压入堆栈S; ElementType Pop(Stack S ):删除并返回S的栈顶元素。 实现队列的操作,即入队void AddQ(ElementType item)和出队ElementType DeleteQ()。 输入格式: 输入首先给出两个正整数N1和N2,表示堆栈S1和S2的最大容量。随后给出一系列的队列操作:A item表示将item入列(这里假设item为整型数字);D表示出队操作;T表示输入结束。 输出格式: 对输入中的每个D操作,输出相应出队的数字,或者错误信息ERROR:Empty。如果入队操作无法执行,也需要输出ERROR:Full。每个输出占1行。用c语言实现
时间: 2024-04-10 11:33:12 浏览: 145
下面是使用两个堆栈模拟队列的 C 语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef int ElementType;
typedef struct {
ElementType data[MAXSIZE];
int top;
} Stack;
Stack* createStack(int maxsize) {
Stack* s = (Stack*)malloc(sizeof(Stack));
s->top = -1;
return s;
}
int IsFull(Stack* s) {
return s->top == MAXSIZE - 1;
}
int IsEmpty(Stack* s) {
return s->top == -1;
}
void Push(Stack* s, ElementType item) {
if (IsFull(s)) {
printf("ERROR: Full\n");
return;
}
s->data[++(s->top)] = item;
}
ElementType Pop(Stack* s) {
if (IsEmpty(s)) {
printf("ERROR: Empty\n");
return -1;
}
return s->data[(s->top)--];
}
void AddQ(Stack* s1, Stack* s2, ElementType item) {
if (IsFull(s1)) {
printf("ERROR: Full\n");
return;
}
while (!IsEmpty(s1)) {
Push(s2, Pop(s1));
}
Push(s1, item);
while (!IsEmpty(s2)) {
Push(s1, Pop(s2));
}
}
ElementType DeleteQ(Stack* s1) {
if (IsEmpty(s1)) {
printf("ERROR: Empty\n");
return -1;
}
return Pop(s1);
}
int main() {
int N1, N2;
scanf("%d %d", &N1, &N2);
Stack* S1 = createStack(N1);
Stack* S2 = createStack(N2);
char op;
ElementType item;
while (scanf(" %c", &op) != EOF && op != 'T') {
if (op == 'A') {
scanf("%d", &item);
AddQ(S1, S2, item);
} else if (op == 'D') {
ElementType result = DeleteQ(S1);
if (result != -1) {
printf("%d\n", result);
}
}
}
free(S1);
free(S2);
return 0;
}
```
这段代码首先定义了一个 `Stack` 结构体,用于表示堆栈。然后通过 `createStack` 函数创建了两个堆栈 S1 和 S2。接下来,实现了堆栈的基本操作函数 `IsFull`、`IsEmpty`、`Push` 和 `Pop`。
在 `AddQ` 函数中,首先将 S1 中的元素依次弹出并压入 S2,然后将要入队的元素压入 S1,最后将 S2 中的元素依次弹出并压入 S1,实现了入队操作。
在 `DeleteQ` 函数中,直接调用 `Pop` 函数从 S1 中弹出并返回队头元素,实现了出队操作。
在主函数中,根据输入的操作符执行相应的操作。当输入为 'A' 时,调用 `AddQ` 函数进行入队操作;当输入为 'D' 时,调用 `DeleteQ` 函数进行出队操作;当输入为 'T' 时,结束输入。
注意,如果入队操作无法执行或出队操作无法执行,需要输出相应的错误信息。
阅读全文