深入理解栈与队列：从基本概念到高级实现-阿里云开发者社区

🐳一、栈

💨1.1 栈的概念及结构

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

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

💨1.2 栈的创建

栈的实现一般可以使用 数组或者链表 实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

✨<1> 栈的存储结构

下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
//typedef int STDataType;
//#define N 10
//typedef struct Stack
//{
//  STDataType _a[N];
//  int _top; // 栈顶
//}Stack;
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;    // 栈顶
  int capacity;  // 容量 
}Stack;

✨<2> 栈的接口

// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

💨1.3 栈的实现

💥【1】初始化栈

创建一个空的栈，使其数组指针为 NULL，容量为 0，栈顶指针为 0

// 初始化栈 
void StackInit(Stack* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;//top指向栈顶元素的下一个
  // 表示top指向栈顶元素
  //pst->top = -1;
}

💥【2】进栈

初始化：首先，函数通过assert来检查传入的栈指针ps是否非空，以确认该栈存在。如果栈已满（ps->top == ps->capacity），则不执行任何操作。

扩容：如果栈不满，但接近满载，代码将进行扩容操作。如果栈的当前容量ps->capacity为 0（即初始状态或刚经历过扩容），新的容量设为 4。否则，新的容量为当前容量的两倍。这样做是为了预先保留足够的空间，避免频繁的扩容操作。

重新分配内存：使用realloc函数重新分配栈的内存空间。新的内存大小为新的容量乘以数据类型的大小。如果重新分配失败（realloc返回NULL），则输出错误信息并返回。

数据入栈：将数据data存储在栈顶的位置，即将data赋值给ps->a[ps->top]。然后，栈顶指针ps->top自增 1，表示栈中多了一个元素。

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
  assert(ps);
  if (ps->capacity == ps->top)
  {
    int newcapacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;
    STDataType* temp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
    if (temp == NULL)
    {
      perror("realloc fail");
      return;
    }
    ps->a = temp;
    ps->capacity = newcapacity;
  }
  ps->a[ps->top] = data;
  ps->top++;
}

💥【3】出栈

初始化：首先，函数通过 assert 来检查传入的栈指针ps是否非空，以确认该栈存在。这保证了不会对一个不存在的栈进行操作。

栈非空：接着，函数通过另一个 assert 来确认栈顶指针ps->top大于 0，即栈非空。如果栈为空，那么执行出栈操作没有意义，因此代码会在这里停止执行并输出错误信息。

出栈：如果栈非空，那么代码将栈顶指针ps->top自减 1，表示栈顶的元素已经出栈。

// 出栈 
void StackPop(Stack* ps)
{
  assert(ps);
  //栈不为空
  assert(ps->top > 0);
  ps->top--;
}

💥【4】获取栈顶元素

初始化：首先，函数通过assert来检查传入的栈指针ps是否非空，以确认该栈存在。这保证了不会对一个不存在的栈进行操作。

栈非空：接着，函数通过另一个assert来确认栈顶指针ps->top大于0，即栈非空。如果栈为空，那么获取栈顶元素的操作没有意义，因此代码会在这里停止执行并输出错误信息。

获取栈顶元素：如果栈非空，那么代码将返回栈顶元素，即ps->a[ps->top - 1]。这里之所以使用ps->top - 1，是因为在C/C++中，数组的索引是从0开始的，而栈顶元素实际上是位于栈顶指针所指示的位置的前一个位置。

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
  assert(ps);
  //栈不为空
  assert(ps->top > 0);
  return ps->a[ps->top - 1];
}

💥【5】获取栈中有效元素个数

// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
  assert(ps);
  return ps->top;
}

💥【6】判空

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
  assert(ps);
  /*if (ps->top == 0)
    return 1;
  return 0;*/
  return ps->top == 0;
}

💥【7】销毁栈

// 销毁栈 
void StackDestroy(Stack* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}

🐳二、队列

💨2.1 队列的概念及结构

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

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

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

💨2.2 队列的创建

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，需要将后面的元素向前移动，时间复杂度为 O(1) 效率会比较低。

✨<1>队列的结构

// 链式结构：表示队列 
typedef int QDataType; //元素类型
//队列的节点
typedef struct QListNode
{
  QDataType data;
  struct QListNode* next;
}QNode; 
// 队列的结构 
typedef struct Queue
{
  QNode* front; //对头
  QNode* rear; //队尾
  int size; //队列元素个数
}Queue;

✨<2>队列的接口

// 初始化队列 
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);

💨2.3 队列的实现

💥【1】初始化队列

通过断言检查输入的有效性，然后初始化队列的front、rear和size属性，为后续队列操作做好准备。

// 初始化队列 
void QueueInit(Queue* q)
{
  assert(q);
  q->front = q->rear = NULL;
  q->size = 0;
}

💥【2】队尾入队

