用一个队列实现栈用c语言编写
时间: 2024-05-10 18:15:32 浏览: 11
以下是使用队列实现栈的 C 语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
// 定义队列结构体
typedef struct {
int data[MAX_SIZE];
int front;
int rear;
} Queue;
// 初始化队列
void initQueue(Queue *q) {
q->front = q->rear = 0;
}
// 判断队列是否为空
int isEmpty(Queue *q) {
return q->front == q->rear;
}
// 判断队列是否已满
int isFull(Queue *q) {
return (q->rear + 1) % MAX_SIZE == q->front;
}
// 入队
void enqueue(Queue *q, int value) {
if (isFull(q)) {
printf("Queue is full!\n");
return;
}
q->data[q->rear] = value;
q->rear = (q->rear + 1) % MAX_SIZE;
}
// 出队
int dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty!\n");
return -1;
}
int value = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE;
return value;
}
// 使用队列实现栈
typedef struct {
Queue q1;
Queue q2;
} Stack;
// 初始化栈
void initStack(Stack *s) {
initQueue(&s->q1);
initQueue(&s->q2);
}
// 判断栈是否为空
int isStackEmpty(Stack *s) {
return isEmpty(&s->q1) && isEmpty(&s->q2);
}
// 入栈
void push(Stack *s, int value) {
if (isFull(&s->q1)) {
printf("Stack is full!\n");
return;
}
enqueue(&s->q1, value);
}
// 出栈
int pop(Stack *s) {
if (isStackEmpty(s)) {
printf("Stack is empty!\n");
return -1;
}
int value;
if (!isEmpty(&s->q1)) {
while (!isEmpty(&s->q1)) {
value = dequeue(&s->q1);
if (!isEmpty(&s->q1)) {
enqueue(&s->q2, value);
}
}
} else {
while (!isEmpty(&s->q2)) {
value = dequeue(&s->q2);
if (!isEmpty(&s->q2)) {
enqueue(&s->q1, value);
}
}
}
return value;
}
int main() {
Stack s;
initStack(&s);
push(&s, 1);
push(&s, 2);
push(&s, 3);
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
return 0;
}
```
上述代码中,我们使用了两个队列 `q1` 和 `q2`,其中 `q1` 作为主队列,存储栈中的元素,`q2` 作为辅助队列,用于在出栈操作时暂存 `q1` 中的元素。当执行出栈操作时,我们先将 `q1` 中的元素依次出队并存储到 `q2` 中,直到 `q1` 中只剩下一个元素,此时将该元素出队并返回即可。