【数据结构】--- 栈和队列-阿里云开发者社区

【数据结构】--- 栈和队列

2024-10-12 12

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构】--- 栈和队列

前言

前面学习了数据结构的顺序表、单链表、双向循环链表这些结构；现在就来学习栈和队列，这里可以简单的说栈和队列是具有特殊化的线性表

一、栈

1.1、栈的概念和结构

栈是一种遵循先入后出逻辑的线性数据结构。

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

栈中的数据元素遵循先进后出（LIFO）的原则；也就是所谓的后来者居上

如图所示，我们把堆叠元素的顶部称为“栈顶”，底部称为“栈底”。将元素添加到栈顶的操作叫做“入栈”，删除栈顶的元素叫做“出栈”。

从图中我们可以看出，栈数据的出栈和入栈都在栈顶；这就是栈数据先进后出的原则。

1.2、栈的实现

栈的实现可以使用数组来实现，当然也可以使用链表来实现，这里就用数组来实现栈。

用数组来实现栈就和之前顺序表的实现有些相似，对顺序表不了解的话可以看一下前面的

【数据结构】--- 顺序表

首先先来看一下，栈这个数据结构都要实现哪些功能：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
typedef int SType;
typedef struct Stack
{
  SType* arr;
  int size;  //栈顶
  int num;   //空间大小
}Stack;
 
//初始化
void STInit(Stack* ps);
//判断栈是否为空
bool STEmpty(Stack* ps);
//入栈
void STPush(Stack* ps, SType x);
//出栈
void STPop(Stack* ps);
//取栈顶数据
SType STtop(Stack* ps);
//获取栈中数据个数
int STSize(Stack* ps);
//栈的销毁
void STDesTroy(Stack* ps);

1.2.1、初始化

//初始化
void STInit(Stack* ps)
{
  assert(ps);
  ps->arr = NULL;
  ps->size = ps->num = 0;
}

1.2.2、判断栈是否为空

判断栈是否为空？如果为空，就返回true；如果不为空，就返回false。

//判断栈是否为空
bool STEmpty(Stack* ps)
{
  assert(ps);
  return ps->size == 0;
}

1.2.3、入栈

入栈，在栈顶插入数据（和顺序表尾插相似）

//入栈
void STPush(Stack* ps, SType x)
{
  assert(ps);
  //判断空间大小是否足够
  if (ps->num <= ps->size)
  {
    int newnum = (ps->num == 0) ? 4 : 2 * ps->num;
    SType* tmp = (SType*)realloc(ps->arr, newnum * sizeof(Stack));
    if (tmp == NULL)
    {
      perror("realloc filed");
      exit(1);
    }
    ps->arr = tmp;
    ps->num = newnum;
  }
  ps->arr[ps->size++] = x;
}

1.2.4、出栈

出栈，删除栈顶的数据（和顺序表尾删相似）

//出栈
void STPop(Stack* ps)
{
  assert(ps); //不能传NULL
  assert(!STEmpty(ps));  //栈不能为空
  ps->size--;
}

1.2.5、取栈顶数据

取栈顶数据，将栈顶的数据返回即可

//取栈顶数据
SType STtop(Stack* ps)
{
  assert(ps); //不能传NULL
  assert(!STEmpty(ps));  //栈不能为空
  return ps->arr[ps->size - 1];
}

1.2.6、获取栈中数据个数

获取栈中数据个数，这里size就是栈的数据个数

//获取栈中数据个数
int STSize(Stack* ps)
{
  assert(ps);
  return ps->size;
}

1.2.7、销毁栈

这里，动态开辟的空间要进行释放，养成好习惯

//栈的销毁
void STDesTroy(Stack* ps)
{
  assert(ps);
  if (ps->arr)
    free(ps->arr);
  ps->arr = NULL;
  ps->size = ps->num = 0;
}

二、队列

2.1、队列的概念和结构

队列，是一种遵循先入先出规则的线性数据结构。

