【数据结构】栈和队列的模拟实现（两个方式实现）

前言

💓作者简介： 加油，旭杏，目前大二，正在学习C++，数据结构等👀

💓作者主页：加油，旭杏的主页👀

⏩本文收录在：再识C进阶的专栏👀

🚚代码仓库：旭日东升 1👀

🌹欢迎大家点赞 👍 收藏 ⭐ 加关注哦！💖

学习目标：

       这一篇博客将学习栈和队列的相关知识，栈和队列是两种基础的数据结构，在现在一定要打好基础，在之后的学习生涯中，也常常遇见，例如：深度优先搜索（DFS）广度优先搜索（BFS）……今天要学习栈和队列的模拟实现：用数组模拟实现栈，用单链表模拟实现队列，用数组模拟实现队列。

学习内容：

通过上面的学习目标，我们可以列出要学习的内容：

1. 用数组模拟实现栈
2. 用数组模拟实现队列
3. 用单链表模拟实现队列

一、栈的相关知识

1.1 栈的概念及结构

下面先来一段大白话，在介绍栈的文章中都会出现的。

       栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作（类似于尾插尾删）。我们先来介绍两个概念——栈顶与栈底：进行数据插入和删除操作的一端为栈顶，而另一端为栈底。高大上一点的叫法是：栈中的元素遵守后进先出LIFO(Last In First Out)的原则。

下面，我们在来介绍两个操作——圧栈与入栈：

