用c语言编写程序完成以下要求:1,可以在Dev-C++5.4.0中运行 2,用两个顺序栈S1, S2(S1、S2的大小分别为Max1、Max2)模拟一个顺序队列时,不能用到其它的辅助空间。设计用栈的运算实现队列的插入(在可能的条件下,要保证队列元素要能插入成功)、删除以及队列判空运算
时间: 2024-02-20 18:57:13 浏览: 100
以下是用C语言实现双栈法模拟顺序队列的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define Max1 10
#define Max2 10
typedef struct {
int data[Max1];
int top;
}Stack1;
typedef struct {
int data[Max2];
int top;
}Stack2;
typedef struct {
Stack1 s1;
Stack2 s2;
int length;
}SqQueue;
void init(SqQueue *q) {
q->s1.top = -1;
q->s2.top = -1;
q->length = 0;
}
int is_empty(SqQueue *q) {
return q->length == 0;
}
int is_full(SqQueue *q) {
return q->length == Max1 + Max2;
}
int push(Stack1 *s, int x) {
if (s->top == Max1 - 1) {
printf("Queue is full\n");
return 0;
}
s->data[++s->top] = x;
return 1;
}
int pop(Stack1 *s) {
if (s->top == -1) {
printf("Queue is empty\n");
return -1;
}
return s->data[s->top--];
}
int push2(Stack2 *s, int x) {
if (s->top == Max2 - 1) {
printf("Queue is full\n");
return 0;
}
s->data[++s->top] = x;
return 1;
}
int pop2(Stack2 *s) {
if (s->top == -1) {
printf("Queue is empty\n");
return -1;
}
return s->data[s->top--];
}
int insert(SqQueue *q, int x) {
if (is_full(q)) {
printf("Queue is full\n");
return 0;
}
push(&q->s1, x);
q->length++;
return 1;
}
int delete(SqQueue *q) {
if (is_empty(q)) {
printf("Queue is empty\n");
return -1;
}
if (q->s2.top == -1) {
while (q->s1.top != -1) {
push2(&q->s2, pop(&q->s1));
}
}
int x = pop2(&q->s2);
q->length--;
return x;
}
int main() {
SqQueue q;
init(&q);
insert(&q, 1);
insert(&q, 2);
insert(&q, 3);
printf("%d\n", delete(&q));
printf("%d\n", delete(&q));
printf("%d\n", delete(&q));
printf("%d\n", delete(&q));
return 0;
}
```
在该程序中,我们使用了两个结构体Stack1和Stack2来实现两个栈,用SqQueue来表示我们模拟的顺序队列。其中,init()函数用于初始化队列,is_empty()和is_full()函数分别用于判断队列是否为空和是否已满,push()和pop()函数分别用于在栈S1中压入元素和弹出元素,push2()和pop2()函数分别用于在栈S2中压入元素和弹出元素,insert()函数用于在队列中插入元素,delete()函数用于删除队列中的元素。
阅读全文