初阶数据结构之---栈和队列(C语言)

简介: 初阶数据结构之---栈和队列(C语言)

引言

在顺序表和链表那篇博客中提到过,栈和队列也属于线性表

线性表:

线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。线性表在逻辑上是线性结构,也就是说是连续的一条直线。但在物理上并不一定是连续的。线性表在物理上存储时,通常以数组链式结构的形式存储。

但栈和队列相比于之前学的顺序表和链表,就简单的多了。

现在我们就来看看数据结构中的队列到底是什么,以及用C语言的模拟实现吧!

概念及结构

栈的概念

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

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

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

在上图中,左边两图是压栈(push)的过程;右边两图是出栈(pop)的过程

以上就是栈的概念及逻辑,下面我们就可以来看看栈的实现了

栈的具体结构

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小,其缓存命中率也高。

下面是数组实现栈的结构

capacity是容量,指向所开空间最后一位的下一位;top是有效元素个数,指向有效数字的下一位

下面是链表实现栈的结构

由于数组实现栈相比于链表实现更有优势,这里我们用数组手搓一个栈

手搓一个栈(栈的实现)

这里的栈的空间也需要动态开辟(需要时动态扩容),故数组的内存是开辟在堆中的。

先放上需要实现的接口,头文件Stack.h

//Stack.h
// 下面是定长的静态栈的结构,实际中一般不实用
// 所以我们主要实现后面的支持动态增长的栈
// typedef int STDataType;
// #define N 10
// typedef struct Stack
// {
//  STDataType _a[N];
//  int _top; // 栈顶
// }Stack;
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct stack
{
  STDataType* a;
  int top;  //栈顶
  int capacity; //容量
}ST;
//初始化栈
void STInit(ST* ps);
//销毁栈
void STDestory(ST* ps);
//入栈(压栈)
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool STEmpty(ST* ps);

此时我们可以开始实现头文件接口中的内容了

初始化和销毁栈

感觉没什么好说的,注意下销毁的free就行

//初始化栈
void STInit(ST* ps) 
{
  assert(ps);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}
//销毁栈
void STDestory(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}

入栈(压栈)和出栈

注意在空间不够的时候要动态开辟空间realloc,这里入空间开辟后返回的指针先用tmp接收是为了防止开辟失败时找不到原来的内存空间,当开辟成功后再将新开辟的地址赋给ps->a,realloc同时也会自动释放过去的空间。

//入栈
void STPush(ST* ps, STDataType x)
{
  assert(ps);
  if (ps->top == ps->capacity) {
    int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//这里是三目操作符
        //下面别忘乘sizeof(STDataType)
    STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity*sizeof(STDataType));
    if (tmp == NULL) {
      perror("realloc tmp fail:");
      exit(1);
    }
    ps->a = tmp;
    ps->capacity = newcapacity;
  }
  ps->a[ps->top] = x;
  ++ps->top;//入栈后最大元素数加一
}
//出栈
void STPop(ST* ps)
{
  assert(ps);
    //出栈时要保证栈中有元素
  assert(!STEmpty(ps));
  ps->top--;
}

获取栈顶元素

栈顶元素其实就是top前一位,这里注意栈为空时不能获取到元素

//获取栈顶元素
STDataType STTop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));
  return ps->a[ps->top - 1];
}

获取栈中有效元素个数和检测栈是否为空

这里也是根据栈的top去判断就行

//获取栈中有效元素个数
int STSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
//检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
bool STEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}

体验一下栈

//测试栈的代码
#include"Stack.h"
int main()
{
  struct stack st;
  STInit(&st);
  STPush(&st, 1);
  STPush(&st, 2);
  STPush(&st, 3);
  STPush(&st, 4);
  while (!STEmpty(&st)) {
    printf("%d ", STTop(&st));
    STPop(&st);
  }
  printf("\n");
  STDestory(&st);
  return 0;
}

怎么说呢,栈就这么点内容,再多的没有,简单的结构应该大家都能理解,如果有疑问的朋友也欢迎再评论区提出,我也会尽我所能去提供帮助。

队列

队列的概念及结构

队列的概念

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出。FIFO(First In First Out)

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

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

队列的具体结构

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

