用一个队列实现栈C语言
时间: 2024-02-11 14:37:03 浏览: 22
可以使用一个队列来实现一个栈,具体思路如下:
1. 定义一个队列结构体,包含一个数组和两个指针 front 和 rear,分别指向队列的头和尾。
2. 定义一个栈结构体,包含一个队列的指针和一个整数 top,表示栈顶元素的下标。
3. 入栈操作时,将元素插入队列的尾部,同时更新 top 的值。
4. 出栈操作时,将队列的 rear 指针指向的元素弹出,同时更新 top 的值。
5. 判断栈是否为空时,判断 top 的值是否为 -1。
下面是示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
// 定义队列结构体
typedef struct {
int data[MAXSIZE];
int front; // 队首指针
int rear; // 队尾指针
} Queue;
// 初始化队列
void initQueue(Queue *q) {
q->front = q->rear = -1;
}
// 判断队列是否为空
int isEmpty(Queue *q) {
return q->front == -1;
}
// 判断队列是否已满
int isFull(Queue *q) {
return (q->rear + 1) % MAXSIZE == q->front;
}
// 入队操作
void enqueue(Queue *q, int x) {
if (isFull(q)) {
printf("Queue is full.\n");
return;
}
if (isEmpty(q)) {
q->front = q->rear = 0;
} else {
q->rear = (q->rear + 1) % MAXSIZE;
}
q->data[q->rear] = x;
}
// 出队操作
int dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
return -1;
}
int x = q->data[q->front];
if (q->front == q->rear) {
q->front = q->rear = -1;
} else {
q->front = (q->front + 1) % MAXSIZE;
}
return x;
}
// 定义栈结构体
typedef struct {
Queue *q;
int top; // 栈顶指针
} Stack;
// 初始化栈
void initStack(Stack *s) {
s->q = (Queue *) malloc(sizeof(Queue));
initQueue(s->q);
s->top = -1;
}
// 判断栈是否为空
int stackIsEmpty(Stack *s) {
return s->top == -1;
}
// 入栈操作
void push(Stack *s, int x) {
enqueue(s->q, x);
s->top++;
}
// 出栈操作
int pop(Stack *s) {
if (stackIsEmpty(s)) {
printf("Stack is empty.\n");
return -1;
}
int i, x;
// 将队列中的前 top 个元素出队再入队,实现栈的弹出操作
for (i = 0; i < s->top; i++) {
x = dequeue(s->q);
enqueue(s->q, x);
}
// 弹出栈顶元素
x = dequeue(s->q);
// top 减 1
s->top--;
return x;
}
int main() {
Stack s;
initStack(&s);
push(&s, 1);
push(&s, 2);
push(&s, 3);
printf("%d\n", pop(&s)); // 3
printf("%d\n", pop(&s)); // 2
printf("%d\n", pop(&s)); // 1
printf("%d\n", pop(&s)); // Stack is empty.
return 0;
}
```