顾名思义，队列模拟了现实生活中排队现象，即新来的人不断加入队列队尾，而位于对头的人逐个离开

队列只允许在一端进行插入数据操作，在另一端进行删除数据操作

如图，我们将队列头部称为“对头（队首）”，尾部称为“队尾”；

将把元素插入到队尾操作称为“入队”，删除队首的数据的操作称为“出队”

2.2、队列的实现

队列的实现，这里也是即可以使用数组来实现，也可以使用链表来实现；这里使用链表来实现队列

用链表来实现队列就和之前链表的实现有些相似，对单链表不了解的话可以看一下前面的

【数据结构】--- 单链表的实现

先来卡看队列的基本功能

typedef int QType;
typedef struct QueueNode //队列节结构
{
  QType data;
  struct QueueNode* next;
}QueueNode;
typedef struct Queue //队列结构
{
  int size;   //队列中的数据个数
  QueueNode* phead; //队头
  QueueNode* ptial; //队尾
}Queue;
 
//初始化
void QueueInit(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//入队列--从队尾删除数据
void QueuePush(Queue* pq);
//出队列--从对头删除数据
void QueuePop(Queue* pq);
//取队头数据
QType QueueFront(Queue* pq);
//取队尾数据
QType QueueBack(Queue* pq);
//获取队列数据个数
int QueueSize(Queue* pq);
//销毁队列
void QueueDesTroy(Queue* pq);

2.2.1、初始化

//初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->phead = pq->ptial = NULL;
  pq->size = 0;
}

2.2.2、判断队列是否为空

如果队列为空，返回true；如果不为空，返回false

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->size == 0;
}

2.2.3、入队列

从队列尾部插入数据，与单链表尾插类似

//入队列--从队尾插入数据
void QueuePush(Queue* pq, QType x)
{
  assert(pq);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  newnode->data = x;
  newnode->next = NULL;
  if (QueueEmpty(pq)) // 队列为空
  {
    pq->phead = pq->ptial = newnode;
  }
  else {  //队列不为空
    pq->ptial->next = newnode;
    pq->ptial = newnode;
  }
  pq->size++;
}

2.2.4、出队列

从队头删除数据，与链表头删类似

//出队列--从对头删除数据
void QueuePop(Queue* pq)
{
  assert(pq);  //不能传NULL
  assert(!QueueEmpty(pq));  //队列不能为空
  QueueNode* del = pq->phead;
  pq->phead = pq->phead->next;
  if (pq->size == 1)  //队列只有一个节点
  {
    pq->ptial = NULL;
  }
  pq->size--;
  free(del);
  del = NULL;
}

2.2.5、取队头数据

取队头的数据返回

//取队头数据
QType QueueFront(Queue* pq)
{
  assert(pq);  //不能传NULL
  assert(!QueueEmpty(pq));  //队列不能为空
  return pq->phead->data;
}

2.2.6、取队尾数据

取队尾数据返回

//取队尾数据
QType QueueBack(Queue* pq)
{
  assert(pq);  //不能传NULL
  assert(!QueueEmpty(pq));  //队列不能为空
  return pq->ptial->data;
}

2.2.7、获取队列数据个数

获取队列数据个数，这里实现队列时，定义了一个结构体成员size记录队列数据个数。

//获取队列数据个数
int QueueSize(Queue* pq)
{
  assert(pq);  //不能传NULL
  return pq->size;
}

2.2.8、销毁队列

队列是由链表实现的，而链表是动态开辟的内存，记得释放。

//销毁队列
void QueueDesTroy(Queue* pq)
{
  assert(pq);  //不能传NULL
  assert(!QueueEmpty(pq));  //队列不能为空
  QueueNode* pcur = pq->phead;
  while (pcur)
  {
    QueueNode* del = pcur;
    pcur = pcur->next;
    free(del);
    del = NULL;
  }
  pq->phead = pq->ptial = NULL;
  pq->size = 0;
}

感谢各位大佬支持并指出问题，

如果本篇内容对你有帮助，可以一键三连支持以下，感谢支持！！！