AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【C语言数据结构（基础版）】第四站：栈和队列

2023-11-14 76
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【C语言数据结构（基础版）】第四站：栈和队列

一.栈的表示和实现

1.栈的概念及结构

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

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

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

2.栈的实现

从上面我们也可以看出来，栈的实现一般可以使用数组或者链表实现，相对而言，其实数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小

二、栈的实现

1.栈的声明和定义

根据我们上面的分析，我们决定使用顺序表来实现栈。所以它的声明如下

typedef int STDateType;
typedef struct Stack
{
  STDateType* a;
  int top;
  int capacity;
}Stack;

2.栈的初始化

它的声明如下

//栈的初始化
void StackInit(Stack* ps);

它的函数实现也很简单

//栈的初始化
void StackInit(Stack* ps)
{
  assert(ps);
  ps->a = (STDateType*)malloc(4 * sizeof(STDateType));
  if (ps->a == NULL)
  {
    printf("malloc is fail\n");
    exit(-1);
  }
  ps->capacity = 4;
  ps->top = 0;
}

注意这里的top可以为0也可以为-1

这两种其实也是有区别的，

如果top初始化为0的化，那就意味着top指向栈顶元素的下一个

如果top初始化欸-1的话，那么意味着top指向栈顶元素

3.栈的销毁

创建好那么必要要有销毁

销毁的声明为

//栈的销毁
void StackDestory(Stack* ps);

实现为

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

4.入栈

这个也非常简单，函数声明为

//入栈
void StackPush(Stack* ps, STDateType x);

实现为

//入栈
void StackPush(Stack* ps, STDateType x)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    //扩容
    STDateType* tmp = (STDateType*)realloc(ps->a, sizeof(STDateType) * 2 * ps->capacity);
    if (tmp == NULL)
    {
      printf("realloc is fail\n");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity *= 2;
  }
  ps->a[ps->top] = x;
  ps->top++;
}

5.出栈

函数声明为

//出栈
void StackPop(Stack* ps);

函数实现为

//出栈
void StackPop(Stack* ps)
{
  assert(ps);
  //栈为空了，还想要继续删除直接报错
  assert(ps->top > 0);
  ps->top--;
}

6.返回栈顶元素

这是函数声明

//取出栈顶元素
STDateType StackTop(Stack* ps);

这是函数实现

//取出栈顶元素
STDateType StackTop(Stack* ps)
{
  assert(ps);
  //栈为空，还继续调用的话直接报错
  assert(ps->top > 0);
  return ps->a[ps->top - 1];
}

7.返回栈的元素个数

这是函数声明

//栈的元素个数
int StackSize(Stack* ps);

这是函数实现

//栈的元素个数
int StackSize(Stack* ps)
{
  assert(ps);
  return ps->top;
}

8.栈是否为空

这是函数声明

//栈是否为空
bool StackEmpty(Stack* ps);

这是函数实现

//栈是否为空
bool StackEmpty(Stack* ps)
{
  assert(ps);
  return (ps->top == 0);
}

9.测试

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
int main()
{
  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);
  }
  StackDestory(&s);
}

运行结果为

三、栈的完整代码

Test.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
int main()
{
  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);
  }
  StackDestory(&s);
}

Stack.h文件

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<string.h>
#include<stdlib.h>
typedef int STDateType;
typedef struct Stack
{
  STDateType* a;
  int top;
  int capacity;
}Stack;
//栈的初始化
void StackInit(Stack* ps);
//栈的销毁
void StackDestory(Stack* ps);
//入栈
void StackPush(Stack* ps, STDateType x);
//出栈
void StackPop(Stack* ps);
//取出栈顶元素
STDateType StackTop(Stack* ps);
//栈的元素个数
int StackSize(Stack* ps);
//栈是否为空
bool StackEmpty(Stack* ps);

