数据结构——栈和队列

一.前言

如果有友友看了我上一篇文章：数据结构——单链表，那么本篇的队列和栈你会发现到处是单链表的影子，所以我们的重心是在关于队列和栈的OJ题上。本文干货满满，高能不断，一定不要错过！码字不易，希望大家多多支持我呀！（三连＋关注，你是我滴神！）

二.前文回顾

顺序表和链表的区别

三.栈

3.1 栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out)的原则。
压栈: 栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈，出数据也在栈顶。

3.2 栈的实现

其实数组或者链表都是可以实现栈的，二者区别无法就是实现的方式有所不同，效率各有千秋。

要想用数组实现的话，那数组尾部就可以作为栈顶（尾插尾删方便）。

要想用链表实现的话，那链表头部得作为栈顶，然后进行多次头插入栈（这样出栈时方便，用头删即可）。想想如果是栈顶是在1的位置，那到时候出栈删除1时还得找到2进行重新链接，要用到双链表。所以我们的原则是能用单链表实现就用单链表~

相对而言，数组更合适实现栈~

3.2.1 初始化函数

这里有一点需要注意，当top一开始是0的时候，入栈完top++指向下一位.这样当我们打算输入（入栈）最后一个数据时，真正的栈顶并非top所指向的数据，而是top-1的指向。
//初始化函数
void STInit(ST* ps)
{
	assert(ps);
	ps->top = 0;
	ps->a = NULL;
	ps->capacity = 0;
}

3.2.2 销毁函数

//销毁函数
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

3.2.3 入栈函数

在准备扩容的时候一开始空间是0为什么这里可以用realloc来代替malloc呢？realloc不是只能在已有空间基础上扩容吗？

如果一开始没有空间，那么realloc在这时候是可以代替malloc来作出对于功能的。（为空可当成malloc，不为空就realloc）

//入栈函数
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	//扩容准备
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)relloc(ps->a, sizeof(STDataType)*newCapacity);
		if (tmp == NULL)
		{
			perror("relloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//入栈准备
	ps->a[ps->top] = x;
	ps->top++;

	
	
}

3.2.4 出栈函数

出栈挺简单，唯一要注意的就是当栈为空的时候，就不要继续出栈了。
//出栈函数
void STPop(ST* ps)
{
	assert(ps);
	//空
	assert(ps->top > 0);
	ps->top--;
}

3.2.5 计算大小函数

//计算大小函数
int STSize(ST* ps)
{
	assert(ps);

	return ps->top;

}

3.2.6 空栈函数
//判空（栈）函数
bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top==0;
}
看top指向是否空，如果为空则会返回1，不为空则返回0.

3.2.7 获取栈顶函数

//获取栈顶函数
STDataType STTop(ST* ps)
{
	assert(ps);
	//空
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

3.2.8 小测试

最后我们来测试是否满足栈的特点：后进先出

void TestStack1()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);//获取后一位的栈顶
	}
	printf("\n");

	STDestroy(&st);
}

3.3 全部代码

//Stack.h
pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>


typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

//初始化函数
void STInit(ST* ps);

//销毁函数
void STDestroy(ST* ps);

//入栈函数
void STPush(ST* ps, STDataType x);

//出栈函数
void STPop(ST* ps);

//计算大小函数
int STSize(ST* ps);

//空（栈）函数
bool STEmpty(ST* ps);

//获取栈顶函数
STDataType STTop(ST* ps);

——————————————————————————————-——————————

//Test,c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"


void TestStack1()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);//获取后一位的栈顶
	}
	printf("\n");

	STDestroy(&st);
}


int main()
{
	TestStack1();
	return 0;
}

——————————————————————————————————————————


//Stack,c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"


//初始化函数
void STInit(ST* ps)
{
	assert(ps);
	ps->top = 0;
	ps->a = NULL;
	ps->capacity = 0;
}


//销毁函数
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}


//入栈函数
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	//扩容准备
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("relloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//入栈准备
	ps->a[ps->top] = x;
	ps->top++;



}

