AI 助理
备案控制台
开发者社区 云计算 文章 正文

【数据结构】栈和队列--＞理解和实现（赋源码)

2024-08-08 64
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】栈和队列--＞理解和实现（赋源码)

前言

  1. 栈是一种特殊的线性表，它只允许在一端进行插入和删除操作。这一端被称为栈顶，另一端被称为栈底。栈的特点是后进先出（LIFO），即最后进入的元素最先被移除。
  2. 队列是另一种特殊的线性表，它允许在一端进行插入操作，在另一端进行删除操作。插入操作的一端称为队尾，删除操作的一端称为队头。队列的特点是先进先出（FIFO），即最先进入的元素最先被移除。

栈和队列有各自的特点，严格讲用顺序表还是链表的实现都可以。但我们根据结构特点选择一个更加适合的结构进行是实现。

一、栈和队列的理解

对于栈的理解：

栈如同这个图一样，要是想拿出数据，必须从上面一个一个往下面拿。这也正是 LIFO 的体现。

对于队列的理解：

队列如同这个图一样，要是想拿出数据，必须前面一个一个往向后面拿。这也正是 FIFO 的体现。

二、栈的实现（顺组表）

2.1 栈的功能

//初始化
void STInit(ST* ps);
//压栈
void STpush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//大小
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//出栈
STDataType STTop(ST* ps);
//检查容量
void CheckCapacity(ST* ps);
//销毁
void STDestroy(ST* ps);

2.2 栈结构体的定义及其初始化

结构体的定义

typedef int STDataType;

typedef struct stack
{
  STDataType* a;
  int top;
  int capacity;
}ST;

初始化（开辟空间）

void STInit(ST* ps)
{
  assert(ps);
  ps->a = (STDataType*)malloc(sizeof(STDataType)*4);
  if (ps->a == NULL)
  {
    perror("malloc fail");
    return;
  }
  
  ps->capacity = 4;
  ps->top = 0;
}

2.3 压栈（存储数据）

//压栈
void STpush(ST* ps,STDataType x)
{
  assert(ps);

  ps->a[ps->top] = x;
  ps->top++;
}

2,4 删除数据

在这里面删除数据是配合，栈顶出栈。每次拿出一个数据，就要减少一个数据。

void STPop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));

  ps->top--;
}

2.5 计算栈内元个数

//大小
int STSize(ST* ps)
{
  assert(ps);

  return ps->top;
}

2.6 判断栈内是否为空

这里运用 bool 类型直接返回，比较方便。

bool STEmpty(ST* ps)
{
  assert(ps);

  return ps->top == 0;
}

2.7 出栈

//出栈
STDataType STTop(ST* ps)
{
  assert(ps);

  return ps->a[ps->top-1];
}

2.8 增加容量

//检查容量
void CheckCapacity(ST*ps)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    ST* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2);
    if (tmp == NULL)
    {
      perror("malloc fail");
      return;
    }
    ps->capacity *= 2;
    ps->a = tmp;
  }
}

2.9 销毁栈

//销毁
void STDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}

三、队列的实现（单链表）

3.1 队列的功能

//初始化
void QueueInit(Queue* ps);
//销毁
void QueueDestroy(Queue* ps);
//入队
void QueuePush(Queue* ps, QDataType x);
//删除
void QueuePop(Queue* ps);
//大小
int QueueSize(Queue* ps);
//判空队
bool QueueEmpty(Queue* ps);
//出队头
QDataType QueueTop(Queue* ps);
//出队尾
QDataType QueueBack(Queue* ps);

3.2 队列的结构体定义以及初始化

结构体定义

定义两个结构体，第一个为存放数据，第二个结构体为两个指针，分别指向头和尾

typedef int QDataType;

typedef struct QNode
{
  struct QNode* next;
  QDataType data;

}QNode;

typedef struct Queue
{
  QNode*head;
  QNode*tail;
   
  int szie;
}Queue;

初始化

//初始化
void QueueInit(Queue* ps)
{
  assert(ps);
  
  ps->head = ps->tail = NULL;
  
  ps->szie = 0;
  
}