Stack.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//栈的初始化
void StackInit(Stack* ps)
{
  assert(ps);
  ps->a = (STDateType*)malloc(4 * sizeof(STDateType));
  if (ps->a == NULL)
  {
    printf("malloc is fail\n");
    exit(-1);
  }
  ps->capacity = 4;
  ps->top = 0;
}
//栈的销毁
void StackDestory(Stack* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
//入栈
void StackPush(Stack* ps, STDateType x)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    //扩容
    STDateType* tmp = (STDateType*)realloc(ps->a, sizeof(STDateType) * 2 * ps->capacity);
    if (tmp == NULL)
    {
      printf("realloc is fail\n");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity *= 2;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
//出栈
void StackPop(Stack* ps)
{
  assert(ps);
  //栈为空了，还想要继续删除直接报错
  assert(ps->top > 0);
  ps->top--;
}
//取出栈顶元素
STDateType StackTop(Stack* ps)
{
  assert(ps);
  //栈为空，还继续调用的话直接报错
  assert(ps->top > 0);
  return ps->a[ps->top - 1];
}
//栈的元素个数
int StackSize(Stack* ps)
{
  assert(ps);
  return ps->top;
}
//栈是否为空
bool StackEmpty(Stack* ps)
{
  assert(ps);
  return (ps->top == 0);
}

四、队列的表示和实现

1.队列的概念和结构

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

2.队列的实现

队列也可以数组和链表的结构实现，但使用链表的结构更优一些，因为如果使用数组的结构，出队列在数组的头上出数据，效率会比较低.

五、队列的实现

1.队列的声明和定义

我们想要使用链表的结构来实现队列，但是由于单链表的尾插过于麻烦，不妨我们直接声明头节点和尾结点来控制队列

typedef int QDateType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDateType date;
}QNode;
typedef struct Queue
{
  QNode* head;
  QNode* tail;
}Queue;

如上所示，我们先定义了一个队列结点的结构体，里面包含了指向下一个结点的指针和一个队列的数据。然后我们定义了一个队列结构体，我们主要是使用队列这个结构体，它里面有头结点和尾结点，有头有尾刚好确定一个队列。

2.队列的初始化

接下来让我们先来实现一下队列的初始化

函数声明为

//队列初始化
void QueueInit(Queue* pq);

实现为

//队列的初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
}

其实对这个实现，建议与前面的一些LeetCode题目和单链表的实现进行对比，我们可以看出来这里的妙处。

3.队列的销毁

有始有终，我们来实现一下队列的销毁

//队列的销毁
void QueueDestory(Queue* pq);

函数实现为

//队列的销毁
void QueueDestory(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
}

4.队列的插入

函数声明为

//队列的插入
void QueuePush(Queue* pq, QDateType x);

函数实现为

//队列的插入
void QueuePush(Queue* pq, QDateType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    printf("malloc is fail\n");
    exit(-1);
  }
  //对新节点进行初始化
  newnode->date = x;
  newnode->next = NULL;
  //对新结点进行连接
  if (pq->head == NULL)
  {
    //头结点是空的，也就是第一个数据的插入
    pq->head = pq->tail = newnode;
  }
  else
  {
    //非第一个数据的插入
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
}

5.队列的删除

函数声明为

//队列的删除
void QueuePop(Queue* pq);

函数实现为

//队列的删除
void QueuePop(Queue* pq)
{
  assert(pq);
  //确保队列不是空的队列
  assert(pq->head);
  //如果只有一个结点，防止tail形成野指针
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  //不是只有一个结点
  else
  {
    //保存第二个队列结点
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
}

6.队列的判空

函数声明

//判断队列是否为空
bool QueueEmpty(Queue* pq);

函数实现

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

7.取出队头的数据

函数声明

//取出队头的数据
QDateType QueueFront(Queue* pq);

函数实现

//取出队头的数据
QDateType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  return pq->head->date;
}

8.取出队尾的数据

函数声明

//取出队尾的数据
QDateType QueueBack(Queue* pq);

函数实现

//取出队尾的数据
QDateType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  return pq->tail->date;
}

9.队列数据的个数

函数声明

//取出数据的个数
int QueueSize(Queue* pq);

函数实现

//取出数据的个数
int QueueSize(Queue* pq)
{
  assert(pq);
  int size = 0;
  QNode* cur = pq->head;
  while (cur)
  {
    cur = cur->next;
    size++;
  }
  return size;
}

10.测试

void TestQueue()
{
  Queue q;
  QueueInit(&q);
  QueuePush(&q, 1);
  QueuePush(&q, 2);
  QueuePush(&q, 3);
  QueuePush(&q, 4);
  QueuePush(&q, 5);
  while (!QueueEmpty(&q))
  {
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }
  printf("\n");
  QueueDestory(&q);
}
int main()
{
  //TestStack();
  TestQueue();
}

运行结果为

六、队列完整代码

Test.c

