栈和队列简单应用
通篇使用C语言实现
本文会直接使用写好的栈和队列，而且与上文为姐妹篇，好多内容是基于上文展开的。

不是重要目录

• 前言
• 用栈实现队列
• • 使用C语言简单实现
• 用队列实现栈
• • 使用C语言简单实现
• 循环队列
• 总结

前言

通过几道例题可以帮助熟悉栈和队列的性质与使用

栈是将数据由栈顶放入，但也只能由栈顶出数据只能通过栈顶操作。
队列由队头和队尾一起操作，是由对尾入数据，队头出数据。

用栈实现队列

栈只能由栈顶出入数据，为了实现由队尾入数据队头出数据的队列，可以借助两个栈来回导数据，一个用来插入，一个用来删除。
数据入队列即将数据放入插入栈。
数据出队列即将插入栈的数据逐一放入删除栈，直到遇到需要删除的数据在插入栈删除即可。

push主要插入时使用，pop删除时使用
比如将队头的一删除后，2就变成了队头，再去看图中不同栈的功能。

说白了也是构造自己的函数，因为是C语言实现，没有STL库，需要借助栈和队列的一些内容。

使用C语言简单实现

• 先把栈拿过来

//栈typedef int STDataType;typedef struct Stack{    STDataType* a;    int top;     //栈顶的位置    int capacity;//容量}ST;//队列结构typedef struct {    ST* push;    ST* pop;} MyQueue;void StackInit(ST* ps)//栈的初始化{    assert(ps);    ps->a = NULL;    ps->top = 0;    ps->capacity = 0;}void StackDestory(ST* ps)//栈的销毁{    assert(ps);    free(ps->a);    ps->a = NULL;    ps->top = ps->capacity = 0;}void StackPush(ST* ps, STDataType x)//插入数据{    assert(ps);    if (ps->top == ps->capacity)    { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType)); if (ps->a == NULL) {     printf("realloc fail\n");     exit(-1); } ps->capacity = newCapacity;    }    ps->a[ps->top] = x;    ps->top++;}void StackPop(ST* ps)//删除数据{    assert(ps);    assert(ps->top > 0);    ps->top--;}bool StackEmpty(ST* ps)//判断栈是否为空{    assert(ps);    return ps->top == 0;}int StackSize(ST* ps)//栈内元素数量{    assert(ps);    return ps->top;}STDataType StackTop(ST* ps)//获得栈顶元素{    assert(ps);    assert(ps->top > 0);    return ps->a[ps->top - 1];}

队列结构

//队列结构typedef struct {    ST* push;    ST* pop;} MyQueue;

队列实现
队列创建

MyQueue* myQueueCreate()

MyQueue* myQueueCreate(){  MyQueue* newqueue = (MyQueue*)malloc(sizeof(MyQueue));   StackInit(&newqueue->push);  StackInit(&newqueue->pop); return newqueue;}

正常操作

插入数据

void myQueuePush(MyQueue* obj, int x)

void myQueuePush(MyQueue* obj, int x) {   assert(obj);   StackPush(&obj->push, x);}

判空等安全操作已在栈中实现

删除数据

int myQueuePop(MyQueue* obj)

