栈和队列——用队列实现栈

题目中给出，让我们应用两个队列实现栈，首先我们先来想一下，栈是先进后出，队列是先进先出。所以我们就需要应用两个队列来回导才能实现栈的特点。因为这道题是基于队列来实现的，所以在下方若有看不懂的函数名称可以去栈和队列(二)中找到。

1.MyStrack

首先我们需要在结构体中存储我们的两个队列，后续方便通过结构体来调用两个队列。

typedef struct 
{Queue q1;Queue q2;
} MyStack;

2.myStackCreate()

对其进行初始化，首先我们需要先开辟一块空间用来存储两个队列。然后我们调用QueueInit()函数来对两个队列进行初始化。

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

3.myStackPush()

对栈进行插入，首先我们需要调用QueueEmpty()函数判断两个队列哪个不为空，再调用QueuePush()函数将数据直接插入到不为空的那个队列里就可以了。

void myStackPush(MyStack* obj, int x) 
{if(!QueueEmpty(&(obj->q1))){QueuePush(&(obj->q1),x);}else{QueuePush(&(obj->q2),x);}
}

4.myStackPop()

因为我们已经知道栈的删除是删除后进的数据，队列的删除是删除先进的数据。其删除的位置不同，所以不能混为一谈。所以我们需要把非空的队列中的前size-1个数据都挪到空的队列中。首先我们就需要先判断那个队列是空的。所以，依据我们之前做过的题，我们可以使用假设法，先假设q1为空，若q1不为空，再将空的改为q2。现在我们就用empty和nonempty来代表空队列和非空队列了。然后我们应用QueuePush()函数和QueueFront()函数来将非空队列中的头数据插入到空队列中，直到非空链表中的数据个数为1时停止，取出非空队列中的数据，就是我们需要的数据。

int myStackPop(MyStack* obj) 
{Queue*empty=&(obj->q1);Queue*nonempty=&(obj->q2);if(!QueueEmpty(&(obj->q1))){empty=&(obj->q2);nonempty=&(obj->q1);}while(QueueSize(nonempty)>1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int top=QueueFront(nonempty);QueuePop(nonempty);return top;
}

5.myStackTop()

由于栈是先进后出，队列是先进先出，所以栈的Top就是队列中后进的那个数据。所以我们首先需要判断哪个队列为非空队列，再调用QueueBack()函数返回非空队列中的尾数据就可以了。

int myStackTop(MyStack* obj) 
{if(!QueueEmpty(&(obj->q1))){return QueueBack(&(obj->q1));}else{return QueueBack(&(obj->q2));}
}

6.myStackEmpty()

判断队列是否为空，需要两个队列同时为空，所以只需要调用QueueEmpty()函数，并返回两个队列进行与运算的值就可以了。

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

7.myStackFree()

由于我们刚刚将两个队列存储在了一个结构体中，所以在销毁时不能直接将结构体销毁，而是应该先销毁两个队列，再销毁结构体。

void myStackFree(MyStack* obj) 
{QueueDestory(&(obj->q1));QueueDestory(&(obj->q2));free(obj);
}

总结

整道题的基本思路与代码就讲解完毕了，下面附上本题的完整代码，如果大家感兴趣的话可以自行尝试哦~

typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//队列的初始化
void QueueInit(Queue* pq);
//队列的插入
void QueuePush(Queue* pq, QDataType x);
//队列的删除
void QueuePop(Queue* pq);
//统计队列内的数据个数
int QueueSize(Queue* pq);
//获取队列的头数据
QDataType QueueFront(Queue* pq);
//获取队列的尾数据
QDataType QueueBack(Queue* pq);
//队列的判空
bool QueueEmpty(Queue* pq);
//队列的销毁
void QueueDestory(Queue* pq);//队列的初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}
//队列的插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}
//队列的删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);//方法一：后判是否为只剩一个节点//QNode* next = pq->phead->next;//free(pq->phead);//pq->phead = next;//if (pq->phead == NULL)//{//	pq->ptail = NULL;//}//pq->size--;//方法二：先判是否为只剩一个节点if (pq->phead->next == NULL){pq->phead = pq->ptail = NULL;pq->size = 0;}else{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;pq->size--;}
}//统计队列内的数据个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}//获取队列的头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
//获取队列的尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}//队列的判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;}//队列的销毁
void QueueDestory(Queue* pq)
{assert(pq);QNode* pcur = pq->phead;while (pcur){QNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}typedef struct 
{Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() 
{MyStack*obj=(MyStack*)malloc(sizeof(MyStack));QueueInit(&(obj->q1));QueueInit(&(obj->q2));return obj;
}void myStackPush(MyStack* obj, int x) 
{if(!QueueEmpty(&(obj->q1))){QueuePush(&(obj->q1),x);}else{QueuePush(&(obj->q2),x);}
}int myStackPop(MyStack* obj) 
{Queue*empty=&(obj->q1);Queue*nonempty=&(obj->q2);if(!QueueEmpty(&(obj->q1))){empty=&(obj->q2);nonempty=&(obj->q1);}while(QueueSize(nonempty)>1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int top=QueueFront(nonempty);QueuePop(nonempty);return top;
}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) 
{QueueDestory(&(obj->q1));QueueDestory(&(obj->q2));free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/