【数据结构和算法】---栈和队列的互相实现

一、用栈实现队列

具体题目可以参考LeetCode232. 用栈实现队列
首先要想到的是，队列是一种先进先出的结构，而栈是一种先进后出的结构。依此我们可以定义两个栈结构来模拟先进先出，既然要定义两个栈，那么为了方便调用，我们可以将这两个栈结构定义在一个结构体中，如下：

typedef struct {
    ST st1;//栈1
    ST st2;//栈2
} MyQueue;

实现 MyQueue类：

• void push(int x)将元素 x推到队列的末尾；
• int pop()从队列的开头移除并返回元素；
• int peek()返回队列开头的元素；
• boolean empty()如果队列为空，返回 true；否则，返回 false。

1.1初始化队列

我们定义的结构体在主函数外部，为了让每个函数都能用到，那么我们就必须要用malloc来动态开辟空间，这样此结构会被保存在静态区，每次函数调用时便不会销毁此变量，然后再将此结构体中的栈初始化。

MyQueue* myQueueCreate() 
{
    MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));//动态开辟结构体变量
    //注意初始化栈的参数为地址
    StackInit(&queue->st1);//初始化栈1
    StackInit(&queue->st2);//初始化栈2
    return queue;
}

1.2模拟入队列

我们可以将栈1作为存数据的栈，那么每次入队列操作就是进栈操作（StackPush(&obj->st1, x);）。

void myQueuePush(MyQueue* obj, int x) 
{
    assert(obj);
    StackPush(&obj->st1, x);
}

1.3模拟出队列

1. 思路1：
   如果我们用栈1obj->st1来存放数据，在模拟出队列时我们首先要断言栈1不为空，那么当栈1不为空且我们需要出队列头元素时。此时就需要栈2obj->st2来暂存数据，即我们将栈1除栈底的全部元素都出栈并入栈到栈2obj->st2，然后再出栈1最后的元素并返回，这样就模拟了先入先出性质。还需要注意的是在返回最后一个元素前还需要再将所有数据从栈2再入到栈1。逻辑如下：

2. 思路2：
   栈1用来存数据，栈2用来出数据。 那么为什么栈2的元素可以直接出呢？当我们需要模拟出队列时，我们可以先将栈1中所以元素出栈并入栈到栈2，这样一来栈2中的top就相当于队列头元素。每次从栈2中出元素时要先判断栈2中是否有元素，若没有，就将栈1中的元素出栈并入栈到栈2中。大致逻辑如下：

与思路一相比较，思路二栈2无需重新入栈1，还可继续模拟出队列。只能说两种思路各有好处，下列代码实现使用的是思路一：

int myQueuePop(MyQueue* obj) 
{
    assert(obj);
    assert(StackSize(&obj->st1) != 0);//栈1不为空
    ST* empty = &obj->st2;//栈2为空
    ST* noempty = &obj->st1;//栈1不为空
    //将栈1除栈底的所有元素出栈并入栈到栈2
    while(StackSize(noempty) > 1)
    {
        StackPush(empty,StackTop(noempty));
        StackPop(noempty);
    }
    //找到队头
    int ret = StackTop(noempty);
    StackPop(noempty);
    //重新入栈1
    while(StackSize(empty) > 0)
    {
        StackPush(noempty,StackTop(empty));
        StackPop(empty);
    }
    return ret;
}

1.4取模拟的队列头元素

此函数实现与1.3模拟出队列方法相似，就不多介绍了，如下：

int myQueuePeek(MyQueue* obj)
{
    assert(obj);
    ST* empty = &obj->st2;
    ST* noempty = &obj->st1;
    //将栈1除栈底的所有元素出栈并入栈到栈2
    while(StackSize(noempty) > 1)
    {
        StackPush(empty,StackTop(noempty));
        StackPop(noempty);
    }
    //找到队头
    int ret = StackTop(noempty);
    StackPush(empty,ret);
    StackPop(noempty);
    //重新入栈1
    while(StackSize(empty) > 0)
    {
        StackPush(noempty,StackTop(empty));
        StackPop(empty);
    }
    return ret;
}

