队列概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
队列的代码实现
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue
{QNode* phead;//链表头，方便删除头结点QNode* ptail;//链表尾，方便插入新节点int size;
}Queue;void QueueInit(Queue* pq);//初始化
void QueueDestroy(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);//判断是否为空队列#include"Queue.h"void QueueInit(Queue* pq)
{pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur) {QNode* temp = cur->next;free(cur);cur = temp;}pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* temp = (QNode*)malloc(sizeof(QNode));if (temp == NULL) {perror("malloc fail");return;}temp->next = NULL;temp->val = x;if (pq->ptail == NULL) {pq->phead = pq->ptail = temp;}else{pq->ptail->next = temp;pq->ptail = temp;}pq->size++;}
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size!=0);QNode* temp = pq->phead->next;free(pq->phead);pq->phead = temp;if (pq->phead == NULL) {pq->ptail = NULL;}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;
}队列的应用
难点在于，队列只在队尾插入元素，而在队头删除元素。所以在用队列模拟实现栈的时候，我们可以轻松用队列push功能实现栈的push，而栈的pop则要另想方法。
例如，
让q1前面的元素迁移到q2，并pop掉。当q1只剩4的时候，就可以把4删掉；而剩下的数据保存在q2中。这样就可以实现栈的pop功能。
然后每次push元素的时候就push到不为空的队列，删除元素的时候仿造上述过程。
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
void QueueInit(Queue* pq)
{pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur) {QNode* temp = cur->next;free(cur);cur = temp;}pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* temp = (QNode*)malloc(sizeof(QNode));if (temp == NULL) {perror("malloc fail");return;}temp->next = NULL;temp->val = x;if (pq->ptail == NULL) {pq->phead = pq->ptail = temp;}else{pq->ptail->next = temp;pq->ptail = temp;}pq->size++;}
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size!=0);QNode* temp = pq->phead->next;free(pq->phead);pq->phead = temp;if (pq->phead == NULL) {pq->ptail = NULL;}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;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack*pst=(MyStack*)malloc(sizeof(MyStack));QueueInit(&(pst->q1));QueueInit(&(pst->q2));return pst;
}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) {QueueDestroy(&(obj->q1));QueueDestroy(&(obj->q2));
}/*** 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);
*/