C语言实现栈和队列【数据结构/初阶】

简介: C语言实现栈和队列【数据结构/初阶】

1. 栈

1.1 概念

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

压栈:栈的插入操作称作进栈/压栈/入栈,

出栈:栈的删除操作称作出栈。

压栈和出栈都在栈顶。

1.2 结构

例如:进栈顺序为1、2、3、4,那么(在进栈时无出栈)出栈时的顺序为4、3、2、1

1.3 栈的实现

栈可以用数组和链表实现。回顾并在此比较两者的优缺点:

  1. 数组可以通过下标随机访问,但插入删除数据需要挪动数据,但在栈中,这个缺点不会体现出来,因为数据出栈只能在栈顶出,不能在中间出栈。相当于在两端插入或删除数据。
  2. 链表虽然插入或删除数据不用挪动数据,但这个优点在栈中也不会体现出来。链表的内存不是连续的,CPU高速缓存命中率较低。而且由于链表的结构相较于数组较复杂,每次增加一个节点都要开辟一次内存,(数组一般一次开辟容量的2倍),对性能消耗也是相对较大的。

栈的实现用数组,因为在栈底插入数据的代价较小。

结构:

1.3.1 结构体和数组元素类型定义

结构体成员包含数组,成员数量计数器top(栈顶),容量计数器capacity

typedef int STDataType;
typedef struct Stack
{
  STDataType* data;//注意是数组形式
  int top;
  int capacity;
};
typedef struct Stack Stack;//这是另一种规范的定义写法

1.3.2 栈的初始化与销毁

起初栈需要有空间存放数组元素,capacity不为零,由于还没有元素放入,top为0,要为数组开辟capacity个以结构为大小的空间

//初始化栈
void StackInit(Stack* pst)
{
  assert(pst);
  pst->data = (STDataType*)malloc(sizeof(STDataType) * 4);
  pst->top = 0;
  pst->capacity = 4;
}

为避免造成内存泄漏的问题,有内存的开辟就一定要有内存的销毁

  • 只要将计数器置零,数组地址置空即可,无需在处理数组中之前存放的元素
//销毁栈
void StackDestroy(Stack* pst)
{
  assert(pst);
  free(pst->data);
  pst->data = NULL;
  pst->top = 0;
  pst->capacity = 0;
}

1.3.3 判断栈是否为空

巧妙地将top == 0的结果作为返回值,为空则返回true,否则返回false

有些编译器不支持C99,所以bool可以先定义一下

typedef int bool;
bool StackEmpty(Stack* pst)
{
  assert(pst);
  return pst->top == 0;//top为0则为真,否则为假
}

1.3.4 压栈

压栈的操作就是对数组的尾插

  • 注意判断元素个数是否达到容量
  • 注意判断达到容量以后开辟内存是否成功
void StackPush(Stack* pst, STDataType x)
{
  assert(pst);
  //判断top是否达到容量,达到则扩容
  if (pst->top == pst->capacity)
  {
    STDataType* tmp = (Stack*)realloc(pst->data, sizeof(STDataType) * pst->capacity * 2);//扩容
    if (tmp == NULL)//增容失败
    {
      printf("realloc failed\n");
      exit(-1);//告诉系统这是异常终止程序
    }
    pst->data = tmp;
    pst->capacity = pst->capacity * 2;//更新容量
  }
  pst->data[pst->top] = x;//压入数据
  pst->top++;
}

1.3.5 出栈

出栈相当于对数组尾删,只需将top往后移一步即可,无需再处理删除的元素

  • 注意判断栈是否为空
//出栈(相当于尾删)
void StackPop(Stack* pst)
{
  assert(pst);
  assert(!StackEmpty(pst));
  pst->top--;
}

1.3.6 获取栈顶元素

由于top是从0开始的,所以top指向的是最新元素的下一个位置,要得到栈顶元素,下标要-1

  • 注意判断栈是否为空
//获取栈顶元素
STDataType StackTop(Stack* pst)
{
  assert(pst);
  assert(!StackEmpty(pst));
  return pst->data[pst->top - 1];//top指向第一个元素的下一位
}

1.3.7 获取栈的元素个数

top就是元素个数计数器,直接返回它即可

//获取栈的元素个数
int StackSize(Stack* pst)
{
  assert(pst);
  return pst->top;//top从0开始,其值等于元素个数
}

1.3.8 打印

遍历打印即可

//打印
void StackPrint(Stack* pst)
{
  assert(pst);
  for (int i = 0; i < pst->top; i++)
  {
    printf("%d ", pst->data[i]);
  }
}

2. 队列

2.1 概念

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的特点

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

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

2.2 结构

2.3 队列的实现

队列的结构决定了它的性质,只能在队尾入,在队头出。所以如果用数组实现队列,就正好体现了它的缺点,每次头删都要重新挪动一次数据。使用链表实现队列能避免这个问题。

使用单向链表实现队列,其实就是对链表的尾增和头删。

结构:

2.3.1 链表和队列结构定义

typedef int QDataType;
//用链表表示队列
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
};
typedef struct QueueNode QNode;
//队列结构
typedef struct Queue
{
  QNode* head;
  QNode* tail;
};

2.3.2 队列的初始化与销毁