• 压栈：栈的插入操作是进栈/压栈/入栈，入数据在栈顶；
• 出栈：栈的删除操作是出栈，出数据在栈顶。

  1.2 栈的实现

         现在，我们学习了两个数据结构：顺序表与链表，到底用哪个数据结构实现栈比较好呢？在这里我们选用数组来模拟实现栈。

  为什么我们要用数组模拟实现栈会更好一些？

         栈的两个操作无疑就是尾插与尾删，这两个操作在数组中都比较容易实现（相对于链表），而且数组存储的数据内容比较集中，CPU高速缓存命中率高，尽可能小地不污染缓存区，所以用数组模拟实现比较好一些。

  
  （图片来源网络，侵删）

         在现实生活中，我们一般要实现能够进行动态增长的栈，而不是静态的栈（比较死板，在实际应用中不常见）。虽然，静态的栈在实际生活中不常见，但是在算法题目中还是可以进行使用，而且在算法题中，我们不用考虑内存泄漏问题hh。下面来实现吧！

  代码一：实现动态的栈

  第一步，我们先来定义要使用的头文件：

  #include   //必须要包含的头文件
  #include  //要使用assert进行断言，防止出现一下不好的情况发生
  #include  //在C语言中，没有提供bool变量
  #include   //使用一些申请内存空间的函数
  

  第二步，我们要让主角登场，构造栈的结构体：

  typedef int StDatatype; // 为了方便以后更改数组中的数据类型
  typedef struct stack {
  	StDatatype* a;  // 一个动态空间
  	int top;   // 表示栈的栈顶
  	int capacity; // 表示栈现在有多少空间
  }ST;

  第三步，我们要定义一些我们要实现栈功能的一些函数：栈的初始化（定义一个结构，一定要初始化成员变量）、栈的销毁、栈的插入操作、栈的删除操作、查看栈的栈顶元素、查看栈的大小、查看栈是否为空

  //栈的初始化
  void stackinit(ST* stk);
  //栈的插入操作
  void stackpush(ST* stk, StDatatype x);
  //栈的删除操作
  void stackpop(ST* stk);
  //返回栈的栈顶元素
  StDatatype stacktop(ST* stk);
  //判断栈是否为空
  bool stackempty(ST* stk);
  //返回栈的大小
  int stacksize(ST* stk);
  //销毁栈
  void stackdestroy(ST* stk);

  栈的初始化操作：

  void stackinit(ST* stk)
  {
  	assert(stk); //防止传空指针
  	//有两个方式进行初始化
  	//法1
  	stk->a = NULL;
  	stk->capacity = 0;
  	stk->top = 0; //如果这里指向0，top表示的是栈的大小
  }
  //法2
  void stackinit(ST* stk)
  {
      assert(stk);
      stk->a = NULL;
      stk->capacity = 0;
      stk->top = -1; //如果这里指向-1，top表示的是栈顶元素的下标
  }

  栈的销毁操作：

  void stackdestroy(ST* stk)
  {
  	assert(stk);
  	free(stk->a);
  	stk->a = NULL; // 别忘记置空，防止野指针出现
      free(stk);
      stk = NULL;
  }
  // 因为栈所使用的是数组，所以直接销毁即可

  栈的插入操作：

  void stackpush(ST* stk, StDatatype x)
  {
  	assert(stk);
  	//因为我们在这里的栈的空间是没有创建的
  	if (stk->capacity == stk->top) 
  	{
  		int newcapacity = stk->capacity == 0 ? 4 : stk->capacity * 2;
  		StDatatype* tmp = (StDatatype*)realloc(stk->a, newcapacity * sizeof(StDatatype));
  		if (tmp == NULL) {
  			perror(tmp);
  			return;
  		}
  		stk->a = tmp;
  		stk->capacity = newcapacity;
  	}
  //插入操作相当于尾插
  	stk->a[stk->top] = x;
  	stk->top++;  // 别忘了栈顶要加1
  }

  栈的删除操作：

  void stackpop(ST* stk)
  {
  	assert(stk);
  	assert(stk->top > 0);
  	stk->top--;
  }

  返回栈的栈顶元素：

  StDatatype stacktop(ST* stk)
  {
  	assert(stk);
  	assert(stk->top > 0);
  	return stk->a[stk->top - 1]; // top == 0
      //return stk->a[stk->top];  // top == -1
  }

   判断栈是否为空：

  bool stackempty(ST* stk)
  {
  // 第一种写法：
  	assert(stk);
  	if (stk->top == 0)
  	{
  		return true;
  	}
  	return false;
  // 第二种写法：
  	//return stk->top == 0;
  }
  

  返回栈的大小：

  int stacksize(ST* stk)
  {
  	assert(stk);
  	return stk->top;  // top == 0
      //return stk->top + 1; // top == -1
  }

  代码二：实现静态的栈

  struct my_stack
  {
      int a[10];
      int size;
      int capacity;
  }

  二、队列的相关知识

  2.1 队列的概念及结构

         队列在日常生活中无处不在，排队就是一种典型的队列。对此，我们大致可以得知：队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的性质。和栈一样，队列具有两个基本操作——入队和出队：

  入队：进行插入操作的一端称为队尾；

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

  2.2 队列的实现

         与实现栈类似，我们先来讨论一下使用哪种数据结构方便一些？是使用顺序表呢，还是使用链表呢？是使用单链表呢还是使用双向链表？

         分析一下队列的插入和删除操作，发现插入操作是尾插，而删除操作是头删。在实现顺序表和链表时，对于头删操作来说，链表更为简单，而顺序表需要进行移动数据，效率较低。因此，我们使用链表来实现操作。

  代码一：链表实现队列

  第一步，我们还是先将头文件加上：

  #include 
  #include 
  #include 
  #include 

  第二步，我们来建立一下队列的数据结构：

  typedef int QueDatatype;
  typedef struct queue {
  	QueDatatype x;
  	struct queue* next;
  }Queue;
  //由于要用二级指针，并且我们还有多个成员，
  //然后就用结构体
  typedef struct Qnode {
  	Queue* phead;
  	Queue* ptail;  // 存储链表的尾结点，方便于尾插
  	int size;
  }Qnode;

   第三步，我们来定义一下队列的功能：队列的初始化，队列的销毁，队列的插入操作，队列的删除操作，返回队列的队头元素，返回队列的大小，检查队列是否为空。

  //队列初始化
  void queueinit(Qnode* qnd);
  //队列销毁
  void queuedestroy(Qnode* qnd);
  //队列的插入操作
  void queuepush(Qnode* qnd, QueDatatype x);
  //队列的删除操作
  void queuepop(Qnode* qnd);
  //队列的对头元素
  QueDatatype queuefront(Qnode* qnd);
  //队列的大小
  int queuesize(Qnode* qnd);
  //检查队列是否为空
  bool quueueempty(Qnode* qnd);

  队列的初始化操作：

  void queueinit(Qnode* qnd)
  {
  	assert(qnd);
  	qnd->phead = qnd->ptail = NULL;
  	qnd->size = 0;
  }

  队列的销毁操作：

  void queuedestroy(Qnode* qnd)
  {
  	assert(qnd);
  	//销毁是要从头到尾进行销毁的
  	Queue* cur = qnd->phead;
  	while (cur)
  	{
  		Queue* del = cur->next;
  		free(cur);
  		cur = del;
  	}
  // 只有一个结点的情况，会出现一个野指针
  	qnd->phead = qnd->ptail = NULL;
  	qnd->size = 0;
  }

  队列的插入操作：

  void queuepush(Qnode* qnd, QueDatatype x)
  {
  	assert(qnd);
  	//创建好了结构体，然后进行操作
  	Queue* tmp = (Queue*)malloc(sizeof(Queue));
  	//防止创建失败
  	if (tmp == NULL)
  	{
  		perror(tmp);
  		return;
  	}
  	tmp->x = x;
  	tmp->next = NULL;
  	//将这个新结点链接到链表中
  	if (qnd->phead == NULL)
  	{
  		qnd->phead = qnd->ptail = tmp;
  	}
  	else 
  	{
  		qnd->ptail->next = tmp;
  		qnd->ptail = tmp;
  	}
  	qnd->size++;
  }

  队列的删除操作：

  void queuepop(Qnode* qnd)
  {
  	assert(qnd);
  	//头结点不能为空
  	assert(qnd->phead);
  	//其次，在只有一个结点的过程中，会出现野指针
  	Queue* del = qnd->phead;
  	qnd->phead = del->next;
  	free(del);
  	del = NULL;
  	if (qnd->phead == NULL)
  	{
  		qnd->ptail = NULL;
  	}
  	qnd->size--;
  }

  返回队列的队头元素：

  QueDatatype queuefront(Qnode* qnd)
  {
  	assert(qnd);
  	//不能队列为空
  	assert(qnd->phead);
  	return qnd->phead->x;
  }

  返回队列的大小：

  int queuesize(Qnode* qnd)
  {
  	assert(qnd);
  	return qnd->size;
  }

  检查队列是否为空：

  bool quueueempty(Qnode* qnd)
  {
  	assert(qnd);
  	//if (qnd->phead ==NULL)
  	//{
  	//	return true;
  	//}
  	//return false;
  	return qnd->phead == NULL;
  }

  代码二：数组实现队列

  int q[N], hh, tt = -1;

  学习产出：

  1. 用数组模拟实现栈
  2. 用数组模拟实现队列
  3. 用单链表模拟实现队列