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栈二。