【数据结构】C语言实现:栈(Stack)与队列(Queue)

简介: 【数据结构】C语言实现:栈(Stack)与队列(Queue)

栈的概念及其结构

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。 栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。所以也有被称为后进先出的顺序结构。


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

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


栈的顺序结构(杯子)

c7c1e76cfc193bcb7901ba8acda75807_07452c28c2234da58eade9e427d0a024.png


~~就像上述图片一样,像个”杯子“,只能从上面进出,后进先出;栈底是固定的,无法插入于删除。


栈的相关接口

我们来到cplusplus这个网站,查找库中的栈的接口。(这里我们只讲解C语言的哈,C++涉及的emplace和swap就暂不讲解)

f4cfbeb05c985ac7daff4c366f470b08_1386e45145804ebb8bd35d944a255841.png


栈的实现

栈,我们可以用顺序表实现,也可以用链表实现,各有各的优势,接下来我们就具体用C语言代码来实现下顺序栈和链栈。


顺序栈

顺序栈,也就是用顺序表来实现,顺序表也就是用了数组这一结构。动态内存管理,开辟一个空间大小固定的数组(当然可以扩容)。这一结构地址相连,方便访问。接下来我们先定义一个栈。


定义栈结构:

定义栈分为三部分:动态开辟数组(a)、top下标、容量(capacity)

typedef int STDataType;
//栈的定义
typedef struct Stack
{
  STDataType* a;
  int top;
  int capacity;
}S;
头文件 (Stack.h)

我们进行一个简单的分装,把库头文件、接口函数声明、结构体定义封装到头文件中。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义初始空间大小
#define A_INIT 2
//定义栈元素类型:这里是为了我们的栈更兼容其他类型元素,比如我们现在想变为存储double的栈,只需要在这里把int改成double就可以。
typedef int STDataType;
//栈的定义
typedef struct Stack
{
  STDataType* a;
  int top;
  int capacity;
}S;
//初始化栈
void StackInit(S* stack);
//栈的销毁
void StackDestroy(S* stack);
//压栈
void StackPush(S* stack, STDataType x);
//出栈
void StackPop(S* stack);
//读取栈顶元素
STDataType StackTop(S* stack);
//判断是否空栈
bool StackEmpty(S* stack);
//栈的元素个数
int StackSize(S* stack);
初始化 (StackInit)

初始化:我们根据栈结构来初始化,所以也分为三部分:

1.对a,进行空间开辟,用malloc来开辟空间。

2.容量(便于后续扩容操作)

3.top下标。这里我们有两种主流的:初始化为0或者初始化为-1.

(ps:初始化为0,则表示top指向的是栈顶上一个元素,我们访问的时候就需要-1;初始化为-1,则表示top指针指向栈顶元素,直接访问即可。这里我便是采用初始化为-1)

void StackInit(S* stack)
{
  assert(stack);//断言
  stack->a = (STDataType*)malloc(sizeof(STDataType) * A_INIT);
  stack->capacity = A_INIT;
  stack->top = -1;
}
销毁 (StackDestroy)

同上,根据定义来,malloc的动态空间,调用free()函数来释放空间,以防内存泄漏。

void StackDestroy(S* stack)
{
  free(stack->a);
  stack->a = NULL;
  stack->capacity = 0;
  stack->top = -1;
}
压栈 (StackPush)
  • 压栈:只需要把top指针上移,赋值新插入元素即可,也就是对应最后两段代码。
  • ps:但我们插入要考虑我们开辟的容量问题,当容量空间不够我们需要扩容操作。
  • 扩容:调用realloc函数进行空间的扩容。这里也有两个问题:原地扩容和异地扩容,这个详细我们在realloc函数那篇解释。这里影响并不是很大。
void StackPush(S* stack, STDataType x)
{
  //扩容
  assert(stack);
  if (stack->top + 1 == stack->capacity)
  {
    STDataType* tmp = (STDataType*)realloc(stack->a, sizeof(STDataType) * 2 * stack->capacity);
    if (tmp == NULL)//判断是否扩容成功
    {
      perror("realloc error");
      return;
    }
    stack->a = tmp;
    stack->capacity = 2 * stack->capacity;
  }
  stack->top++;
  stack->a[stack->top] = x;
}
出栈(StackPop)

出栈就十分简单,先判断是否为空栈,若不是,只需要收回栈顶访问权,让栈顶指针指向下一个位置。

void StackPop(S* stack)
{
  assert(stack);
  assert(stack->top != -1);

  stack->top--;
}
读取栈顶元素 (StackTop)

这里值得注意的是top的初始化是0还是-1问题。