创建一个新的节点，并将其添加到队列的尾部。如果队列为空，新节点会同时成为队列的前端和后端；如果队列不为空，新节点会添加到队列的后端，并更新队列的后端为新节点。

断言：通过assert语句检查输入的队列指针是否非空。如果队列指针为空，则程序会在此处停止并输出错误信息。

动态分配内存：创建一个新的节点newnode，并为其分配内存空间。使用malloc函数实现动态内存分配。如果分配失败（即malloc返回NULL），则输出错误信息并结束函数。

设置新节点数据：设置新节点的数据为输入的data，并将新节点的下一个节点设置为NULL。

插入新节点：如果队列为空（即队列的前端q->front和队列的后端q->rear都为NULL），那么将新节点设置为队列的前端和后端。如果队列不为空，那么将新节点添加到队列的后端，并更新队列的后端为新节点。

更新队列大小：每添加一个新节点，队列的大小增加1，因此增加队列的size属性。

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
  assert(q);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc");
    return;
  }
  newnode->data = data;
  newnode->next = NULL;
  if (q->front == NULL)
  {
    q->front = q->rear = newnode;
  }
  else
  {
    q->rear->next = newnode;
    q->rear = newnode;
  }
  q->size++;//队列元素加一
}

💥【3】队头出队

删除队列的队头元素，并更新队列的队头和队尾。同时，需要注意处理队列为空的情况，以防止产生野指针。

断言：通过assert语句检查输入的队列指针是否非空，以及队列是否非空。如果队列指针为空或队列为空，则程序会在此处停止并输出错误信息。

获取队头节点：保存当前队列的队头节点cur。

更新队头：将队列的队头更新为下一个节点。如果队列变为空（即队列的队头和队尾都为NULL），那么将队尾也设置为NULL。

释放内存：由于已经删除了队头节点，需要使用free函数释放该节点的内存空间。

更新队列大小：每删除一个元素，队列的大小减1。

// 队头出队列 
void QueuePop(Queue* q)
{
  assert(q);
  //队列不为空
  assert(q->front);
  QNode* cur = q->front;
  q->front = q->front->next;
  //队列只有一个元素的情况，要考虑队尾的指针，防止野指针
  if (q->front == NULL)
    q->rear = NULL;
  free(cur);
  q->size--;//队列元素减一
}

💥【4】取队头元素

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
  assert(q);
  //队列不为空
  assert(q->front);
  return q->front->data;
}

💥【5】取队尾元素

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
  assert(q);
  //队列不为空
  assert(q->front);
  return q->rear->data;
}

💥【6】获取队列中有效元素个数

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
  assert(q);
  return q->size;
}

💥【7】判空

通过比较队列的队头指针q->front是否等于NULL来判断队列是否为空。如果队列为空（即队列的前端和后端都为NULL），则返回非零结果（这里可能是一个表示“真”的值，例如1）。如果队列非空，则返回0。

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
  assert(q);
  return q->front == NULL;
}

💥【8】销毁队列

遍历队列中的所有节点并逐个释放其内存空间，然后重置队列的属性以使其成为一个空队列。

断言：通过assert语句检查输入的队列指针是否非空。如果队列指针为空，则程序会在此处停止并输出错误信息。

遍历队列：通过一个循环遍历队列中的所有节点。循环继续进行，直到当前节点cur为空。 * 获取当前节点：使用队列的前端指针q->front来获取当前节点cur。 * 释放内存：使用free函数释放当前节点cur的内存空间。 * 移动指针：将当前节点cur的指针更新为下一个节点。

重置队列属性：将队列的前端指针q->front和后端指针q->rear重置为NULL，并将队列的大小属性q->size重置为0。

// 销毁队列 
void QueueDestroy(Queue* q)
{
  assert(q);
  QNode* cur = q->front;
  while (cur)//当cur为空时结束
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  q->front = q->rear = NULL;
  q->size = 0;
}

🐳三、源码

💨3.1 栈

//Stack.h文件
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
//typedef int STDataType;
//#define N 10
//typedef struct Stack
//{
//  STDataType _a[N];
//  int _top; // 栈顶
//}Stack;
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;    // 栈顶
  int capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);