void TestQueue()
{
  Queue q;
  QueueInit(&q);
  QueuePush(&q, 1);
  QueuePush(&q, 2);
  QueuePush(&q, 3);
  QueuePush(&q, 4);
  QueuePush(&q, 5);
  while (!QueueEmpty(&q))
  {
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }
  printf("\n");
  QueueDestory(&q);
}
int main()
{
  //TestStack();
  TestQueue();
}

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDateType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDateType date;
}QNode;
typedef struct Queue
{
  QNode* head;
  QNode* tail;
}Queue;
//队列初始化
void QueueInit(Queue* pq);
//队列的销毁
void QueueDestory(Queue* pq);
//队列的插入
void QueuePush(Queue* pq, QDateType x);
//队列的删除
void QueuePop(Queue* pq);
//取出队头的数据
QDateType QueueFront(Queue* pq);
//取出队尾的数据
QDateType QueueBack(Queue* pq);
//取出数据的个数
int QueueSize(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//队列的初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
}
//队列的销毁
void QueueDestory(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
}
//队列的插入
void QueuePush(Queue* pq, QDateType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    printf("malloc is fail\n");
    exit(-1);
  }
  //对新节点进行初始化
  newnode->date = x;
  newnode->next = NULL;
  //对新结点进行连接
  if (pq->head == NULL)
  {
    //头结点是空的，也就是第一个数据的插入
    pq->head = pq->tail = newnode;
  }
  else
  {
    //非第一个数据的插入
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
}
//队列的删除
void QueuePop(Queue* pq)
{
  assert(pq);
  //确保队列不是空的队列
  assert(pq->head);
  //如果只有一个结点，防止tail形成野指针
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  //不是只有一个结点
  else
  {
    //保存第二个队列结点
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
} 
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}
//取出队头的数据
QDateType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  return pq->head->date;
}
//取出队尾的数据
QDateType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  return pq->tail->date;
}
//取出数据的个数
int QueueSize(Queue* pq)
{
  assert(pq);
  int size = 0;
  QNode* cur = pq->head;
  while (cur)
  {
    cur = cur->next;
    size++;
  }
  return size;
}

总结

本节实现了栈和队列的实现，难度不大，希望大家都能学会

如果对你有帮助，不要忘记点赞加收藏哦！！！

想获得更多优质的内容，一定要记得关注我哦！！！

文章标签：
C语言
关键词：
数据结构栈
数据结构c语言
数据结构队列
数据结构栈队列
C语言数据结构
青色忘川
目录
相关文章
ephemerals__
|
16天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
91 9
那年春天
|
7天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
16 1
德国都芳最好
|
10天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
50 21
ephemerals__
|
15天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
58 16
ephemerals__
|
15天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
65 8
html的七十二变
|
13天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
27 2
dufadayang
|
15天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
43 4
白子寰
|
1月前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
白子寰
34 3
Skyund
|
8天前
|
C语言
c语言调用的函数的声明
被调用的函数的声明： 一个函数调用另一个函数需具备的条件: 首先被调用的函数必须是已经存在的函数，即头文件中存在或已经定义过； 如果使用库函数，一般应该在本文件开头用#include命令将调用有关库函数时在所需要用到的信息“包含”到本文件中。.h文件是头文件所用的后缀。 如果使用用户自己定义的函数，而且该函数与使用它的函数在同一个文件中，一般还应该在主调函数中对被调用的函数做声明。 如果被调用的函数定义出现在主调函数之前可以不必声明。 如果已在所有函数定义之前，在函数的外部已做了函数声明，则在各个主调函数中不必多所调用的函数在做声明
Skyund
25 6
ephemerals__
|
28天前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余，其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值，并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出，支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
ephemerals__
35 10

热门文章

最新文章

  • 1
    【数据结构与算法】一篇文章彻底搞懂二分查找（思路图解+代码优化）两种实现方式，递归与非递归
  • 2
    数据结构学习笔记【持续更新】
  • 3
    我花了一夜用数据结构给女朋友写个H5走迷宫游戏
  • 4
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 5
    【数据结构7】查找
  • 6
    算法导论第十四章 数据结构的扩张
  • 7
    学数据结构，只需要基本的编程体验
  • 8
    数据结构（2）：栈的原理和实现
  • 9
    R语言学习笔记（一）数据结构
  • 10
    初学python数据结构-切片
  • 1
    C语言之详细讲解文件操作（抓住文件操作的奥秘）
    47
  • 2
    C语言结构体—自定义类型—struct
    48
  • 3
    C语言—内存函数的实现和模拟实现（内存函数的丝绸之路）
    47
  • 4
    C语言—字符函数与字符串函数（字符问题变简单的关键之技）
    62
  • 5
    C语言之九九乘法表||素数||最小公倍数
    62
  • 6
    C语言详解指针（指针海洋的探索，将传值与传址刻在心里）
    41
  • 7
    C语言——函数递归
    38
  • 8
    C语言扫雷代码（蹦蹦炸弹）（下）
    37
  • 9
    关于我在C语言中玩扫雷（上）
    36
  • 10
    C语言—函数（大化小方式的心脏）
    38

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程
  • Go语言核心编程 - 基础语法、数组、切片、Map
  • 5天玩转Java面向对象编程
  • Java面向对象编程

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云OSS设置跨域访问