数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列（核心思路、解题过程、完整题解）一

用队列实现栈

题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

题目示例

示例：

输入：

["MyStack", "push", "push", "top", "pop", "empty"]

[[], [1], [2], [], [], []]

输出：

[null, null, null, 2, 2, false]

解释：

MyStack myStack = new MyStack();

myStack.push(1);

myStack.push(2);

myStack.top(); // 返回 2

myStack.pop(); // 返回 2

myStack.empty(); // 返回 False

核心思路

1.入数据时，往不为空的队列入，保持另一个队列为空。

2.出数据时，依次出队头的数据，转移到另一个队列保存。直到剩下最后一个数据，用来出数据，则实现了栈的先进后出。

用C语言来解决这道题之前，应该先把队列的结构完成了。

解题过程

定义结构体

用队列实现栈，先定义一下这个栈的结构体类型。 题目中定义的是匿名结构体，这个栈的结构体包括了两个队列的结构体。（属于嵌套定义）

typedef struct
{
    Queue q1;
    Queue q2;
} MyStack;

创建栈结构体函数

这里的创建栈结构体的函数，是指调用这个函数之后，创建一个我们栈的结构体，再将这个结构体的地址返回。 但是它在函数内部，出了这个函数就会被销毁，要解决这个问题有两种方式：一是使用全局变量，二是申请空间。为了避免全局变量带来的一些问题，我们就用申请空间的方式来实现。 要注意的一点是：对这个结构体进行初始化时，要深入到它内部的两个队列结构体中，分别对两个队列进行初始化。 最终返回我们栈结构体的地址。

MyStack* myStackCreate() 
{
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}

入栈函数

按照之前的核心思路，将数据入到为空的队列中去，如果两个都为空则入到任意一个队列。

void myStackPush(MyStack* obj, int x) 
{
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);        
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

出栈函数

实现出栈函数，需要先将有数据的一方队列转移到空的另一方队列，保留最后一个数据。那么就要先判断哪一个队列为空，使用假设法：先假设q1为空，q2不为空，且创建两个变量记录下来，类似emptyQ和nonemptyQ；然后调用函数确认q1是否为空，为空则不变，不为空则交换q1和q2。 确认哪一方的队列为空之后，就可以对nonemptyQ(不为空的队列)进行数据转移了。

int myStackPop(MyStack* obj) 
{
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }
 
    while(QueueSize(nonemptyQ) > 1)
    {
        QueuePush(emptyQ,QueueFront(nonemptyQ)); 
        QueuePop(nonemptyQ);       
    }
    int top = QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);
 
    return top;
}

取栈顶数据函数

取栈顶的数据，直接取不为空队列的最后一个数据即可。

int myStackTop(MyStack* obj)
{
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

判断栈是否为空函数

因为栈是包含两个队列的，所以要两个队列都为空，这个栈才为空。

bool myStackEmpty(MyStack* obj) 
{
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列（核心思路、解题过程、完整题解）二：https://developer.aliyun.com/article/1530538