//出栈函数
void STPop(ST* ps)
{
	assert(ps);
	//空
	assert(ps->top > 0);
	ps->top--;
}

//计算大小函数
int STSize(ST* ps)
{
	assert(ps);

	return ps->top;

}

//空（栈）函数
bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

//获取栈顶函数
STDataType STTop(ST* ps)
{
	assert(ps);
	//空
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

其实写到最后我们可以发现，栈其实就是顺序表的简化版，相当于定义了部分适用于栈特征的接口罢了~

四.栈的练习

4.1 有效的括号

链接：力扣——有效的括号

基本思路：

数量上最后再进行判断~
类型上：遇到右括号就进行匹配，看有没有对应的左括号。
顺序上：当遇到右括号时判断距离最进的括号是否为对应左括号。

那如何找到最近的括号呢？

左括号，入栈
右括号，出栈顶括号，进行匹配

//前面需要用到Stack.h与Stack.c的代码	
bool isValid(char* s)
	{
		ST st;
		STInit(&st);
		char topVal;
		while (*s)
		{
            //左括号入栈
			if (*s == '(' || *s == '[' || *s == '{')
			{
				STPush(&st, *s);
			}
            //右括号判定
			else
			{
				//数量不匹配——如果栈中没有左括号，
                //说明在s中右括号在左括号前面，那肯定是不行的
				if (STEmpty(&st))
				{
					STDestroy(&st);
					return false;
				}
                //在这一步说明栈中有左括号
				topVal = STTop(&st);//把栈顶的左括号存入topVal中
				STPop(&st);//压栈，使得下一次取排在栈顶前一位的左括号
				if ((*s == ']' && topVal != '[') || (*s == ')' && topVal != '(') || (*s                                     
                     == '}' && topVal != '{'))
             //这里我们不去判定括号与括号的对应，
             //去判断不对应的情况，这样筛选到最后的就是对应的                    
				{
					STDestroy(&st);//如果在栈顶中取出的左括号与条件中目前
                                   // 数组指向的右括号不对应，那就销毁栈并且返回错误
					return false;
				}
			}

			++s;//对数组中的每一个元素进行遍历
		}
        //到了最后如果栈里面还有左括号，那么就说明数量对不上，在STEmpty(&st)判断为0
        //如果栈里面没有左括号，那么在STEmpty(&st)判断为1
		//栈不为空，flase,说明数量不匹配
		bool ret = STEmpty(&st);
		STDestroy(&st);
		return ret;
	}

备注：千万不要想着去用switch，千万不要，除非你想要头脑风暴。。。。

五.队列

5.1队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)。
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。

5.2 队列的实现

队列也可以用数组或链表的结构实现，使用链表的结构表现更优一些，因为数组在实现出队列（头删）效率比较低~

这里我们采用单链表结构进行实现队列，既然队列核心是一端出一端入，那我们就先预设头节点（head）与尾节点（tail）的指向。

因为是不带哨兵位，所以我们插入第一个节点时既要赋值给head,又要赋值给tail。并且还要用到二级，因为形参的改变影响不了实参。（这里也不能用return,我们这里要返回两个值。）如果有友友理解不了二级指针可以移步至这篇文章单链表，里面的尾插部分有详细讲解哦~

切回正题，在这里我们可以采用新的方法来实现二级指针的功能。
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;
//入队列函数
void QueuePush(Que* pq, QDataType x);
我们可以再建立一个结构体，里面放置头指针和尾指针，用结构体接收，这样就可以改变二者的指向了。

5.2.1 初始化函数

//初始化函数
void QueueInit(Que* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

5.2.2 入队列函数

在我们处理好空间问题后，要进行入队列（尾插）就得先找到尾节点，不过这里还有一些小问题需要注意。

如果链表是空的呢？——赋值给它们2个

//入队列函数
void QueuePush(Que* pq, QDataType x)
{
	assert(pq);
    //创造新节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
    //给新节点插入数据
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail==NULL)//链表为空时
	{
		pq->head = pq->tail = newnode;
	}
	else//链表不为空时
	{
		pq->head->next = newnode;
		pq->tail = newnode;
	}
    pq->size++;
}

