用队列实现栈

题目

题目描述：

示例：

解题思路

题目要求使用两个队列实现栈的入栈、出栈、获取栈顶元素、检查栈是否为空栈的基本操作。
既然要用到队列，我们首先得有能够实现队列基本操作的代码，这里直接复制之前已经写好的队列代码。

typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;}QueueNode;typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size;
}Queue;
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}
// ⼊队列，队尾
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//申请新节点QueueNode* newnode =(QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//ptail newnodeif (pq->phead == NULL){//队列为空pq->phead = pq->ptail = newnode;}else{//队列不为空pq->ptail->next = newnode;pq->ptail = pq->ptail->next;//newnode}pq->size++;
}//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL && pq->ptail == NULL;
}// 出队列，队头
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//只有一个结点的情况，避免ptail变成野指针if (pq->ptail == pq->phead){free(pq->phead);pq->phead = pq->ptail = NULL;}else{//删除队头元素、QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}--pq->size;
}
//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);/*int size = 0;QueueNode* pcur = pq->phead;while (pcur){size++ ;pcur = pcur->next;}return size;*/return pq->size;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

现在有了队列的代码，继续分析如何通过队列实现栈的操作。
队列是先进先出，栈的话是先进后出。
他说要使用两个队列，我们就先创建两个队列：

这两个队列就是我们的栈，当我们入栈时，就是将数据放入队列内。
第一种情况：这里假设栈里面没有数据，我们放入哪个队列都可以。
第二种情况：这里假设栈里面有数据，我们就需要放入不为空的队列内。

如上面这种情况，我们就需要放入Q1内，这样当我们取栈顶数据时，才可以正确出栈。
综合一下就是入栈的数据放入不为空的队列内。

出栈的操作：假设我们入栈放入的是Q1

根据栈先进后出的特性，我们取栈顶取的是3，有什么方法可以取出来？
显然我们可以将Q1内的数据出队列存入到Q2，但是不是全部转移，在队列结构体里面我们定义了有效数据个数size，我们只要转移size-1个数据，剩下的就是栈顶的数据。

根据上面这个例子，我们转移2个数据，当转移完后，我们就剩下了3，而3刚好就是我们需要的数据，在出栈后我们释放栈顶及释放队列头节点空间即可。

入栈出栈了解完了，再了解一下取栈顶数据。
数据是放在队列里面的，队列是有头指针phead和尾指针ptail的，我们找到不为空的队列，直接返回队列的尾节点数据即可。

这里注意我们的队列无论在什么时候，两个队列是肯定有一个为空的。
在这些操作例，能改变队列是否为空的操作就只有入栈跟出栈，但是入栈时我们放的是不为空的队列，出栈我们在取出数据后会删除栈顶的数据，这样无论如何我们都会保持一个队列为空队列。

因为不能通过视频的方式讲解，会显得比较凌乱，可以在之上通过画图来帮助自己理解。

代码实现

这里队列的操作函数在上面已经提供了，这些代码在前面讲解队列时全部讲解过了，有不了解的可以去回顾一下哈。

创建栈的结构体

typedef struct {Queue q1;//队列1Queue q2;//队列2
} MyStack;

栈的初始化

栈是由两个队列实现的，那初始化就是初始化两个队列。

MyStack* myStackCreate() {MyStack* ps=(MyStack*)malloc(sizeof(MyStack));QueueInit(&ps->q1);QueueInit(&ps->q2);return ps;
}

入栈

void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1))//判断是否为空队列{QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}

出栈

int myStackPop(MyStack* obj) {//定义两个变量分别指向空队列和不为空队列Queue* empq=&obj->q1;Queue* noneq=&obj->q2;if(!QueueEmpty(&obj->q1))//这里判断Q1是否为空，不为空就要替换一下{empq=&obj->q2;noneq=&obj->q1;}while(QueueSize(noneq)>1)//转移数据到空队列{int pop=QueueFront(noneq);QueuePush(empq,pop);QueuePop(noneq);}//出队列int pop =QueueFront(noneq);QueuePop(noneq);return pop;
}

获取栈顶数据

int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1))//寻找不为空的队列{return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}

判断栈是否为空

就是判断两个队列是否为空队列，当有一个不满足就代表栈内部有数据。

bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

销毁栈

销毁两个队列

void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);//销毁队列1QueueDestroy(&obj->q2);//销毁队列2free(obj);obj=NULL;
}

---

感谢观看，有错请在评论区指正，谢谢。
最后赏赐小编一个三连吧各位看官老爷们。