1.5判断队列是否为空

依据上面思路，因为栈1是用来存数据的，所以当栈1为空时就代表我们模拟的队列为空。

bool myQueueEmpty(MyQueue* obj) 
{
    assert(obj);
    return StackEmpty(&obj->st1);
}

二、用队列实现栈

具体题目可以参考LeetCode225. 用队列实现栈
与用栈实现队列相似，我们同样需要两个队列来模拟实现栈，且关键在于还原队列先入先出的性质，依此性质来实现函数。既然这样我们可以如下定义结构体：

typedef struct 
{
    Queue* q1;//队列1
    Queue* q2;//队列2
} MyStack;

我们可以看到与模拟队列不同的是，模拟栈的结构体中存放的是两个结构体指针，这与队列的实现方法有关。因为我们用的队列是用链表实现的，所以其每个节点都是组成队列的一部分，且我们应该通过指针将他们一个个都连接起来（即通过指针来寻找节点）。
至于用栈实现队列问题中的结构体我们存放的是两个关于栈的结构体，是因为我们所使用的栈使用数组来实现的，这样一来我们操作的就是栈结构体中某一个元素（即动态开辟的数组）。当然在我们也可以放两个栈结构体指针，只不过在下面初始化队列时（myQueueCreate() ）我们需要额外malloc动态开辟栈结构大小的空间，然后将指针指向该空间的地址。
实现 MyStack类：

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

2.1初始化栈

malloc()动态开辟栈结构体没什么问题，与模拟队列相似。但为什么还要给结构体中的两个队列结构体指针动态开辟空间呢？这样不就违背了我们上面探讨的问题了吗？其实不然，这里的两个结构体指针事实上指向的是存放队列头指针和尾指针的结构体，如下：

typedef struct Queue
{
	QNode* phead;//队列头指针
	QNode* ptail;//队列尾指针
	int size;//长度
}Queue;

这样一来，基本每个函数都需要用到此结构体，那么我们就必须malloc开辟来增加作用域和生命周期。 最后再初始化这两个存放头/尾指针的结构体，并返回用来模拟栈的结构体地址。

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

2.2模拟出栈

与模拟出队列不同的是，这里用来模拟出栈的两个队列都可以用来出栈和入栈，具体方法如下：
为了还原栈先入后出的性质，我们可以先找到不为空的队列（因为两个队列都有可能有数据，但不同时有），然后将有数据的队列（noempty）除队尾的一个节点全都出队列并入队列到无数据的队列（empty），这样一来就找到了尾节点（模拟的栈顶）。还需要注意的是，此时我们无需再将数据重新入到noempty。 逻辑大致如下：

int myStackPop(MyStack* obj) 
{
    //先假设队列1为空
    Queue* empty = obj->q1;
    Queue* noempty = obj->q2;
    //纠正
    if(QueueEmpty(obj->q2))
    {
        empty = obj->q2;
        noempty = obj->q1;
    }
    //noempty出，并入到empty
    while(QueueSize(noempty) > 1)
    {
        int cmp = QueueFront(noempty);
        QueuePop(noempty);
        QueuePush(empty, cmp);
    }
    //取到模拟的栈顶元素
	int ret = QueueFront(noempty);
	QueuePop(noempty);
    return ret;
}

2.3模拟入栈

依据上面的方法，我们是要将数据入到不为空的队列，简单的if语句便可完成筛选。

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

2.4取模拟的栈顶元素

同样我们需要找到不为空的那个队列，且事实上队列尾指针指向的那个节点就是模拟的栈的栈顶，我们只需返回此元素即可。

int myStackTop(MyStack* obj) 
{
    assert(obj);
    //找不为空的队列
    if(!QueueEmpty(obj->q1))
        return QueueBack(obj->q1);
    else
        return QueueBack(obj->q2);
}

2.5判读栈是否为空

当两个队列都没有数据时，那么模拟的栈就是空栈。

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