5.2.3 出队列函数

出队列其实就是头删，定义好下一位的指针next就可以实现了

不过这样写还有一个问题；在只剩下一个节点的时候，head可以顺利置空，但tail却没有置空变成了野指针。
//出队列函数
void QueuePop(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//空链表时不给删除
	if (pq->head->next == NULL)//只剩下一个节点时
	{
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}

5.2.4 获取头队列函数

//获取头队列函数
QDataType QueueFront(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

5.2.5 获取尾队列函数

//获取尾队列函数
QDataType QueueBack(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

5.2.6 判空（队列）函数

//判空（队列）函数
bool QueueEmpty(Que* pq)
{
	assert(pq);

	return pq->head == NULL;
}

5.2.7 计算队列大小函数

//计算大小函数
int QueueSize(Que* pq)
{
	assert(pq);

	return pq->size;
}

5.2.8 销毁函数

//销毁函数
void QueueDestroy(Que* pq)
{
	assert(pq);
	QNode* cur = pq->head;//创造一个方便遍历的指针
	while (cur)
	{
		QNode* next = cur->next;//记录每一次销毁后一位的指针
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;//置空，避免野指针
	pq->size = 0;
}

5.2.9 小测试

void TestQueue()
{
	Que q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);

	while (!QueueEmpty(&q))//遍历，链表不为空就继续
	{
		printf("%d ", QueueFront(&q));//打印头队列
		QueuePop(&q);//打印完就让其出队列
	}
	printf("\n");


	QueueDestroy(&q);

}

成功实现先进先出。

5.3 全部代码

//Queue.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;



//入队列函数
void QueuePush(Que* pq, QDataType x);

//初始化函数
void QueueInit(Que* pq);

//销毁函数
void QueueDestroy(Que* pq);

//出队列函数
void QueuePop(Que* pq);

//获取头队列函数
QDataType QueueFront(Que* pq);

//获取尾队列函数
QDataType QueueBack(Que* pq);

//判空（队列）函数
bool QueueEmpty(Que* pq);

//计算大小函数
int QueueSize(Que* pq);

————-——————————————————————————————————————

//Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"


//初始化函数
void QueueInit(Que* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

//入队列函数
void QueuePush(Que* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail==NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

//出队列函数
void QueuePop(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}

//获取头队列函数
QDataType QueueFront(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

//获取尾队列函数
QDataType QueueBack(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

//判空（队列）函数
bool QueueEmpty(Que* pq)
{
	assert(pq);

	return pq->head == NULL;
}

//计算大小函数
int QueueSize(Que* pq)
{
	assert(pq);

	return pq->size;
}

//销毁函数
void QueueDestroy(Que* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

———————————————————————————————————————————

//Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"


void TestQueue()
{
	Que q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);

	while (!QueueEmpty(&q))//遍历，链表不为空就继续
	{
		printf("%d ", QueueFront(&q));//打印头队列
		QueuePop(&q);//打印完就让其出队列
	}
	printf("\n");


	QueueDestroy(&q);

}


int main()
{
	TestQueue();
	return 0;
}

六.队列的练习

6.1选择题

学习完队列和栈我们可以知道，入队列是1 2 3 4 5那出队列就是1 2 3 4 5，那栈呢？也入栈1 2 3 4 5，出栈就一定是5 4 3 2 1吗？

第一问无疑是选B，那第二问又是怎么回事呢？我们看好这一句话“进栈过程可以出栈”，这意味着有多种可能性，其中最不可能的就是C选项了，3出栈前提是1 2 3入栈，那1出栈前提是1入栈，显然不符合事实。

6.2用队列实现栈

链接：力扣——用队列实现栈




typedef struct {

} MyStack;


MyStack* myStackCreate() {

}

void myStackPush(MyStack* obj, int x) {

}

int myStackPop(MyStack* obj) {

}

int myStackTop(MyStack* obj) {

}

bool myStackEmpty(MyStack* obj) {

}

void myStackFree(MyStack* obj) {

}

6.2.1 整体思路：

我们先列出两个队列，然后往其中一个队列Push1 2 3 4,要想实现后入先出的栈，就得把4优先Pop出来 .

为了实现Pop4，我们可以依次出队列中队头数据把它插入到另一个队列里，当剩下最后一个数据4时再Pop掉（不继续插入到另一个队列）

当我们想让5，6入队列的时候又应该去哪里呢？——去不为空的队列，然后再重复上述的操作（把n个数据的前n-1个导走）最后Pop出6（后入先出）。

所以大思路就是保持一个队列为空（导出数据），另一个不为空（存入数据）。

入队列：不为空的队列
出队列：不为空队列前N-1个出队列，插入空队列。删除剩余的数据。

代码解析：

MyStack* myStackCreate() {
    MyStack st;

    //......
    return &st
}

这个接口的作用仅仅是返回&st吗？——这个局部作用域一出来那么里面的变量都会销毁，这时候传st的地址已经是没意思的了，它已经变成一个野指针了。为了保证MyStack的对象还在，我们可以改用malloc来创造节点，这样出作用域时，malloc出来的空间还是在的。

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

	return pst;
}

6.2.2 Push函数（入队列）：

由于我们不知道哪个为空，哪个不为空，那么我们直接用判空条件来判断再进行入队列

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

}

6.2.3 Pop函数(出队列）：

还是一样的逻辑，不为空的队列往空队列导入。在这里我们假设q1为空，q2不为空。如果q1不为空（判空函数）那交换即可。

int myStackPop(MyStack* obj) {
	QNode* empty = &obj->q1;//假设q1为空
	QNode* nonEmpty = &obj->q2;//假设q2不为空
	if (!QueueEmpty(&obj->q1))//如果qi不为空
	{
		empty = &obj->q2;//交换
		nonEmpty = &obj->q1;

	}
	//前size-1个导入空队列
	while (QueueSize(nonEmpty) > 1)
	{
		QueuePush(empty, QueueFront(nonEmpty));
		//进行入队列，在空队列中存入在不为空队列中的首个数据
		QueuePop(nonEmpty);
		//再Pop掉该数据，使下一次循环是首数据后面的数据

	}//入一次出一次，直达剩下一个
	//这时候只剩下一个数据，获取栈顶元素
	int top = QueueFront(nonEmpty);//存储不为空队列中的元素
	QueuePop(nonEmpty);//再Pop掉该元素

	return top;//返回所谓的栈顶数据
	//至此，该函数完全实现在2个队列入好数据后，
	//结果返回的是后入队列的数据，实现了后进后出。
}

到这里大家是不是有疑惑，为什么都是&obj，到了empty传输时反而不用取地址了呢？

我们需要把类型认识清楚，q1与q2是队列的结构体，该结构体包含了头指针（head)，尾指针（tail),和size。对于我们所要实现的接口（Pop,Push,Creat)而言，它们想要改变的都是结构体的指针（tail,head等）来实现自身功能。所以这里需要&obj,而empty与nonEmpty已经是结构体指针了，就相当于&obj，也就不需要&了。

6.2.4 Top函数（取栈顶）：

这个函数要实现的功能是取栈顶元素，也就是取最后入队列的数据。这里我们可以直接复用前面所写的获取队列尾部数据函数（ QueueBack）来轻松实现。

int myStackTop(MyStack* obj) {
	//哪个队列不为空就去取该队列的尾部数据
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}

6.2.5 Empty函数（判空）:

在这里的判空应该是两个队列都为空，那才是空。一个为空的不算空。

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

6.2.6 Free（释放空间）函数：

这里我们不能直接free掉obj，因为在obj里面有两个队列q1,q2而这两个队列的底层是链表，所以我们在free之前记得使用销毁函数（QueueDestroy）（销毁链表）

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

6.2.7 全部代码

注：想要写题解或者测试，请自行添加上文关于Queue.c与Queue.h的代码段（下面代码能够复用的前提）


typedef struct {
	Que q1;
	Que 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))//如果q1为空
	{
		QueuePush(&obj->q1, x);
	}
	else
	{
		QueuePush(&obj->q2, x);
	}

}

int myStackPop(MyStack* obj) 
{
	QNode* empty = &obj->q1;//假设q1为空
	QNode* nonEmpty = &obj->q2;//假设q2不为空
	if (!QueueEmpty(&obj->q1))//如果qi不为空
	{
		empty = &obj->q2;//交换
		nonEmpty = &obj->q1;

	}
	//前size-1个导入空队列
	while (QueueSize(nonEmpty) > 1)
	{
		QueuePush(empty, QueueFront(nonEmpty));
		//进行入队列，在空队列中存入在不为空队列中的首个数据
		QueuePop(nonEmpty);
		//再Pop掉该数据，使下一次循环是首数据后面的数据

	}//入一次出一次，直达剩下一个
	//这时候只剩下一个数据，获取栈顶元素
	int top = QueueFront(nonEmpty);//存储不为空队列中的元素
	QueuePop(nonEmpty);//再Pop掉该元素

	return top;//返回所谓的栈顶数据
	//至此，该函数完全实现在2个队列入好数据后，
	//结果返回的是后入队列的数据，实现了后进后出。
}

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);
}

