[数据结构]~栈和队列(0-1)

 前言

作者：小蜗牛向前冲

名言：我可以接收失败，但我不能接收放弃

 如果觉的博主的文章还不错的话，还请点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。

目录

一 “栈”

二 栈的实现

1 栈的定义

2 栈功能的实现

 三 “队列”

四 队列的实现

1 队列的定义 

 五 栈和队列的区别

---

栈和队列作为一种典型的线性表，都是基于线性表(顺序表)实现的，有人可能会问，我都有线性表了，为什么还要知道栈和队列呢？

举个例子：

有个小平大厨，他要去做一道名菜，可能要花费上百道刀工，在此期间他会换不同的刀去完成不同的工艺，我们试想一下难道我用一把刀就不能完成各种刀工，其实也是可以的，那小平大厨为什么要那么麻烦去换不同的刀呢?那大家肯定会说这样方便啊！对没错就是方便。

其实换到数据结构上来说，由于我们会频繁的入栈、出栈、取栈顶元素，怎么操作都是最常用的，所以我们就定义栈和队列来完成他，省的我们去运用更麻烦的线性表，降低我们出错的概率。

下面我们就一起去认识栈和队列吧！

一 “栈”

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底
压栈(入栈)：栈的插入操作，数据会在栈顶

 出栈：栈的删除操作叫做出栈。出数据也在栈顶

我们可以理解为出栈就为压栈的逆过程

栈的特点：先进后出

二 栈的实现

对于栈来说，由于他都是尾插和尾删数据，所以我们选择用顺序表来实现他，此时间复杂度为O（1）。

1 栈的定义

这里我们在Stack.h的头文件中包含以下内容：

#pragma once
 
#include
#include
#include
#include
 
typedef  int STDataType;
//定义栈
typedef struct Stack
{
	STDataType* arr;//数据类型
	int pos;//数组下标
	int capacity;//栈的容量
}ST;
 
//初始化
void StackInit(ST* ps);
//销毁
void StackDestroy(ST* ps);
//入栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
显示返回栈顶数据
STDataType StackTop(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps);
//返回栈的长度
int StackSize(ST* ps);

2 栈功能的实现

#include"Stack.h"
//初始化
void StackInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;//初始数组为空
	ps->pos = ps->capacity = 0;//初始为0
}
 
//销毁
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->arr);//arr是整个栈的地址
	ps->arr = NULL;
	ps->capacity = ps->pos = 0;
}
 
//入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//判断栈的空间是否满
	if (ps->pos == ps->capacity)
	{
		//扩容
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//扩2倍
		STDataType* tmp = (STDataType*)realloc(ps->arr,newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("reamlloc fail");
			exit(-1);
		}
		//跟新容量
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//入栈
	ps->arr[ps->pos] = x;
	ps->pos++;//下标++
}
 
//出栈
void StackPop(ST* ps)
{
	assert(ps);
	//断言栈是否为空
	assert(!StackEmpty(ps));
	--ps->pos;
}
 
//判断栈是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->pos == 0;
}
 
//显示返回栈顶数据
STDataType StackTop(ST* ps)
{
	assert(ps);
	//断言栈是否为空
	assert(!StackEmpty(ps));
	return  ps->arr[ps->pos - 1];//下标已经前移
}
 
//返回栈的长度
int StackSize(ST* ps)
{
	assert(ps);
	return ps->pos;
}

在这里我们重点为大家刨析压栈，出栈，取栈的写法。

（1）压栈

//入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//判断栈的空间是否满
	if (ps->pos == ps->capacity)
	{
		//扩容
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//扩2倍
		STDataType* tmp = (STDataType*)realloc(ps->arr,newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("reamlloc fail");
			exit(-1);
		}
		//跟新容量
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//入栈
	ps->arr[ps->pos] = x;
	ps->pos++;//下标++
}

这里我们的实现思路是：

判断栈的空间是否以满；

在进行入栈

（2）出栈

//出栈
void StackPop(ST* ps)
{
	assert(ps);
	//断言栈是否为空
	assert(!StackEmpty(ps));
	--ps->pos;
}

出栈的实现是非常简单的，只要将pos的标记--即可。

（3）取栈

//显示返回栈顶数据
STDataType StackTop(ST* ps)
{
	assert(ps);
	//断言栈是否为空
	assert(!StackEmpty(ps));
	return  ps->arr[ps->pos - 1];//下标已经前移
}

我们直接返回栈顶指针即可

每当我们完成一个功能时候，我们都应该去测试一下：

 三 “队列”

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

出队列：进行删除操作的一端称为队头

 

四 队列的实现

1 队列的定义 

我们同样在Queue头文件在实现:

#pragma once
 
#include
#include
#include
#include
 
typedef  int QDataType;
//定义队列
typedef struct QueueNode
{
	QDataType data;//数据类型
	struct QueueNode* next;
}QNode;
 
//定义指向头和尾的二个指针
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;
 
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//返回指向队头的数据的指针
QDataType QueueFront(Queue* pq);
//返回指向队尾的数据的指针
QDataType QueueBack(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//返回队列的大小
int QueueSize(Queue* pq);

由于栈和队列中定义是差不多，这里就不在过的的说明了。

2 队列的实现

这里就直接上代码，里面有详细的注释，大家不懂就可以看看。

大家在实现队列时可以对照着头文件的函数功能经行实现。

#define  _CRT_SECURE_NO_WARNINGS
 
#include"Queue.h"
 
//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
 
//销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;//指向下个节点
		free(del);
	}
	pq->head = pq->tail = NULL;//防止出现野指针
	pq->size = 0;
}
 
//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//申请节点
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode==NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newNode->data = x;
		newNode->next = NULL;
	}
	//队列为空
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newNode;
	}
	//不为空
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;//tail指针指向newNode
	}
	pq->size++;
}
 
//出队
void QueuePop(Queue* pq)
{
	assert(pq);
	//断言队列是否为空
	assert(!QueueEmpty(pq));
	//当队列中就一个数据时
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;//头变为下个节点
		free(del);
		del = NULL;
	}
	pq->size--;
}
 
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->tail == NULL;
}
 
//返回指向队头的数据的指针
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//断言队列是否为空
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
 
//返回指向队尾的数据的指针
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	//断言队列是否为空
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
 
//返回队列的大小
int QueueSize(Queue* pq)
{
	return pq->size;
}

下面我们继续测试一下队列是否能够成功实现自己的功能：

 五 栈和队列的区别

栈和队列区别：

(1)操作的限定不同:

栈是在栈顶进栈顶出，无法对栈底进行直接操作。

队列是在队尾入队头出，可以对二边进行操作。

(2）操作的规则不同:

栈是先进后出，新来的成员从栈顶入，老成员要想离开，就得先让栈顶的成员先离开。

队列是先进先出,新来的成员总是在队尾插入，每次离开的成员都是从队头离开。

(3)遍历数据速度不同:

栈是只能从顶部取数据，也就是说最先进入栈底的，需要遍历整个栈才能取出来，而且在遍历数据的同时需要为数据开辟临时空间，保持数据在遍历前的一致性

队列是通过地址指针进行遍历，而且可以从头部或者尾部进行遍历，但不能同时遍历，无需开辟空间，因为在遍历的过程中不影响数据结构，所以遍历速度要快