1 栈与队列
1.1 栈
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
1.2 队列
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 的原则
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
1.3 差别与关系
通过上述的介绍，栈与队列仿佛毫不相干，一个先入先出，一个后入后出。
栈像一个容器来装物品，队列像排队买饭。这两个事情看起来毫不相干，那么如何实现栈与队列的相互转换呢。下面我们来看两道OJ题，来进行具体解决。
2 栈与队列的相互转换
2.1 队列模拟实现栈
我们来看题目描述
这道题给了我们六个接口，接下来我们来逐一完成。
首先先把队列的代码拷贝到代码区，方便我们使用队列中的对应接口。、
2.1.1 栈的结构体设置
首先，我们来分析一下怎样通过队列来模拟栈
我们看，我们模拟一下发现，删除操作只需要将一个队列的前n个数据迁移到另一个队列就可以，那我们不妨就假设看看两个队列能否实现栈。
typedef struct { Queue q1; Queue q2; } MyStack;
2.1.2 初始化接口
非常简单的我们初始化一下
MyStack* myStackCreate() { MyStack* st = (MyStack*)malloc(sizeof(MyStack)); QueueInit(st->q1); QueueInit(st->q2); return st
2.1.3 压栈操作
void myStackPush(MyStack* obj, int x) { Queue* emptyQueue = &obj->q1; Queue* unemptyQueue = &obj->q2; if (!QueueEmpty(emptyQueue)) { emptyQueue = &obj->q2; unemptyQueue = &obj->q1; } QueuePush(unemptyQueue, x); }
使用假设法来判断两个队列的空与非空，选择非空进行插入。
2.1.4 出栈
int myStackPop(MyStack* obj) { Queue* emptyQueue = &obj->q1; Queue* unemptyQueue = &obj->q2; if (!QueueEmpty(emptyQueue)) { emptyQueue = &obj->q2; unemptyQueue = &obj->q1; } while (QueueSize(unemptyQueue) > 1) { QueuePush(emptyQueue, unemptyQueue->front->data); QueuePop(unemptyQueue); } int ret = QueueFront(unemptyQueue); QueuePop(unemptyQueue); return ret; }
依然是通过假设法来判断是否非空，然后依次将非空队列的前n-1个元素移动到空队列，这里的移动不是将节点的移动，而是将值赋给空队列。最后取栈顶 返回值，再出栈一下非空队列，完成操作。
2.1.5 取栈顶
int myStackTop(MyStack* obj) { if (!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); } }
选择判断是否为非空进行取队列顶操作即可。
2.1.6 判断是否为空
bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); }
都为空才为空
2.1.7 销毁栈
void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); obj = NULL; }
一步一步free掉即可。
2.2 栈模拟实现队列
我将源码放在下面，原理与上述相似，请自行观看。
2.2.1 版本一
typedef struct { Stack st1; Stack st2; } MyQueue; MyQueue* myQueueCreate() { MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&pq->st1); StackInit(&pq->st2); return pq; } void myQueuePush(MyQueue* obj, int x) { if(!StackEmpty(&obj->st1)){ StackPush(&obj->st1,x); } else{ StackPush(&obj->st2,x); } } int myQueuePop(MyQueue* obj) { //判断 空与非空 Stack* empty_st = &obj->st1; Stack* nonempty_st = &obj->st2; if(!StackEmpty(&obj->st1)){ empty_st = &obj->st2; nonempty_st = &obj->st1; } //转移元素 while(StackSize(nonempty_st)>1){ StackPush(empty_st,StackTop(nonempty_st)); StackPop(nonempty_st); } int del = StackTop(nonempty_st); StackPop(nonempty_st); while(!StackEmpty(empty_st)){ StackPush(nonempty_st,StackTop(empty_st)); StackPop(empty_st); } return del; } int myQueuePeek(MyQueue* obj) { //判断 空与非空 Stack* empty_st = &obj->st1; Stack* nonempty_st = &obj->st2; if(!StackEmpty(&obj->st1)){ empty_st = &obj->st2; nonempty_st = &obj->st1; } while(StackSize(nonempty_st)>1){ StackPush(empty_st,StackTop(nonempty_st)); StackPop(nonempty_st); } int ret = StackTop(nonempty_st); while(!StackEmpty(empty_st)){ StackPush(nonempty_st,StackTop(empty_st)); StackPop(empty_st); } return ret; } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->st1) && StackEmpty(&obj->st2); } void myQueueFree(MyQueue* obj) { StackDestroy(&obj->st1); StackDestroy(&obj->st2); free(obj); }
2.2.2 优化版本二