最后附上结构图，帮助大家理解~

这也是我们为什么不能直接free掉obj的原因。

6.3用栈实现队列

链接：力扣——用栈实现队列

typedef struct {

} MyQueue;


MyQueue* myQueueCreate() {

}

void myQueuePush(MyQueue* obj, int x) {

}

int myQueuePop(MyQueue* obj) {

}

int myQueuePeek(MyQueue* obj) {

}

bool myQueueEmpty(MyQueue* obj) {

}

void myQueueFree(MyQueue* obj) {

}

6.3.1 整体思路：

老规矩我们先创造两个栈，其中一个依次输入1 2 3 4，要想实现队列的先进先出，那最终要Pop的数就是1.至此，我们可以沿用与上一题差不多的思路（先入栈，再出栈导到另一个栈，最后再处理1.）。

当我们把1Pop掉时再尝试Push5 6，把2 3 4导回去再入栈5 6继续重复上述操作是没问题的，那能不能不把2 3 4导回原来的栈呢？——这时候的情况就发生了变化：可以把2 3 4全部Pop掉，这样第二个栈就空了，再把5 6导入第二个栈最终可以Pop出5.

这时候我们就可以制定规则了

pushst栈: 这个栈只能用来入栈。
popst栈：这个栈只能用来出栈。

