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

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

2023-11-14 79
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【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语言数据结构队列
数据结构栈
数据结构队列
C语言队列
青色忘川
目录
相关文章
土木林森
|
24天前
|
算法 数据处理 C语言
C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合，旨在帮助读者掌握这一高效的数据处理方法。
土木林森
37 1
XIAZHI
|
1月前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现，包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题，读者可以深入了解排序算法、数据处理方法和图论基础知识，提升编程能力和算法理解。
XIAZHI
45 4
XIAZHI
|
1月前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法：直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景，如直接插入排序适合小规模或基本有序的数据，快速排序则适用于大规模数据集，具有较高的效率。通过学习这些算法，读者可以加深对数据结构和算法设计的理解，提升解决实际问题的能力。
XIAZHI
43 4
XIAZHI
|
1月前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现，涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大，且在实际应用中极为广泛，有助于提升编程能力和数据结构理解。
XIAZHI
39 4
XIAZHI
|
1月前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现，涵盖二叉树的层次遍历及广度优先搜索（BFS）和深度优先搜索（DFS）的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点；BFS利用队列从源节点逐层遍历图节点，适用于最短路径等问题；DFS通过递归或栈深入图的分支，适合拓扑排序等场景。这些算法是数据结构和算法学习的基础，对提升编程能力和解决实际问题至关重要。
XIAZHI
50 4
XIAZHI
|
1月前
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现，涵盖链表与二叉树操作，包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法，解决了理论与实际应用中的常见问题，有助于提升编程能力和数据结构理解。
XIAZHI
37 4
龙大吉
|
25天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
49 5
土木林森
|
24天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面，旨在通过综合策略提升程序性能，满足实际需求。
土木林森
56 1
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
197 9
那年春天
|
1月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
32 1