一、队列的定义
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out)
入队列：进行插入操作的一端称为
队尾
出队列：进行删除操作的一端称为
队头
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
二、头文件以及结构设计
因为队列对头节点和尾节点使用多，所以我们用一个结构体封装出其头节点和尾节点的地址，会更加方便我们后续的操作：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 链式结构：表示队列
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* _pNext;
QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);三、.c文件的实现
1、初始化
void QueueInit(Queue* q)
{
assert(q);
q->_front = NULL;
q->_rear = NULL;
q->size = 0;
}2、销毁
注意这个与链表的销毁很想，不能简单的只释放Queue节点，而是要通过循环将每一块申请的空间都释放（充分体现了链表的物理结构不连续）
void QueueDestroy(Queue* q)
{
QNode* tmp = q->_front;
while (tmp!=NULL)
{
QNode* next = tmp->_pNext;
free(tmp);
tmp = next;
}
q->_front = q->_rear = NULL;
q->size = 0;
}3、插入
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* tmp = (QNode*)malloc(sizeof(QNode));
if (tmp == NULL)
{
perror("malloc fail");
return;
}
else
{
tmp->_data = data;
tmp->_pNext = NULL;
}
if (q->_rear == NULL)
{
q->_front = q->_rear = tmp;
}
else
{
q->_rear->_pNext = tmp;
q->_rear = tmp;
}
q->size++;
}4、出列
void QueuePop(Queue* q)
{
assert(q);
assert(q->_front);
assert(q->size != 0);
if (q->_front->_pNext == NULL)//只有一个节点
{
free(q->_front);
q->_front = q->_rear = NULL;
}
else
{
QNode* next = q->_front->_pNext;
free(q->_front->_pNext);
q->_front = next;
}
q->size--;
}5、访问头数据
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->_front);
return q->_front->_data;
}6、访问尾数据
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->_rear);
return q->_rear->_data;
}7、判断是否为空和获取数据个数
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
return q->size == 0;
}四、用队列实现栈
1、分析
我们知道栈是先出后进，而队列是先进先出；
为了操作简单，我们在一个队列中存储数据；当我们需要插入时，我们可以直接插入，将队列的队尾当做栈顶，而当我们要出数据时，我们可以将前n个数据移动到第二个队列中，最后一个在原队列中出（此时最后一个数据为第一个数据，符合先进先出）；
有了以上的思路，那么这道题就非常容易解决了：
2、实现
这里要注意力扣上关于这个函数
它返回的是一个栈这个与初始化不一样。不能再函数内部直接创建栈变量，而是malloc申请一块空间后返回该指针（因为局部变量出函数就自动销毁了）
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack*psk=(MyStack*)malloc(sizeof(MyStack));
QueueInit(&(psk->q1));
QueueInit(&(psk->q2));
return psk;
}
void myStackPush(MyStack* obj, int x)
{
if(!QueueEmpty(&(obj->q1)))
{
QueuePush(&(obj->q1),x);
}
else
{
QueuePush(&(obj->q2),x);
}
}
int myStackPop(MyStack* obj)
{
Queue* tmp=&(obj->q1);//假设p1为空
Queue* ntmp=&(obj->q2);//p2不为空
if(!QueueEmpty(&(obj->q1)))
{
tmp=&(obj->q2);
ntmp=&(obj->q1);//假设p1为空
}
while(QueueSize(ntmp)>1)
{
QueuePush(tmp,QueueFront(ntmp));
QueuePop(ntmp);
}
int top=QueueFront(ntmp);
QueuePop(ntmp);
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);
free(obj);
}