跟上题一样先搞出两个栈出来；

MyQueue* myStackCreate() {
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	STInit(&obj->pushst);
	STInit(&obj->popst);

	return obj;
}

6.3.2 Push（入栈）函数

void myQueuePush(MyQueue* obj, int x) {
	STPush(&obj->pushst, x);
}

6.3.3 Peek(取头)函数

我们先来写Peek（获取头队列数据函数），要想获取首先得判断popst中是否为空，如果是空的我们需要从pushst中导出数据到popst里。这样才可以获取头队列数据。如果有友友对这里复用的函数命名不熟悉可以去目录对照查看。

int myQueuePeek(MyQueue* obj) {
	//哪个队列不为空就去取该队列的尾部数据
	if (STEmpty(&obj->popst))
	{
		//判断popst为空，开始导入数据
		while (!STEmpty(&obj->pushst))
		{
			STPush(&obj->popst, STTop(&obj->pushst));//导入数据后再进行删除头队列数据
			STPop(&obj->pushst);//导进一个删除一个，清空pushst
		}
	}
	return STTop(&obj->popst);
}

6.3.4 Pop（出栈）函数

到这一步我们就可以发现先写Peek的好处了，因为Peek已经先判断popst是否为空，为空就把pushst的数据搬过来，所以我们只需要处理好popst里面的数据就好了。

