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

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

🐳一、栈

💨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】进栈

  1. 初始化:首先,函数通过assert来检查传入的栈指针ps是否非空,以确认该栈存在。如果栈已满(ps->top == ps->capacity),则不执行任何操作。
  2. 扩容:如果栈不满,但接近满载,代码将进行扩容操作。如果栈的当前容量ps->capacity0(即初始状态或刚经历过扩容),新的容量设为 4。否则,新的容量为当前容量的两倍。这样做是为了预先保留足够的空间,避免频繁的扩容操作。
  3. 重新分配内存:使用realloc函数重新分配栈的内存空间。新的内存大小为新的容量乘以数据类型的大小。如果重新分配失败(realloc返回NULL),则输出错误信息并返回。
  4. 数据入栈:将数据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】出栈

  1. 初始化:首先,函数通过 assert 来检查传入的栈指针ps是否非空,以确认该栈存在。这保证了不会对一个不存在的栈进行操作。
  2. 栈非空:接着,函数通过另一个 assert 来确认栈顶指针ps->top大于 0,即栈非空。如果栈为空,那么执行出栈操作没有意义,因此代码会在这里停止执行并输出错误信息。
  3. 出栈:如果栈非空,那么代码将栈顶指针ps->top自减 1,表示栈顶的元素已经出栈。
// 出栈 
void StackPop(Stack* ps)
{
  assert(ps);
  //栈不为空
  assert(ps->top > 0);
  ps->top--;
}

💥【4】获取栈顶元素

  1. 初始化:首先,函数通过assert来检查传入的栈指针ps是否非空,以确认该栈存在。这保证了不会对一个不存在的栈进行操作。
  2. 栈非空:接着,函数通过另一个assert来确认栈顶指针ps->top大于0,即栈非空。如果栈为空,那么获取栈顶元素的操作没有意义,因此代码会在这里停止执行并输出错误信息。
  3. 获取栈顶元素:如果栈非空,那么代码将返回栈顶元素,即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】队尾入队

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

  1. 断言:通过assert语句检查输入的队列指针是否非空。如果队列指针为空,则程序会在此处停止并输出错误信息。
  2. 动态分配内存:创建一个新的节点newnode,并为其分配内存空间。使用malloc函数实现动态内存分配。如果分配失败(即malloc返回NULL),则输出错误信息并结束函数。
  3. 设置新节点数据:设置新节点的数据为输入的data,并将新节点的下一个节点设置为NULL
  4. 插入新节点:如果队列为空(即队列的前端q->front和队列的后端q->rear都为NULL),那么将新节点设置为队列的前端和后端。如果队列不为空,那么将新节点添加到队列的后端,并更新队列的后端为新节点。
  5. 更新队列大小:每添加一个新节点,队列的大小增加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】队头出队

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

  1. 断言:通过assert语句检查输入的队列指针是否非空,以及队列是否非空。如果队列指针为空或队列为空,则程序会在此处停止并输出错误信息。
  2. 获取队头节点:保存当前队列的队头节点cur
  3. 更新队头:将队列的队头更新为下一个节点。如果队列变为空(即队列的队头和队尾都为NULL),那么将队尾也设置为NULL
  4. 释放内存:由于已经删除了队头节点,需要使用free函数释放该节点的内存空间。
  5. 更新队列大小:每删除一个元素,队列的大小减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】销毁队列

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

  1. 断言:通过assert语句检查输入的队列指针是否非空。如果队列指针为空,则程序会在此处停止并输出错误信息。
  2. 遍历队列:通过一个循环遍历队列中的所有节点。循环继续进行,直到当前节点cur为空。 * 获取当前节点:使用队列的前端指针q->front来获取当前节点cur。 * 释放内存:使用free函数释放当前节点cur的内存空间。 * 移动指针:将当前节点cur的指针更新为下一个节点。
  3. 重置队列属性:将队列的前端指针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;
}

目录
相关文章
|
4天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
|
4天前
|
前端开发
07_用队列实现栈
07_用队列实现栈
06_用栈来求解汉诺塔问题
06_用栈来求解汉诺塔问题
05_用一个栈实现另一个栈的排序
05_用一个栈实现另一个栈的排序
03_如何仅用递归函数和栈操作逆序一个栈
03_如何仅用递归函数和栈操作逆序一个栈
|
4天前
|
测试技术
02_由两个栈组成的队列
02_由两个栈组成的队列
01_设计一个有getMin功能的栈
01_设计一个有getMin功能的栈
|
8天前
|
存储
|
23天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配,利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题,要求判断输入字符串中的括号是否正确匹配,并给出了完整的代码示例。此外,还探讨了栈在表达式求值中的应用,包括中缀、后缀和前缀表达式的转换与计算方法。最后,文章介绍了矩阵的压缩存储技术,涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略,提高存储效率。
|
25天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表,常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈,顺序栈使用数组存储,链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛,如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成,链栈则基于单链表的头插法实现。
150 3
下一篇
无影云桌面