【使用两个栈实现队列】

---

一、栈和队列的基本特点

栈的特点是后进先出，而队列的特点是先进先出。
使用两个栈实现队列，必须具备队列的先进先出的功能。

举个例子：

向其中一个栈中放入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中的元素,如果没有元素，先全部导入进去，然后再popif(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);
}

先释放两个栈，再释放这两个栈所在的结构体。

总结

以上就是今天要讲的内容，本文简单介绍了两个栈实现队列的方法。