一、栈和队列的基本特点
栈的特点是后进先出，而队列的特点是先进先出。
使用两个栈实现队列，必须具备队列的先进先出的功能。
举个例子：
向其中一个栈中放入4个元素，那么按照队列的特点，出队时是1先出队，所以需要把栈的所有元素全部出栈转移到空栈中。
再逐一出元素。
假如出栈一次后，又需要入栈，如下图：
则需要把元素存入空栈中，出栈的时候就出右边的非空栈。
出完右边的非空栈后，假如还想出栈，应该出的是5，那么就把左边的元素导入到右边的空栈，再出栈。
题目如下：
二、基本接口函数的实现
1.栈的接口
typedef int STDataType; //采用顺序表来实现栈和队列 //采用链表形式来实现也可以,不过更加推荐顺序表，顺序表 //最大的优点就是支持随机访问 typedef struct Stack { STDataType* a; int top; int capacity; }ST; void StackInit(ST* ps); void StackDestroy(ST* ps); void StackPush(ST* ps, STDataType x); void StackPop(ST* ps);//取栈顶数据 STDataType StackTop(ST* ps); int StackSize(ST* ps); bool StackEmpty(ST* ps); //也可以用int作为类型返回值 void StackPrint(const ST *ps); void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = ps->capacity = 0; //top也可以给-1,给0的意思是，先给值，再++。---指向栈顶数据的下一个 //top给-1是先++再给值。---指向栈顶数据。 } void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity)//空间不足，增容 { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newcapacity); //当ps->a 为NULL时，realloc相当于malloc。不用分类讨论ps->a是否为空 assert(tmp != NULL); ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top] = x; ps->top++; } void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; } void StackPop(ST* ps)//取栈顶数据 { assert(ps); //assert(ps->top > 0); assert(!StackEmpty(ps));//也可以这样写 ps->top--; //但是这里有问题，top会减到小于0，所以需要断言top要>0 } //取栈顶数据 STDataType StackTop(ST* ps) { assert(ps); //这里也需要给定，top必须大于0， assert(ps->top > 0); return ps->a[ps->top - 1];//顺序表相当于数组，下标从0开始，并且top也是从0开始的，所以需要-1 } int StackSize(ST* ps)//返回栈的元素个数 { assert(ps); return ps->top; } bool StackEmpty(ST* ps)//判断栈内是否还有元素 { assert(ps); //if (ps->top == 0) //{ // return true; //} //else //{ // return false; //} return ps->top == 0; //表达式为真，返回逻辑真，为假，返回逻辑假 } void StackPrint(const ST*ps)//栈要保证后进先出。 { assert(ps); for (int i = ps->top-1; i>=0; --i) { printf("%d ",ps->a[i]); } printf("\n"); }
2.创建队列骨架
typedef struct { ST pushST; ST popST; } MyQueue; MyQueue* myQueueCreate() { MyQueue*q = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&q->pushST); StackInit(&q->popST); return q; }
这里可以细致地将两个栈分为入数据栈（pushST）和出数据栈（popST），便于操作。
3.入队操作
void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushST,x); }
4.取出队列元素
int myQueuePop(MyQueue* obj) { //应该先要判断popST中是否有元素，如果有元素，那就直接pop掉 //popST中的元素,如果没有元素，先全部导入进去，然后再pop if(StackEmpty(&obj->popST)) { while(!StackEmpty(&obj->pushST)) { StackPush(&obj->popST,StackTop(&obj->pushST)); StackPop(&obj->pushST); } } int top = StackTop(&obj->popST); StackPop(&obj->popST); return top; }
注意，取出队列元素时，先判断popST栈是否为空，如果不为空，直接在这个栈中出元素。
如果为空，先将pushST栈的元素导入到popST栈，再从popST栈出元素
5.返回队首元素
//返回队列开头的元素 int myQueuePeek(MyQueue* obj) { //如果popST还有元素，则直接在这里返回，如果没有元素，则应该先把pushST的元素全部导入PopST，再取栈顶元素 if(StackEmpty(&obj->popST)) { while(!StackEmpty(&obj->pushST)) { StackPush(&obj->popST,StackTop(&obj->pushST)); StackPop(&obj->pushST); } } return StackTop(&obj->popST); }
这里也有需要注意的点：
返回队首元素应先判断pushST栈是否为空，如果不为空直接从这个栈返回栈顶元素，如果为空，应该先从pushST栈导入数据到popST，再从popST栈中出栈顶元素。
6.判断队列是否为空
bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST); }
判断队列是否为空，等同于判断完两个栈是否为空。
7.销毁队列
void myQueueFree(MyQueue* obj) { StackDestroy(&obj->pushST); StackDestroy(&obj->popST); free(obj); }
先释放两个栈，再释放这两个栈所在的结构体。
总结
以上就是今天要讲的内容，本文简单介绍了两个栈实现队列的方法。