3.3 队列销毁

//销毁
void QueueDestroy(Queue* ps)
{
  assert(ps);
  QNode* cur = ps->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }

  ps->head = ps->tail = NULL;
  ps->szie = 0;
}

3.4 入队（插入数据）

//入队
void QueuePush(Queue* ps,QDataType x)
{
  assert(ps);

  QNode* newcode = (QNode*)malloc(sizeof(QNode));
  if (newcode == NULL)
  {
    perror("malloc fail");
    return ;
  }
  newcode->next = NULL;
  newcode->data = x;

  if (ps->head == NULL)
  {
    ps->head = ps->tail = newcode;
    
  }
  else

  {
    
    ps->tail->next = newcode;
    ps->tail = newcode;
  }

  ps->szie++;

}

3.5 删除数据（头删）

//删除
void QueuePop(Queue* ps)
{
  assert(ps);
  assert(ps->head != NULL);
  assert(!QueueEmpty(ps));

  if (ps->head->next == NULL)
  {
    free(ps->head);
    ps->head = ps->tail = NULL;
  }
  else
  {
    QNode* next = ps->head->next;
    free(ps->head);
    ps->head = next;

  }
  ps->szie--;
}

3.6 计算队列元素个数

//大小
int QueueSize(Queue* ps)
{
  assert(ps);

  return ps->szie;
}

3.7 判断是否队列为空

//判空队
bool QueueEmpty(Queue* ps)
{
  assert(ps);

  return ps->szie == 0;
}

3.8 出队（头）

//出队头
QDataType QueueTop(Queue* ps)
{
  assert(ps);
  assert(!QueueEmpty(ps));

  return ps->head->data;
}

3.9 出队（尾）

//出队尾
QDataType QueueBack(Queue* ps)
{
  assert(ps);

  return ps->tail->data;
}

四、栈和队列的源码

栈

Stack.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>


typedef int STDataType;

typedef struct stack
{
  STDataType* a;
  int top;
  int capacity;
}ST;

//初始化
void STInit(ST* ps);
//压栈
void STpush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//大小
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//出栈
STDataType STTop(ST* ps);
//检查容量
void CheckCapacity(ST* ps);
//销毁
void STDestroy(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS


#include "stack.h"


//初始化
void STInit(ST* ps)
{
  assert(ps);
  ps->a = (STDataType*)malloc(sizeof(STDataType*)*4);
  if (ps->a == NULL)
  {
    perror("malloc fail");
    return;
  }
  
  ps->capacity = 4;
  ps->top = 0;
}
//销毁
void STDestroy(ST* ps)
{
  assert(ps);

  free(ps->a);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}

//检查容量
void CheckCapacity(ST*ps)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    ST* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2);
    if (tmp == NULL)
    {
      perror("malloc fail");
      return;
    }
    ps->capacity *= 2;
    ps->a = tmp;
  }
}

//压栈
void STpush(ST* ps,STDataType x)
{
  assert(ps);

  ps->a[ps->top] = x;
  ps->top++;
}

//删除
void STPop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));

  ps->top--;
}

//判空
bool STEmpty(ST* ps)
{
  assert(ps);

  return ps->top == 0;
}

//出栈
STDataType STTop(ST* ps)
{
  assert(ps);

  return ps->a[ps->top-1];
}

//大小
int STSize(ST* ps)
{
  assert(ps);

  return ps->top;
}

test.c

#define _CRT_SECURE_NO_WARNINGS


#include "stack.h"

void teststack()
{
  ST st;
  STInit(&st);

  STpush(&st, 1);
  STpush(&st, 2);
  STpush(&st, 3);
  STpush(&st, 4);
  STpush(&st, 5);

  printf("%d", STSize(&st));
  printf("\n");

  while (!STEmpty(&st))
  {
    printf("%d ", STTop(&st));
    STPop(&st);
  }
  printf("\n");
  printf("%d", STSize(&st));

  STDestroy(&st);

}



