我们经历了那么多练习和顺序表，链表，栈的大风大浪，小小一个队列可以说简单至极了

练习，以及顺序表之类的文章都在我的主页哦，请认真学习之后再看本文

目录

1.队列的结构

2.实现

3.栈和队列的相互实现

1.队列的结构

队列其实就是一种特殊的栈（从结构上来说），他是队头出数据，队尾入数据

 所以有一种很可怕的题目就是栈和队列的相互实现

2.实现 

我们还是先学习一下队列的实现吧

由于用数组实现和栈一样，但是他不像栈，只在一头出入，所以还需要一个结构体来封装他的头指针和尾指针

#include 
#include 
#include 
#include 
typedef int type;
typedef struct QlistNode
{type data;struct QlistNode* next;
}Q;
typedef struct QNode
{Q* front;Q* tail;int size;
}QL;void QuenceInit(QL* q);//初始化
void QuencePop(QL* q);//头删
void QuencePush(QL* q, type x);//尾插
bool QEmpty(QL* q);//是否为空
type QFront(QL* q);//获取头部元素
type QBack(QL* q);//获取尾部元素
void QDestory(QL* q);//销毁
int QSize(QL* q);//获取有效元素个数
void QPirnt(QL* q);//打印队列的元素

实现起来也是没什么区别，只是他的结构内容有点多，不要搞晕

#include "quence.h"void QuenceInit(QL* q)//初始化
{assert(q);q->front = NULL;q->tail = NULL;q->size = 0;
}
void QuencePop(QL* q)//头删
{assert(q);assert(!QEmpty(q));if (q->front->next == NULL){free(q->front);q->front = q->tail = NULL;}else{Q* cur = q->front;Q* next = cur->next;free(cur);cur = next;q->front = next;}q->size--;
}
void QuencePush(QL* q,type x)//尾插
{Q* newnode = (Q*)malloc(sizeof(Q));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;
newnode->next = NULL;if (q->front == NULL && q->tail == NULL){q->front = q->tail = newnode;}else{q->tail->next = newnode;q->tail = newnode;}q->size++;
}
bool QEmpty(QL* q)//是否为空
{assert(q);return q->front == NULL &&q->tail==NULL;
}//空就是1
type QFront(QL* q)//获取头部元素
{assert(q);assert(!QEmpty(q));return q->front->data;
}
type QBack(QL* q)//获取尾部元素
{assert(q);assert(!QEmpty(q));return q->tail->data;
}
void QDestory(QL* q)//销毁
{assert(q);Q* cur = q->front;while (cur){/*Q* next = cur->next;cur = next;free(next);*/Q* del = cur;cur = cur->next;free(del);}q->front = q->tail = NULL;q->size = 0;
}
int QSize(QL* q)//获取有效元素个数
{assert(q);return q->size;
}
void QPirnt(QL* q)//打印队列的元素
{assert(q);Q* cur = q->front;while (cur){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}

3.栈和队列的相互实现

队列实现栈

队列——》栈

基于队列一侧出 一侧入的特点，要想变成栈

当push 1 2 3 4

在pop的时候就应该先pop 4  因为栈先入的后出

所以队列的push还是保留没问题

但是pop就需要把有数据的那个队列除了最后一个元素都转移到空队列里面

 由于我们使用C的方法写，所以前面要加上刚才的队列实现

typedef struct {QL q1;QL q2;
} MyStack;MyStack* myStackCreate() {
MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
QuenceInit(&(obj->q1));
QuenceInit(&(obj->q2));
return obj;}void myStackPush(MyStack* obj, int x) {//直接尾插if(!QEmpty(&obj->q1)){QuencePush(&obj->q1,x);}else{QuencePush(&obj->q2,x);}
}
int myStackPop(MyStack* obj) {
QL *empty=&obj->q1;
QL *nonempty=&obj->q2;
if(!QEmpty(&obj->q1)) //假设错误，实际q1非空
{
empty=&obj->q2;
nonempty=&obj->q1;
}while(QSize(nonempty)>1)
{QuencePush(empty,QFront(nonempty));QuencePop(nonempty);
}
int top=QFront(nonempty);
QuencePop(nonempty);
return top;
}
int myStackTop(MyStack* obj) { 
if(!QEmpty(&obj->q1))
{return QBack(&obj->q1);
}
else{return QBack(&obj->q2);
}
}bool myStackEmpty(MyStack* obj) {//两个队列都是空的
return QEmpty(&obj->q1)&&QEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {
QDestory(&obj->q1);
QDestory(&(obj->q2));
free(obj);
}

栈实现队列

栈——>队列

当我们push 1 2 3 4

最后要实现队列，所以应该先pop 1 

所以还是栈的压数据可以保留，但是pop需要变一变

 我们发现，如果还是之前的思路乱套了，1确实是没了，但是相同的办法2就删不掉了，下一个删的就是4，显然不对

新思路就是定义一个push栈和pop栈

在pop的时候先拿走pop栈的栈顶元素此时就是题目给的peek函数

如果pop是空栈，但是push不是空，就把push依次出数据到pop，然后返回pop栈的栈顶元素

此时再pop 2 3..都很好处理了

还是在前面先写上我们栈的实现

typedef struct {
ST push;
ST pop;
} MyQueue;
bool myQueueEmpty(MyQueue* obj) {return Empty(&obj->push) && Empty(&obj->pop);
}MyQueue* myQueueCreate() {
MyQueue* q=(MyQueue*)malloc(sizeof(MyQueue));
InitST(&q->push);
InitST(&q->pop);
return q;
}void myQueuePush(MyQueue* obj, int x) {assert(obj);
PushST(&obj->push,x);
}int myQueuePop(MyQueue* obj) {assert(obj);assert(!myQueueEmpty(obj));
int peek=myQueuePeek(obj);
PopST(&obj->pop);
return peek;
}int myQueuePeek(MyQueue* obj) {assert(obj);assert(!myQueueEmpty(obj));if(Empty(&obj->pop))
{while(!Empty(&obj->push)){PushST(&obj->pop,StackTop(&obj->push));PopST(&obj->push);}
}
return StackTop(&obj->pop);
}void myQueueFree(MyQueue* obj) {
DestoryST(&obj->pop);
DestoryST(&obj->push);
free(obj);
}

学会了吗~~~