使用c++两个队列实现栈

使用两个队列实现栈的基本思路是：

- 用队列1来存储栈中的元素，队列2作为辅助队列。
- 入栈时，将元素插入队列1的队尾。
- 出栈时，将队列1中的元素依次出队并插入队列2中，直到队列1中只剩一个元素，然后将该元素出队即可，此时队列2中的元素顺序与栈中元素的顺序一致。
- 为了保持队列2为空，每次出栈后需要交换队列1和队列2的指针。

以下是使用C语言实现的代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;   // 栈的数据
    int top;     // 栈顶指针
    int size;    // 栈的大小
} MyStack;

typedef struct {
    int *data;   // 队列的数据
    int front;   // 队头指针
    int rear;    // 队尾指针
    int size;    // 队列的大小
} MyQueue;

// 初始化队列
MyQueue *queue_init(int size) {
    MyQueue *q = (MyQueue *)malloc(sizeof(MyQueue));
    q->data = (int *)malloc(sizeof(int) * size);
    q->front = 0;
    q->rear = 0;
    q->size = size;
    return q;
}

// 入队
void queue_push(MyQueue *q, int val) {
    if ((q->rear + 1) % q->size == q->front) {
        printf("Queue is full.\n");
        return;
    }
    q->data[q->rear] = val;
    q->rear = (q->rear + 1) % q->size;
}

// 出队
int queue_pop(MyQueue *q) {
    if (q->front == q->rear) {
        printf("Queue is empty.\n");
        return -1;
    }
    int val = q->data[q->front];
    q->front = (q->front + 1) % q->size;
    return val;
}

// 获取队头元素
int queue_peek(MyQueue *q) {
    if (q->front == q->rear) {
        printf("Queue is empty.\n");
        return -1;
    }
    return q->data[q->front];
}

// 判断队列是否为空
int queue_is_empty(MyQueue *q) {
    return q->front == q->rear;
}

// 初始化栈
MyStack *myStackCreate(int size) {
    MyStack *s = (MyStack *)malloc(sizeof(MyStack));
    s->data = (int *)malloc(sizeof(int) * size);
    s->top = -1;
    s->size = size;
    return s;
}

// 入栈
void myStackPush(MyStack *obj, int x) {
    if (obj->top == obj->size - 1) {
        printf("Stack is full.\n");
        return;
    }
    obj->data[++obj->top] = x;
}

// 出栈
int myStackPop(MyStack *obj) {
    if (obj->top == -1) {
        printf("Stack is empty.\n");
        return -1;
    }
    MyQueue *q1 = queue_init(obj->size);
    MyQueue *q2 = queue_init(obj->size);
    while (obj->top > 0) {  // 将栈中元素依次出队并插入队列2中
        queue_push(q2, obj->data[obj->top--]);
    }
    int val = obj->data[obj->top--];  // 将队列1中的最后一个元素出队
    while (!queue_is_empty(q2)) {     // 将队列2中的元素依次出队并插入队列1中
        queue_push(q1, queue_pop(q2));
    }
    // 交换队列1和队列2的指针，使得队列2为空
    MyQueue *temp = q1;
    q1 = q2;
    q2 = temp;
    free(q1);
    free(q2);
    return val;
}

// 获取栈顶元素
int myStackTop(MyStack *obj) {
    if (obj->top == -1) {
        printf("Stack is empty.\n");
        return -1;
    }
    return obj->data[obj->top];
}

// 判断栈是否为空
int myStackEmpty(MyStack *obj) {
    return obj->top == -1;
}

// 释放栈
void myStackFree(MyStack *obj) {
    free(obj->data);
    free(obj);
}

int main() {
    MyStack *stack = myStackCreate(5);
    myStackPush(stack, 1);
    myStackPush(stack, 2);
    myStackPush(stack, 3);
    printf("%d\n", myStackPop(stack));  // 输出3
    myStackPush(stack, 4);
    printf("%d\n", myStackPop(stack));  // 输出4
    printf("%d\n", myStackTop(stack));  // 输出2
    printf("%d\n", myStackPop(stack));  // 输出2
    printf("%d\n", myStackPop(stack));  // 输出1
    printf("%d\n", myStackPop(stack));  // 输出Stack is empty.
    myStackFree(stack);
    return 0;
}

运行结果为：

3
4
2
2
1
Stack is empty.