int main()
{
  teststack();

  return 0;
}

队列

Queue.h

#pragma once

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int QDataType;

typedef struct QNode
{
  struct QNode* next;
  QDataType data;

}QNode;

typedef struct Queue
{
  QNode*head;
  QNode*tail;
   
  int szie;
}Queue;


//单链表的实现，FIFO

//初始化
void QueueInit(Queue* ps);
//销毁
void QueueDestroy(Queue* ps);
//入队
void QueuePush(Queue* ps, QDataType x);
//删除
void QueuePop(Queue* ps);
//大小
int QueueSize(Queue* ps);
//判空队
bool QueueEmpty(Queue* ps);
//出队头
QDataType QueueTop(Queue* ps);
//出队尾
QDataType QueueBack(Queue* ps);

Queue.c

#define _CRT_SECURE_NO_WARNINGS

#include "queue.h"



//初始化
void QueueInit(Queue* ps)
{
  assert(ps);

  ps->head = ps->tail = NULL;

  ps->szie = 0;

}

//销毁
void QueueDestroy(Queue* ps)
{
  assert(ps);
  QNode* cur = ps->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }

  ps->head = ps->tail = NULL;
  ps->szie = 0;
}

//入队
void QueuePush(Queue* ps,QDataType x)
{
  assert(ps);

  QNode* newcode = (QNode*)malloc(sizeof(QNode));
  if (newcode == NULL)
  {
    perror("malloc fail");
    return ;
  }
  newcode->next = NULL;
  newcode->data = x;

  if (ps->head == NULL)
  {
    ps->head = ps->tail = newcode;
    
  }
  else

  {
    
    ps->tail->next = newcode;
    ps->tail = newcode;
  }

  ps->szie++;

}

//删除
void QueuePop(Queue* ps)
{
  assert(ps);
  assert(ps->head != NULL);
  assert(!QueueEmpty(ps));

  if (ps->head->next == NULL)
  {
    free(ps->head);
    ps->head = ps->tail = NULL;
  }
  else
  {
    QNode* next = ps->head->next;
    free(ps->head);
    ps->head = next;

  }
  ps->szie--;
}

//大小
int QueueSize(Queue* ps)
{
  assert(ps);

  return ps->szie;
}

//判空队
bool QueueEmpty(Queue* ps)
{
  assert(ps);

  return ps->szie == 0;
}

//出队头
QDataType QueueTop(Queue* ps)
{
  assert(ps);
  assert(!QueueEmpty(ps));

  return ps->head->data;
}

//出队尾
QDataType QueueBack(Queue* ps)
{
  assert(ps);

  return ps->tail->data;
}

test.c

#define _CRT_SECURE_NO_WARNINGS

#include "queue.h"



void testQueue()
{
  Queue s;
  QueueInit(&s);

  QueuePush(&s, 1);
  QueuePush(&s, 2);
  QueuePush(&s, 3);
  QueuePush(&s, 4);

  

  //printf("%d ", QueueTop(&s));
  //QueuePop(&s);
  //printf("%d ", QueueTop(&s));
  //QueuePop(&s); 
  //printf("%d ", QueueTop(&s));
  //QueuePop(&s); 
  //printf("%d ", QueueTop(&s));
  //QueuePop(&s);
  //printf("\n");

  while (!(QueueEmpty(&s)))
  {
    printf("%d ", QueueTop(&s));
    QueuePop(&s);
  }


  QueueDestroy(&s);

}

int main()
{
  testQueue();


  return 0;
}