初始化时,没有节点,head和tail指向NULL

//初始化
void QueueInit(Queue* pq)
{
  //0个元素,头尾指针置空
  pq->head = NULL;
  pq->tail = NULL;
}

将每个节点销毁,两指针重新指向NULL

void QueueDestroy(Queue* pq)
{
  QNode* cur = pq->head;
  while (cur)//将每个节点都销毁 
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;//迭代
  }
  //头尾指针置空
  pq->head = NULL;
  pq->tail = NULL;
}

2.3.3 判断队列是否为空

思路同栈

如果编译器支持C99,那么可以引用头文件

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

2.3.4 入队

相当于给单链表尾插

  • 注意判断开辟内存是否成功
  • 注意判断链表为空
//入队(尾插)
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  //新增节点
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    printf("malloc  failed\n");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  if (pq->tail == NULL)//没有元素
  {
    pq->head = newnode;
    pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;//链接旧尾和新节点
    pq->tail = newnode;//更新尾
  }
}

2.3.5 出队

相当于给单链表头删

  • 注意判断只有链表为空和只有一个节点的情况
//出队(头删)
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(pq->head);//判断链表为空
  if (pq->head->next == NULL)//只有一个节点
  {
    free(pq->head);
    pq->head = NULL;
    pq->tail = NULL;
  }
  else
  {
    QNode* next = pq->head->next;//保存头的下一个节点
    free(pq->head);
    pq->head = next;
  }
}

2.3.6 获取队头和队尾的元素

思路同栈

//获取队头的元素
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
//获取队尾的元素
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}

2.3.7 获取队列中元素的个数

迭代计数即可

//获取队列中元素的个数
int QueueSize(Queue* pq)
{
  int size = 0;
  QNode* cur = pq->head;
  while (cur)
  {
    size++;
    cur = cur->next;
  }
  return size;
}

*3. 循环队列

循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

来源:力扣(LeetCode)

循环队列用数组和链表皆可实现。但实现过程需要注意以下问题。

下面将循环队列形象地用环形表示:

head和tail起始都指向第一个元素,tail随着新元素的增加而往下走,直到元素个数达到队列容量。

问题在于:队列全空和队列全满的条件是相同的:head和tail指向同一个位置。

如何解决?

将一个位置空出来,不存储有效数据。

这样就能区分满和空两种情况了。

  • 队列全满:tail的下一个是head
  • 队列全空:tail和head相等(包括删除的情况)

3.1 设计循环队列

)]

思路:下面通过数组实现循环队列。思路同上,只不过在下标的处理、条件判断有所不同

3.1.1 队列结构的声明

typedef struct {
    int* a;//数组
    int k;//队列容量
    int head;
    int tail;
} MyCircularQueue;

3.1.2 队列初始化与销毁

要为队列和队列中的数组开辟空间,注意数组开辟的空间要比给定的k多一个。

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int) * (k+1));//要空出一个
    obj->k = k;
    obj->head = 0;
    obj->tail = 0;
    return obj;
}

销毁内存只需free掉之前开辟的内存即可,注意顺序

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);//注意顺序
    free(obj);
}

3.1.3 判断队列是否为空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head == obj->tail;
}

3.1.4 判断队列是否已满

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    int tailNext = obj->tail+1;
    if(tailNext == obj->k+1)
    {
        tailNext = 0;
    }
    return obj->head == tailNext;
}

细节处理:对下标的模处理可以转换为让它重新指向第一个元素的位置。

CPU中只有加法器,直接将它移到数组首端比模运算效率更高。

3.1.5 入队

  • 注意判断队列是否已满
  • 注意判断tail是否已经指向了最后一个空出来的位置
  • 注意计数器的迭代
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))//满了
    {
        return false;
    }
    else
    {
        obj->a[obj->tail] = value;
        obj->tail++;
        if(obj->tail == obj->k+1)
        {
            obj->tail = 0;
        }
        return true;
    }
}

3.1.6 出队

  • 注意判断队列是否为空
  • 注意判断tail是否已经指向了最后一个空出来的位置
  • 注意计数器的迭代
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))//空了
    {
        return false;
    }
    else
    {
        obj->head++;
        if(obj->head == obj->k+1)//tail已经指向了最后一个空出来的位置
        {
            obj->head = 0;
        }
        return true;
    }
}

3.1.7 取首

  • 注意判断队列是否为空
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        return obj->a[obj->head];
    }
}

3.1.8 取尾

  • 注意判断队列是否为空
  • 注意判断tail是否已经指向了最后一个空出来的位置(最新的元素是否是最后一个第k个)
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        int tailPrev = obj->tail - 1;//取最新的有效数据(tail指向它的下一个位置)
        if(tailPrev == -1)//说明最新的元素在第k个
        {
            tailPrev = obj->k;
        }
        return obj->a[tailPrev];
    }
}

日志

4/22/2022
4/22/2022
//修正了内存开辟部分变量的类型
目录
相关文章
|
3天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
45 9
|
2天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
32 16
|
2天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
27 8
|
1天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
20 4
|
4天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
26 4
|
6天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
24 3
|
5天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
19天前
数据结构(栈与列队)
数据结构(栈与列队)
15 1
|
4天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
17 0
|
20天前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
13 0