int myQueuePop(MyQueue* obj)
{
	int front = myQueuePeek(obj);//存储队列首个数据
	STPop(&obj->popst);//pop掉队列的头数据
	return front;//返回首个数据，达成用两个栈实现先进先出的队列
}

6.3.5 Empty（判空）函数

bool myQueueEmpty(MyQueue* obj) {
	return  QueueEmpty(&obj->pushst) && QueueEmpty(&obj->popst);
}

6.3.6 Free（释放空间）函数

void myQueueFree(MyQueue* obj) {
	STDestroy(&obj->pushst);
	STDestroy(&obj->popst);
	free(obj);
}

6.3.7 全部代码

注：想要写题解或者测试，请自行添加上文关于Stack.h与Stack.c的代码段（下面代码能够复用的前提）

typedef struct {
	ST pushst;
	ST popst;
} MyQueue;


MyQueue* myQueueCreate() {
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	STInit(&obj->pushst);
	STInit(&obj->popst);

	return obj;
}

void myQueuePush(MyQueue* obj, int x) {
	STPush(&obj->pushst, x);
}



int myQueuePeek(MyQueue* obj) {
	//哪个队列不为空就去取该队列的尾部数据
	if (STEmpty(&obj->popst))
	{
		//判断popst为空，开始导入数据
		while (!STEmpty(&obj->pushst))
		{
			STPush(&obj->popst, STTop(&obj->pushst));//导入数据后再进行删除头队列数据
			STPop(&obj->pushst);//导进一个删除一个，清空pushst
		}
	}
	return STTop(&obj->popst);
}

int myQueuePop(MyQueue* obj)
{
	int front = myQueuePeek(obj);//存储队列首个数据
	STPop(&obj->popst);//pop掉队列的头数据
	return front;//返回首个数据，达成用两个栈实现先进先出的队列
}




bool myQueueEmpty(MyQueue* obj) {
	return  STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}

void myQueueFree(MyQueue* obj) {
	STDestroy(&obj->pushst);
	STDestroy(&obj->popst);
	free(obj);
}

6.4 设计循环队列

链接：力扣——设计循环队列

typedef struct {

} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {

}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {

}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {

}

int myCircularQueueFront(MyCircularQueue* obj) {

}

int myCircularQueueRear(MyCircularQueue* obj) {

}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {

}

bool myCircularQueueIsFull(MyCircularQueue* obj) {

}

void myCircularQueueFree(MyCircularQueue* obj) {

}

图像示例：

循环原则：删除完数据front–,增加完数据rear++.

循环关键就是front到rear,虽然经过增删会改变它们的位置，但在定长数组中起点就是front，终点就是rear。但需要注意[front,rear)这是左闭右开的关系。因为rear插入数据后会指向下一位。

这里用数组实现比较轻松，用链表反而会很复杂。

第一缺陷：用rear取队尾数据不好取，因为rear是每次插入数据后才往后移，如果想取队尾部那就得用到rear->pre了，这就变成了双向链表了。又或者再多给一个指针，变成3个指针。
第二缺陷：不好判满，链表为空rear与front指向同一处，而只有一个数据时，还是指向同一处。
第三缺陷：当链表满时rear又指向了与front一致的地方，与链表为空的情况一致，空与满判断不了。

所以为了解决这个问题，很多人选择多开一处空间，该空间不存储数据就为了让rear指到最后。

所以用链表始终存在一些问题，故而我们选择比链表适合一些的数组来实现。

6.4.1 整体思路：

这里判定满的条件就是rear+1，当rear的下标是4时可以想象+1就回到front的指向位置。所以最终的规律就是(rear+1)%(k+1)==front.

我们先来模拟一下增删：

当准备插入7时，只要我们的判满条件达成理论上是不会继续插入滴~我们继续删除数据~

当我们把6给删除后链表为空链表了，不能再继续删除了，而这时候我们发现front与rear相等，也满足了判空条件。