int myQueuePop(MyQueue* obj) {   assert(obj); if (StackEmpty(&obj->pop) == NULL)//某个栈内没有元素{    while (StackEmpty(&obj->push) != NULL)//另一个栈中有元素，直到队头数据出现   {      StackPush(&obj->pop, StackTop(&obj->push));把有元素的栈的栈顶数据放入另一个栈 StackPop(&obj->push);//删除一下原栈中已经转移的数据  }   }int before = StackTop(&obj->pop);//记录了原栈最后一个数据 StackPop(&obj->pop);//删除了（对头数据）//这里将需要删除的数据也转移了一下   return before;//返回了删除的元素}

图解是通用的，而且每行代码都有解释

返回队列开头的数据

int myQueuePeek(MyQueue* obj)

int myQueuePeek(MyQueue* obj) {   assert(obj); if (StackEmpty(&obj->pop) == NULL)//数据转到的栈没有数据    {     return StackTop(&obj->push);//原栈不过有没有返回即可}return StackTop(&obj->pop);//pop栈中有数据，栈顶就是队头}

理清两个栈的作用

判断队列是否为空

bool myQueueEmpty(MyQueue* obj)

bool myQueueEmpty(MyQueue* obj) {   assert(obj);   if (obj->push == NULL && obj->pop == NULL)//两个栈都为空   {return true;   }   else   {      return false;   }}

队列销毁

void myQueueFree(MyQueue* obj)

void myQueueFree(MyQueue* obj){   assert(obj);  StackDestory(&obj->push);  StackDestory(&obj->pop);   free(obj);}

要从内到外

用队列实现栈

队列有着对尾入数据队头出数据的特点
栈只能顶进顶出
那么可以用两个队列，数据入栈时将数据输入q1队列，出栈时由q1队列队头出数据导入q2队列，知道遇到栈顶（也就是q1队列最后一个数据）删除即可。
这里q1，q2两个队列需要多次互相导数据，q1，q2的功能也会互相转换。

使用C语言简单实现

首先把队列拿过来

#pragma once// 链式结构：表示队列 #include #include #include typedef int QDataType;typedef struct QListNode{struct QListNode* next;QDataType data;}QNode;// 队列的结构 typedef struct Queue{QNode* front;QNode* rear;}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);

#include "Queue.h"// 链式结构：表示队列// 初始化队列 void QueueInit(Queue* q){assert(q);q->front = NULL;q->rear = NULL;}// 队尾入队列 void QueuePush(Queue* q, QDataType data){assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));assert(newnode);newnode->data = data;newnode->next = NULL;if (q->rear == NULL){assert(q->front == NULL);q->front = q->rear = newnode;}else{q->rear->next = newnode;q->rear = newnode;}}// 队头出队列 void QueuePop(Queue* q){assert(q);assert(q->front && q->rear);if (q->front->next == NULL){q->front = q->rear == NULL;}else{QNode* next = q->front->next;free(q->front);q->front = next;}}// 获取队列头部元素 QDataType QueueFront(Queue* q){assert(q);if (q->front == NULL && q->rear == NULL){return NULL;}return q->front->data;}// 获取队列队尾元素 QDataType QueueBack(Queue* q){assert(q);if (q->front == NULL && q->rear == NULL){return NULL;}return q->rear->data;}// 获取队列中有效元素个数 int QueueSize(Queue* q){assert(q);QNode* cur = q->front;int size = 0;while (cur){size++;cur = cur->next;}return size;}// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q){assert(q);return q->front == NULL;}// 销毁队列 void QueueDestroy(Queue* q){assert(q);QNode* cur = q->front;while (cur){QNode* next = cur->next;free(cur);cur = next;}q->front = q->rear = NULL;}

细节都在这里的栈和队列。
队列结构

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

栈的创建

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

将元素 x 压入栈顶

void myStackPush(MyStack* obj, int x)

void myStackPush(MyStack* obj, int x){   assert(obj);  if(!QueueEmpty(&obj->q1))//不为空   {      QueuePush(&obj->q1,x);   }   else//空不空为所谓   {      QueuePush(&obj->q2,x);   }}

压栈时优先将数据放入不为空的队列中，都为空时随意放入即可。

移除并返回栈顶元素

int myStackPop(MyStack* obj)

int myStackPop(MyStack* obj) {   assert(obj);   Queue* emptQ = &obj->q1;//有数据（假设）   Queue* nonEmptyQ = &obj->q2;//没有数据   if(!QueueEmpty(&obj->push))//判断   {emptQ = &obj->q2;nonEmptyQ = &obj->q1;   }   while(QueueSize(nonEmptyQ)>1)   {int front = QueueFront(nonEmptyQ);QueuePush(emptQ, front);//将头放入空队列QueuePop(nonEmptyQ);//转移后删除即可   }   int top = QueueFront(nonEmptyQ);//记录并删除   QueuePop(nonEmptyQ);   return top;}

返回栈顶元素

int myStackTop(MyStack* obj)

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

判一下空就好

如果栈是空的，返回 true ；否则，返回 false

bool myStackEmpty(MyStack* obj)

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

q1,q2都是空栈才是空

free

void myStackFree(MyStack* obj)

void myStackFree(MyStack* obj) {   assert(obj);   QueueDestroy(&obj->push);   QueueDestroy(&obj->pop);   free(obj);}

从内到外

循环队列

• 思路见图
  

代码如下

其实没有必要逐行注释，不管是哪方面来看博主所写的代码思想都是易懂的

typedef struct {    int* a;    int front;    int tail;    int k;} MyCircularQueue;bool myCircularQueueIsFull(MyCircularQueue* obj);bool myCircularQueueIsEmpty(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) {    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));    obj->a = (int*)malloc(sizeof(int)*(k+1));    obj->front = obj->tail = 0;    obj->k = k;    return obj;}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {    if(myCircularQueueIsFull(obj))    { return false;    }    obj->a[obj->tail] = value;    if(obj->tail == obj->k)    { obj->tail = 0;    }    else    { obj->tail++;    }    return true;}bool myCircularQueueDeQueue(MyCircularQueue* obj) {    if(myCircularQueueIsFull(obj))    { return false;    }    if(obj->front == obj->k)    { obj->front = 0;    }    else    { obj->tail++;    }    return true;}int myCircularQueueFront(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))    { return -1;    }    return obj->a[obj->front];}int myCircularQueueRear(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))    { return -1;    }    if(obj->tail == 0)    { return obj->a[obj->k];    }    else    { return obj->a[obj->tail-1];    }}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {    return obj->front == obj->tail;}bool myCircularQueueIsFull(MyCircularQueue* obj) {    if(obj->tail == obj->k && obj->front == 0)    { return true;    }    else    { return obj->tail+1 == obj->front;    }}void myCircularQueueFree(MyCircularQueue* obj) {    free(obj->a);    free(obj);}

总结

栈和队列的简单应用，是博主起记忆笔记作用的整理，三块内容也是力扣的原题

下次上二叉树

全民K歌电脑版