所以这里我们讲队列链表结构的具体实现

下面是对队列维护的具体结构

下面是关于队列从队头出元素,队尾进元素的过程。

手搓一个队列(队列的实现)

先放上要实现的接口,我放在头文件Queue.h中

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
// 链式结构:表示队列 
typedef int QDataType;
//队列的一个结点
typedef struct QListNode
{
  struct QListNode* _next;
  QDataType _data;
}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);

初始化队列

这个没什么可说的,将维护队列的指针初始化制空,size置零

// 初始化队列 
void QueueInit(Queue* q)
{
  assert(q);
  q->_front = NULL;
  q->_rear = NULL;
  q->size = 0;
}

队尾入队列

之前在实现链表的时候专门写了一个CreateNode函数,是因为当时在链表头尾中间各处插入时都需要用到。但是队列这里不同,只有入队列这一处用到了CreateNode,我们就大可不必再写这个函数,直接写在这个Push函数里就行。

在新结点开辟出来后,需要分两种情况讨论

  1. 队列中无结点(_front 和 _rear 都为空):这种情况需要同时对_front和_rear做出调整
  2. 队列中有结点:这时直接将新节点链接到 _rear 尾结点之后,同时新节点成为尾结点
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
  assert(q);
    //需要新结点,直接创建
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL) {
    perror("malloc fail:");
    exit(1);
  }
  newnode->_data = data;
  newnode->_next = NULL;
  if (q->_front == NULL) {
    q->_front = newnode;
    q->_rear = newnode;
  }
  else {
    q->_rear->_next = newnode;
    q->_rear = newnode;
  }
  q->size++;
}

队头出队列

这里注意_front和_rear两个指针

这里需要分三种情况讨论:

  1. 队列为空:无法执行pop,assert断言
  2. 队列只有一个结点:释放节点同时将队列置空
  3. 队列中有多个结点:将队头指针释放,_front指向下一个结点(这里稍微注意下释放顺序,不要出现释放之后还去访问结点next的情况)
// 队头出队列 
void QueuePop(Queue* q)
{
  assert(q);
  assert(q->_front);
  if (q->size == 1) {
        //如果只有一个结点,直接释放
    free(q->_front);
    q->_front = q->_rear = NULL;
  }
  else {
    QNode* pnext = q->_front->_next;
    free(q->_front);
    q->_front = pnext;
  }
  q->size--;
}

获取队列头部元素和获取队列尾部元素

这里直接应用_front和_rear指针就可以

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
  assert(q);
  assert(q->_front);
  return q->_front->_data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
  assert(q);
  assert(q->_rear);
  return q->_rear->_data;
}

获取队列有效元素个数和检测队列是否为空

获取队列有效元素可以直接运用上我们的size,size的大小即为有效元素个数,size为0时队列为空

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
  assert(q);
  return q->size;
}
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q)
{
  assert(q);
  return q->size == 0;
}

销毁队列

这里稍微复杂一些,需要分三种情况讨论:

  1. 队列中无元素:直接返回,不用释放了
  2. 队列中有一个元素:释放一次并置空指针,size置零
  3. 队列中有多个元素:对照链表的销毁方式销毁,最后置空指针,size置零
// 销毁队列 
void QueueDestroy(Queue* q)
{
  assert(q);
  if (q->_front == NULL)return;
  if (q->size == 1) {
    free(q->_front);
  }
  else {
    while (q->_front) {
      QNode* pnext = q->_front->_next;
      free(q->_front);
      q->_front = pnext;
    }
  }
  q->_front = q->_rear = NULL;
  q->size = 0;
}

体验一下手搓的队列

#include"Queue.h"
int main()
{
  Queue q;
  QueueInit(&q);
  QueuePush(&q, 1);
  QueuePush(&q, 3);
  QueuePush(&q, 5);
  QueuePush(&q, 7);
  QueuePush(&q, 9);
  while (!QueueEmpty(&q)) {
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }
  printf("\n");
  QueueDestroy(&q);
  return 0;
}

队列拓展之设计循环队列

实际中我们有时还会使用一种队列,叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。

循环队列的存储数据量有一个上限,即容量一定,其逻辑结构图大概是这样的:

循环队列可以使用数组实现,也可以使用循环链表实现:

我们将最后一个有效元素的下一位设计为尾,当front和tail相等的时候,就是队列为空的时候。

就链表实现的循环队列来说,相对比较复杂:如果你把有效数字的下一位当作尾,你将无法直接访问到链表尾元素;如果你把尾元素当作有效数字末尾,还得去区分队列只有一个元素和没有元素的情况,以及tail和front重合时是队列是满的还是空的。同时链表实现的队列还无法直接算出有效数字个数,虽然这时你也许可以存一个size专门来记录有效数字个数。

或许在你给链表设计一大堆解决方案之前,可以来看看用顺序结构来设计环形链表,你会发现,之前的一系列问题在顺序结构面前已经不复存在。

你可以通过下标直接访问到有效数字的上一位和下一位,你可以通过tail和front的相对位置直接计算出有效数字个数,你更可以单凭front和tail的相对位置来判断环形队列此时是满的还是空的。

如果大家已经有思路想法,可以先来看看这道题:622. 设计循环队列 - 力扣(LeetCode)

那么,我们接下来看看用顺序表设计循环队列的方案吧

对于循环队列的结构设计

上图中注意专门预留空间解决假溢出问题,当(rear + 1)%(k + 1) == front 时,队列为满;当rear == front 时,队列为空。这里(rear + 1)%(k + 1)是对下标的一种处理方式,使其逻辑结构为一个环,下标数字范围在(0 ~ k)。

下面我们来实现循环队列的一些功能函数

循环队列初始化

注意在malloc的时候多开了1的空间预留,开始将front和rear都置零,obj中的k置为n,这里的n指的是要开环形队列能容纳有效元素的大小

//MyCircularQueue(k): 构造器,设置队列长度为 k
MyCircularQueue* myCircularQueueCreate(int n) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int) * (n + 1));
    if (obj->a == NULL) {
        perror("malloc fail:");
        exit(1);
    }
    obj->front = 0;
    obj->rear = 0;
    obj->k = n;
    return obj;
}

检查循环队列是否为空和是否为满

当(rear + 1)%(k + 1) == front 时,队列为满;当rear == front 时,队列为空

//isEmpty(): 检查循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}
//isFull(): 检查循环队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear + 1) % (obj->k + 1) == obj->front;
}

循环队列尾插入数据

如果队列已满则返回false,插入失败

//enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))return false;
    obj->a[obj->rear] = value;
    obj->rear = (obj->rear + 1) % (obj->k + 1);
    return true;
}

循环队列头删除数据

如果队列为空则返回false,删除失败

//deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))return false;
    obj->front = (obj->front + 1) % (obj->k + 1);
    return true;
}

循环队列头部和尾部获取元素

这里获取尾部元素需要经行一定的处理,rear的前一位 = (rear - 1 + k + 1)%(k + 1)

取模这部分大家可以拿出草稿纸画一画,其实也不难理解

//Front: 从队首获取元素。如果队列为空,返回 -1
int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))return -1;
    return obj->a[obj->front];
}
//Rear: 获取队尾元素。如果队列为空,返回 -1
int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))return -1;
    return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
}

释放循环队列

这里释放就行

//Free:释放空间
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

以上就是循环队列的内容,如果大家对链表实现循环队列有兴趣,可以自己在电脑上敲敲试试,虽然逻辑相比顺序表实现复杂一些,不过同样是可行的。也可以返回去做做那道力扣循环队列实现的题目,巩固一下所学。

结语

到这里栈和队列的内容基本上就结束了,本篇文章讲解了栈和队列的概念和结构,并用C语言进行了模拟实现,最后拓展了循环队列的概念结构以及循环队列的实现。如果本篇博客对你有帮助的话,还请多多支持博主,后续博主还会产出更多有意思的内容♥

有疑问或者博文有错误可以评论区提出或者私信我哦~

相关文章
|
6月前
|
前端开发 Java
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现,包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构,支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列,并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例(如`enqueue`入队和`dequeue`出队),展示了队列的操作逻辑,帮助读者深入理解其工作机制。
165 1
|
4月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
52 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
9月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
334 77
|
8月前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
169 11
|
8月前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
8月前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
9月前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
11月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
880 9
|
11月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
223 59