STDataType StackTop(S* stack)
{
  assert(stack);
  assert(stack->top + 1 != 0);

  return stack->a[stack->top];
}
判断空栈(StackEmpty)

判断栈顶top是否为默认初始值即可。

bool StackEmpty(S* stack)
{
  assert(stack);

  return stack->top == -1;
}
栈元素个数(StackSize)

这里也是需要注意top初始值问题。

int StackSize(S* stack)
{
  assert(stack);
  return stack->top+1;
}

队列

队列的概念及结构

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)像个管道只允许一个数据通过,所以不能插队,先进先出。

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

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

队列的实现

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

队列的相关接口

我们同样登录cplusplus网站去看下Queue的接口。

队列的实现

队列的定义:

队列的定义我们采用链表来定义,这里队列整体存在两个指针,和前面的双向循环的链表一样,我们最好把两个外部指针封装一下。

1.队列单独结点的定义有值和next指针。

2.队列整体的话有两个指向队列单独结点的head和tail指针,为了方便我这边也定义了size来定义队列结点个数。

typedef int Datatype;
//定义队列
typedef struct Queue
{
  struct Queue* next; 
  Datatype data;
}qnode;

typedef struct
{
  qnode* head;
  qnode* tail;
  int size;
}queue;

头文件(Queue.h)
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int Datatype;
//定义队列
typedef struct Queue
{
  struct Queue* next; 
  Datatype data;
}qnode;

typedef struct
{
  qnode* head;
  qnode* tail;
  int size;
}queue;

void QueueInit(queue* pq);
void QueueDestroy(queue* pa);
void QueuePush(queue* pq, Datatype x);
void QueuePop(queue* pq);
bool QueueEmpty(queue* pq);
int QueueSize(queue* pq);
Datatype QueueFront(queue* pq);
Datatype QueueBack(queue* pq);

初始化(QueueInit)

队列的初始化,因为没有结点,直接初始化外部指针即可。

void QueueInit(queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}
销毁(QueueDestroy)

遍历指针,在释放即可。

void QueueDestroy(queue* pq)
{
  assert(pq);
  qnode* cur = pq->head;
  while (cur)
  {
    qnode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = NULL;
  pq->tail = NULL;
}
入队列(QueuePush)

入队列先进先出,单道通行。

1.首先是申请结点空间,然后赋值。

2.如果是队列为空,直接给head和tail指针赋值新节点地址;如果不为空,就赋值给tail的next指针。接在后方。

3.最后size计数,加加即可。

void QueuePush(queue* pq, Datatype x)
{
  qnode* node = (qnode*)malloc(sizeof(qnode));
  if (node == NULL)
  {
    perror("malloc error!");
    return;
  }
  node->next = NULL;
  node->data = x;

  if (pq->head == NULL)
  {
    pq->head = pq->tail = node;
  }
  else
  {
    pq->tail->next = node;
    pq->tail = node;
  }
  pq->size++;
}
出队列(QueuePop)

出队列先入先出

1.注意断言队列是否为空。

2.若队列只有一个结点,直接释放,双指针置空即可;若队列不止一个结点,保存head的next指针,释放head指针,在head指针赋值新的head位置。

3.最后size减减即可。

void QueuePop(queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));

  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;
  }
  pq->size--;
}
判断队列是否为空(QueueEmpty)
bool QueueEmpty(queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}
返回队列的结点个数(QueueSize)

这里直接返回size即可,若前方定义没有加size,就需要遍历计数返回。

int QueueSize(queue* pq)
{
  assert(pq);
  return pq->size;
}
队列首结点(QueueFront)
Datatype QueueFront(queue* pq)
{
  assert(pq);
  return pq->head->data;
}
队列尾结点(QueueBack)
Datatype QueueBack(queue* pq)
{
  assert(pq);
  return pq->tail->data;
}


相关文章
|
22天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
34 1
|
1月前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
45 4
|
1月前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
43 4
|
1月前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现,涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大,且在实际应用中极为广泛,有助于提升编程能力和数据结构理解。
39 4
|
1月前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现,涵盖二叉树的层次遍历及广度优先搜索(BFS)和深度优先搜索(DFS)的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点;BFS利用队列从源节点逐层遍历图节点,适用于最短路径等问题;DFS通过递归或栈深入图的分支,适合拓扑排序等场景。这些算法是数据结构和算法学习的基础,对提升编程能力和解决实际问题至关重要。
48 4
|
1月前
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现,涵盖链表与二叉树操作,包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法,解决了理论与实际应用中的常见问题,有助于提升编程能力和数据结构理解。
37 4
|
24天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
44 5
|
22天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
54 1
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
187 9
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
32 1