文章标签：
存储
关键词：
数据结构源码
数据结构队列
数据结构栈队列
数据结构栈
数据结构栈队列源码
chian-ocean
目录
相关文章
大数据文摘
|
5月前
|
前端开发 Java
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现，包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构，支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列，并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例（如`enqueue`入队和`dequeue`出队），展示了队列的操作逻辑，帮助读者深入理解其工作机制。
大数据文摘
137 1
啦啦啦191
|
3月前
|
存储 安全 Java
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架，涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口，逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变，包括数组+链表+红黑树优化，以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例，展示集合框架的应用价值，助你全面掌握相关知识，轻松应对面试与开发需求。
啦啦啦191
176 3
hahaha无
|
3月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因，涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问，修改了变量`i`的值，导致`for`循环条件始终为真，形成死循环。原因是VS2022栈区从低地址到高地址分配内存，`arr`数组与`i`相邻，`arr[15]`恰好覆盖`i`的地址。而在VS2019中，栈区先分配高地址再分配低地址，因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致，需避免数组越界以确保代码健壮性。
hahaha无
35 0
栈区的非法访问导致的死循环(x64)
游客beejssedmb2sq
|
3月前
232.用栈实现队列，225. 用队列实现栈
在232题中，通过两个栈（`stIn`和`stOut`）模拟队列的先入先出（FIFO）行为。`push`操作将元素压入`stIn`，`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列（`que`）模拟栈的后入先出（LIFO）特性。通过多次调整队列头部元素的位置，确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素，`empty`判断队列是否为空。 两题均仅使用基础数据结构操作，展示了栈与队列之间的转换逻辑。
游客beejssedmb2sq
56 0
ephemerals__
|
6月前
|
存储 自然语言处理 数据库
【数据结构进阶】AVL树深度剖析 + 实现（附源码）
在深入探讨了AVL树的原理和实现后，我们不难发现，这种数据结构不仅优雅地解决了传统二叉搜索树可能面临的性能退化问题，还通过其独特的平衡机制，确保了在任何情况下都能提供稳定且高效的查找、插入和删除操作。
ephemerals__
449 19
ephemerals__
|
6月前
|
数据库 C++
【数据结构进阶】红黑树超详解 + 实现（附源码）
本文深入探讨了红黑树的实现原理与特性。红黑树是一种自平衡二叉搜索树，通过节点着色（红/黑）和特定规则，确保树的高度接近平衡，从而实现高效的插入、删除和查找操作。相比AVL树，红黑树允许一定程度的不平衡，减少了旋转调整次数，提升了动态操作性能。文章详细解析了红黑树的性质、插入时的平衡调整（变色与旋转）、查找逻辑以及合法性检查，并提供了完整的C++代码实现。红黑树在操作系统和数据库中广泛应用，其设计兼顾效率与复杂性的平衡。
ephemerals__
844 3
蓝易云
|
7月前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例，希望能帮助读者更好地理解和应用这些重要的数据结构。
蓝易云
133 11
ephemerals__
|
10月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
830 9
那年春天
|
10月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
210 59
RossyYan
|
8月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
321 77

热门文章

最新文章

  • 1
    Redis数据库的五类核心数据结构详解
  • 2
    Redis核心数据结构与分布式锁实现详解
  • 3
    MySQL数据库索引的数据结构？
  • 4
    基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
  • 5
    企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
  • 6
    公司员工泄密防护体系中跳表数据结构及其 Go 语言算法的应用研究
  • 7
    【模板】栈
  • 8
    【算法与数据结构】关于代码运行时间复杂度的计算方法
  • 9
    基础知识 初识栈和堆
  • 10
    软考中的数据结构
  • 1
    【数据结构】遍历二叉树（递归思想）--＞赋源码
    104
  • 2
    【数据结构】双向带头（哨兵位）循环链表 —详细讲解（赋源码）
    170
  • 3
    深入探索堆：Go语言中的高效数据结构
    139
  • 4
    PHP 数据结构的巅峰对决：在机器学习的舞台上，谁将主宰沉浮？
    83
  • 5
    揭秘C#.Net编程秘宝：结构体类型Struct，让你的数据结构秒变高效战斗机，编程界的新星就是你！
    413
  • 6
    栈溢出处理
    352
  • 7
    开发与运维C++问题之更改数据模型为通用数据结构如何解决
    84
  • 8
    【数据结构】排序算法——Lesson2
    79
  • 9
    python的数据结构
    78
  • 10
    go 高并发下的数据结构是怎样？
    239

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云OSS设置跨域访问