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

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

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

前言

  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
目录
相关文章
那年春天
|
1月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
26 1
龙大吉
|
17天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
38 5
德国都芳最好
|
1月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
78 21
html的七十二变
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
32 2
XIAZHI
|
24天前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
42 0
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
159 9
dufadayang
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
51 4
java冯坚持
|
2月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
42 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
肾透侧视攻城狮
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
23 1
禁默
|
2月前
初步认识栈和队列
初步认识栈和队列
禁默
61 10