//Stack.c文件
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
// 初始化栈 
void StackInit(Stack* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;//top指向栈顶元素的下一个
  // 表示top指向栈顶元素
  //pst->top = -1;
}
// 入栈 
void StackPush(Stack* ps, STDataType data)
{
  assert(ps);
  if (ps->capacity == ps->top)
  {
    int newcapacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;
    STDataType* temp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
    if (temp == NULL)
    {
      perror("realloc fail");
      return;
    }
    ps->a = temp;
    ps->capacity = newcapacity;
  }
  ps->a[ps->top] = data;
  ps->top++;
}
// 出栈 
void StackPop(Stack* ps)
{
  assert(ps);
  //栈不为空
  assert(ps->top > 0);
  ps->top--;
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
  assert(ps);
  //栈不为空
  assert(ps->top > 0);
  return ps->a[ps->top - 1];
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
  assert(ps);
  return ps->top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
  assert(ps);
  /*if (ps->top == 0)
    return 1;
  return 0;*/
  return ps->top == 0;
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
//Test.c文件
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
void Test()
{
  Stack s;
  StackInit(&s);
  StackPush(&s, 1);
  StackPush(&s, 2);
  StackPush(&s, 3);
  printf("%d ", StackTop(&s));
  StackPop(&s);
  printf("%d ", StackTop(&s));
  StackPop(&s);
  StackPush(&s, 4);
  StackPush(&s, 5);
  //    一     对     多
  // 入栈顺序  --  出栈顺序
  while (!StackEmpty(&s))
  {
    printf("%d ", StackTop(&s));
    StackPop(&s);
  }
  printf("\n");
}
int main()
{
  Test();
  return 0;
}

💨3.2 队列

//Queue.h文件
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
// 链式结构：表示队列 
typedef int QDataType; //元素类型
//队列的节点
typedef struct QListNode
{
  QDataType data;
  struct QListNode* next;
}QNode;
// 队列的结构 
typedef struct Queue
{
  QNode* front; //对头
  QNode* rear; //队尾
  int size; //队列元素个数
}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);
//Queue.c文件
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
// 初始化队列 
void QueueInit(Queue* q)
{
  assert(q);
  q->front = q->rear = NULL;
  q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
  assert(q);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc");
    return;
  }
  newnode->data = data;
  newnode->next = NULL;
  if (q->front == NULL)
  {
    q->front = q->rear = newnode;
  }
  else
  {
    q->rear->next = newnode;
    q->rear = newnode;
  }
  q->size++;//队列元素加一
}
// 队头出队列 
void QueuePop(Queue* q)
{
  assert(q);
  //队列不为空
  assert(q->front);
  QNode* cur = q->front;
  q->front = q->front->next;
  //队列只有一个元素的情况，要考虑队尾的指针，防止野指针
  if (q->front == NULL)
    q->rear = NULL;
  free(cur);
  q->size--;//队列元素减一
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
  assert(q);
  //队列不为空
  assert(q->front);
  return q->front->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
  assert(q);
  //队列不为空
  assert(q->front);
  return q->rear->data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
  assert(q);
  return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
  assert(q);
  return q->front == NULL;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
  assert(q);
  QNode* cur = q->front;
  while (cur)//当cur为空时结束
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  q->front = q->rear = NULL;
  q->size = 0;
}
//Test.c文件
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void Test()
{
  Queue q;
  QueueInit(&q);
  QueuePush(&q, 1);
  QueuePush(&q, 2);
  QueuePush(&q, 3);
  printf("%d ", QueueFront(&q));
  QueuePop(&q);
  printf("%d ", QueueFront(&q));
  QueuePop(&q);
  QueuePush(&q, 4);
  QueuePush(&q, 5);
  while (!QueueEmpty(&q))
  {
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }
  QueueDestroy(&q);
}
int main()
{
  Test();
  return 0;
}

深入理解栈与队列：从基本概念到高级实现

🐳一、栈

💨1.1 栈的概念及结构

💨1.2 栈的创建

✨<1> 栈的存储结构

✨<2> 栈的接口

💨1.3 栈的实现

💥【1】初始化栈

💥【2】进栈

💥【3】出栈

💥【4】获取栈顶元素

💥【5】获取栈中有效元素个数

💥【6】判空

💥【7】销毁栈

🐳二、队列

💨2.1 队列的概念及结构

💨2.2 队列的创建

✨<1>队列的结构

✨<2>队列的接口

💨2.3 队列的实现

💥【1】初始化队列

💥【2】队尾入队

💥【3】队头出队

💥【4】取队头元素

💥【5】取队尾元素

💥【6】获取队列中有效元素个数

💥【7】判空

💥【8】销毁队列

🐳三、源码

💨3.1 栈

💨3.2 队列

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

深入理解栈与队列：从基本概念到高级实现

🐳一、栈

💨1.1 栈的概念及结构

💨1.2 栈的创建

✨<1> 栈的存储结构

✨<2> 栈的接口

💨1.3 栈的实现

💥【1】初始化栈

💥【2】进栈

💥【3】出栈

💥【4】获取栈顶元素

💥【5】获取栈中有效元素个数

💥【6】判空

💥【7】销毁栈

🐳二、队列

💨2.1 队列的概念及结构

💨2.2 队列的创建

✨<1>队列的结构

✨<2>队列的接口

💨2.3 队列的实现

💥【1】初始化队列

💥【2】队尾入队

💥【3】队头出队

💥【4】取队头元素

💥【5】取队尾元素

💥【6】获取队列中有效元素个数

💥【7】判空

💥【8】销毁队列

🐳三、源码

💨3.1 栈

💨3.2 队列

热门文章

最新文章

相关课程

相关电子书