C语言栈与队列相互实现详解
一、本章重点
- 用两个队列实现栈
- 用两个栈实现队列
- 解题思路总结
二、队列实现栈
我们有两个队列：
入栈数据1、 2、 3
可以将数据入队列至队列一或者队列二。
如何出栈？
但出栈要先出1，怎么办？
第一步：
将队列一出队n-1个至队列二。
第二步：
pop队列一的最后一个元素。
接下来怎么入栈呢？
将元素入队至不为空的队列。
怎么判断栈空？
队列一和队列二都为空的情况下，栈就是空的。
如何取栈顶元素？
取不为空的队列尾部元素。
总的来说就是，入栈时就将数据插入不为空的队列，出栈就将不为空的队列的前n-1个数据导入至另一个队列，然后pop最后一个元素。
代码实现：
首先我们要构造一个栈。
这个栈要包含两个队列
typedef struct
{
Queue q1;
Queue q2;
} MyStack;
在此之前我们要准备好队列的一般接口：
我这里的队列是用单链表来构建的，具体接口实现可以看我之前的文章。
typedef int QTypeData;
typedef struct QueueNode
{
struct QueueNode* next;
QTypeData val;
}QN;
void QueueInit(Queue* pq)//初始化队列
size_t QueueSize(Queue* pq)//求队列元素个数
int QueueBack(Queue* pq)//取队列尾部数据
void QueuePush(Queue* pq, QTypeData x)//将x入队
void QueuePop(Queue* pq)//出队
void QueueDestroy(Queue* pq)//结束队列
我们要用队列实现栈的接口：
- 第一个接口：创建并初始化栈
接口一：MyStack* myStackCreate()
这样做行吗？
MyStack* myStackCreate()
{
MyStack ms;
QueueInit(&ms.q1);
QueueInit(&ms.q2);
return ms;
}
很显然，返回局部变量的地址是不明智的，因为在函数返回时，ms开辟的空间会重新交给操作系统，再次访问就是非法操作。
因此我们需要将ms开辟在堆区。
参考代码：
- 第二个接口：入栈
接口二：void myStackPush(MyStack* obj, int x)
入栈简单：只要将数据插入到不为空的队列即可。
入栈之前我们需要判断队列满吗？
不需要，因为我的队列是用单链表实现的，可以无限链接下去。
如果两个队列都为空，该插入到哪个队列呢？
我们可以这样做，如果队列1为空，就插入到队列2，如果不为空，就插入到队列1.
参考代码：
- 第三个接口：出栈
接口三：int myStackPop(MyStack* obj) //出栈
再次回顾一下我们是如何出栈的。
首先我们有两个队列
初始状态它们都是空的
队列一：空
队列二：空
入栈1、2、3、4
执行后
队列一：空
队列二：1、2、3、4
出队列只能先出1，如何出4呢？
把1、2、3先出给队列一
执行后
队列一：1、2、3
队列二：4
然后将4用变量记录并出队，最后返回记录4的变量。
执行后
队列一：1、2、3
队列二：空。
出队三板斧
第一步：即将不为空的队列的前n-1个元素入至为空的队列。
第二步：将剩下的1个元素用变量记录，然后将最后一个元素出队。
第三步：返回用变量记录的元素。
需要注意的是：如果栈为空，那么就返回false。
参考代码：
- 第四个接口：取栈顶元素
接口四：int myStackTop(MyStack* obj) //取栈顶元素
取栈顶元素之前我们需要保证栈不为空
如果栈为空，返回false。
取栈顶元素，即取不为空的队列的队尾元素。
参考代码：
- 第五个接口：判断栈是否为空
接口五：bool myStackEmpty(MyStack* obj) //判断栈是否为空
如果两个队列都是空的那么该栈就是空的。
这里多提一下，栈的元素个数怎么求？
栈的元素个数就是那个不为空队列的元素个数。
参考代码：
- 第六个接口：销毁栈
接口六：void myStackFree(MyStack* obj) //结束栈
参考代码：
void myStackFree(MyStack* obj)
{
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
最后需要注意的是：调用栈为空的接口时，要先声明！！
三、栈实现队列
第一次入队
将数据1出队操作
将栈1的数据全导入栈2
然后栈2进行出栈操作
再次入队5、6、7
直接将5、6、7入栈至栈1
实际我们的对头和队尾是这样的
总的来说：
用两个栈实现一个队列，就得把一个栈专门入队，另一个栈用作出队。这里实现的时候我们用栈1做入队栈，栈2做出队栈。
也就是说，只要将数据入队，直接放入栈1.
出队就直接出栈2的数据，如果栈2为空，这将栈1的数据全部导入栈2.
队列的结构体：
typedef struct
{
ST st1;
ST st2;
} MyQueue;
我们需要准备的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* data;
int top;
int capacity;
}ST;
这里我用的是动态数组实现的栈
需要提前准备栈的接口：
void STInit(ST* p) void STDestroy(ST* p) void STPush(ST* p,STDataType x) void STPop(ST* p) bool STEmpty(ST* p) int STSize(ST* p) STDataType STRear(ST* p)
- 第一个接口：创建并初始化队列
MyQueue* myQueueCreate()
同样的，需要把队列开辟在堆区，同时对栈1和栈2进行初始化。
参考代码：
MyQueue* myQueueCreate()
{
MyQueue* mq=(MyQueue*)malloc(sizeof(MyQueue));
assert(mq);
STInit(&mq->st1);
STInit(&mq->st2);
return mq;
}
- 第二个接口：入队
void myQueuePush(MyQueue* obj, int x)
我们把栈1做入队栈，栈2做出队栈。
也就是说，只要将数据入队，直接放入栈1.
出队就直接出栈2的数据，如果栈2为空，这将栈1的数据全部导入栈2.
参考代码：
void myQueuePush(MyQueue* obj, int x)
{
STPush(&obj->st1,x);
}
- 第三个接口：出队
int myQueuePop(MyQueue* obj)
先要判断队列是否为空，如果队列为空则返回false。
其次如果栈2为空，就将栈1的数据全导入栈2.
参考代码：
int myQueuePop(MyQueue* obj)
{
if(myQueueEmpty(obj))
{
return false;
}
if(STEmpty(&obj->st2))
{
int n=STSize(&obj->st1);
while(n--)
{
STPush(&obj->st2,STRear(&obj->st1));
STPop(&obj->st1);
}
}
int ret=STRear(&obj->st2);
STPop(&obj->st2);
return ret;
}
第四个接口：取队头元素
int myQueuePeek(MyQueue* obj)
取队头元素之前，要判断队列是否为空，如果为空，则返回false
队头元素即栈2的尾部元素。
但如果栈2为空呢？
那队列的队头元素就是栈1的头部元素。
参考代码：
int myQueuePeek(MyQueue* obj)
{
if(myQueueEmpty(obj))
{
return false;
}
if(STEmpty(&obj->st2))
{
return STFront(&obj->st1);
}
return STRear(&obj->st2);
}
第五个接口：判断队列是否为空
bool myQueueEmpty(MyQueue* obj)
队列为空，需要栈1和栈2都为空。
参考代码：
bool myQueueEmpty(MyQueue* obj)
{
return STEmpty(&obj->st1) && STEmpty(&obj->st2);
}
第六个接口：销毁队列
void myQueueFree(MyQueue* obj)
参考代码：
void myQueueFree(MyQueue* obj)
{
STDestroy(&obj->st1);
STDestroy(&obj->st2);
free(obj);
}
注意：当使用判断队列是否为空的接口时，注意是否在之前声明过了。
四、解题思路总结
1.用队列实现栈：
我们需要用两个队列实现栈
栈类是于尾插尾删
队列是尾插头删
第一次入栈：两个队列都为空，随便插入一个队列都可
第一次出栈：出栈要出的是尾部数据，队列只能出头部数据，这是队列不能直接实现的。
那么需要将不为空的队列前n-1个数据导入至为空的队列，再将最后一个元素pop掉。
队列一：1、2、3、4
队列二：空
那么导入后
队列一：4
队列二：1、2、3
最后pop最后一个元素
队列一：空
队列二：1、2、3、4
再次尾插：尾插至不为空的队列即可。
2.用栈实现队列
我们有两个栈要求实现队列的一般接口
栈一：空
栈二：空
第一次入队：入栈至栈一或者栈二都可，这里选择栈一。
假设入队1、2、3、4
栈一：1、2、3、4
栈二:空
出队：要先出1
将栈一全部导入栈二
栈一：空
栈二：4、3、2、1
之后入队就插入至栈一
出队就pop栈二。
