初阶数据结构之---栈和队列（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函数里就行。

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

队列中无结点（_front 和 _rear 都为空）：这种情况需要同时对_front和_rear做出调整
队列中有结点：这时直接将新节点链接到 _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两个指针

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

队列为空：无法执行pop，assert断言
队列只有一个结点：释放节点同时将队列置空
队列中有多个结点：将队头指针释放，_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;
}

销毁队列

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

队列中无元素：直接返回，不用释放了
队列中有一个元素：释放一次并置空指针，size置零
队列中有多个元素：对照链表的销毁方式销毁，最后置空指针，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语言进行了模拟实现，最后拓展了循环队列的概念结构以及循环队列的实现。如果本篇博客对你有帮助的话，还请多多支持博主，后续博主还会产出更多有意思的内容♥

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

初阶数据结构之---栈和队列（C语言）

引言

栈

概念及结构

栈的概念

栈的具体结构

手搓一个栈（栈的实现）

初始化和销毁栈

入栈（压栈）和出栈

获取栈顶元素

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

体验一下栈

队列

队列的概念及结构

队列的概念

队列的具体结构

手搓一个队列（队列的实现）

初始化队列

队尾入队列

队头出队列

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

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

销毁队列

体验一下手搓的队列

队列拓展之设计循环队列

对于循环队列的结构设计

循环队列初始化

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

循环队列尾插入数据

循环队列头删除数据

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

释放循环队列

结语

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

初阶数据结构之---栈和队列（C语言）

引言

栈

概念及结构

栈的概念

栈的具体结构

手搓一个栈（栈的实现）

初始化和销毁栈

入栈（压栈）和出栈

获取栈顶元素

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

体验一下栈

队列

队列的概念及结构

队列的概念

队列的具体结构

手搓一个队列（队列的实现）

初始化队列

队尾入队列

队头出队列

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

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

销毁队列

体验一下手搓的队列

队列拓展之设计循环队列

对于循环队列的结构设计

循环队列初始化

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

循环队列尾插入数据

循环队列头删除数据

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

释放循环队列

结语

热门文章

最新文章

相关课程

相关电子书