总结：实现循环链表的两个关键点

判空：front==rear
判满：（rear+1)%(k+1)==front

6.4.2 创造函数（Creat)

typedef struct {
	int* a;//定义数组
	int front;//起点
	int rear;//终点
	int k;//有效数字
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	//多开一个空间方便区分空和满
	obj->a = (int*)malloc(sizeof(int) * (k + 1));
	obj->front = obj->rear = 0;
	obj->k = k;
    return obj;
}

6.4.2 判空与判满函数（Is(Empty)/(Full))

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return obj->front == obj->rear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
	return (obj->rear + 1)%(obj->k+1) == obj->front;
}

6.4.3 EnQueue(插入)函数

在三种插入情况中我们需要注意第三种：rear循环绕到开头。

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	if (myCircularQueueIsFull(obj))//如果已经满了
	{
		return false;
	}
	//没满情况下
	obj->a[obj->rear] = value;
	obj->rear++;

	obj->rear %= (obj->k + 1);
	//针对第三种情况当rear在下标4插入7时rear++变成5需要循环到头部

	return true;

}

6.4.4 DeQueue（删除）函数

删除完数据front++，那front也会遇到跟上面rear一样的问题，当指向尾时再++需要循环绕到头部。

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))//如果已经是空的
	{
		return false;
	}

	obj->front++;
	obj->front %= (obj->k + 1);
	return true;
}

6.4.5 Front（取头）函数

int myCircularQueueFront(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))//如果已经是空的
	{
		return -1;
	}
	else
	{
		return obj->a[obj->front];
	}
}

6.4.6 rear（取尾）函数

取队尾函数就不像上面取队头那么好取了。正常的队尾取到rear-1就行，但如果是这种情况呢？取到-1该怎么办。

虽然可以通过if条件来判断并修改，但这里我们来引用一种巧妙的方法；

int myCircularQueueRear(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))//如果已经是空的
	{
		return -1;
	}
	else
	{
		return obj->a[(obj->rear+obj->k)%(obj->k+1)];
	}
}

6.4.7 Free（释放空间）函数

void myCircularQueueFree(MyCircularQueue* obj) {
	free(obj->a);
	free(obj);
}

6.4.8 全部代码




typedef struct {
	int* a;//定义数组
	int front;//起点
	int rear;//终点
	int k;//有效数字
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	//多开一个空间方便区分空和满
	obj->a = (int*)malloc(sizeof(int) * (k + 1));
	obj->front = obj->rear = 0;
	obj->k = k;
	return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return obj->front == obj->rear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
	return (obj->rear + 1)%(obj->k+1) == obj->front;
}


bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	if (myCircularQueueIsFull(obj))//如果已经满了
	{
		return false;
	}
	//没满情况下
	obj->a[obj->rear] = value;
	obj->rear++;

	obj->rear %= (obj->k + 1);
	//针对第三种情况当rear在下标4插入7时rear++变成5需要循环到头部

	return true;

}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))//如果已经是空的
	{
		return false;
	}

	obj->front++;
	obj->front %= (obj->k + 1);
	return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))//如果已经是空的
	{
		return -1;
	}
	else
	{
		return obj->a[obj->front];
	}
}

int myCircularQueueRear(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))//如果已经是空的
	{
		return -1;
	}
	else
	{
		return obj->a[(obj->rear+ obj->k)%(obj->k+1)];
	}
}



void myCircularQueueFree(MyCircularQueue* obj) {
	free(obj->a);
	free(obj);
}

七.结语

其实队列和栈的实现我们看作单链表的部分实现，因为我们只需要完成二者特定的结构性质就行了。所以只要单链表学扎实，想实现还是很轻松滴~另外提一嘴，4道oj题非常重要！里面可以帮助我们更加深入理解栈和队列。最后感谢大家的观看，友友们能够学习到新的知识是额滴荣幸，期待我们下次相见~

原文链接：https://blog.csdn.net/fax_player/article/details/133249808