【奇妙的数据结构世界】用图像和代码对堆栈的使用进行透彻学习 | C++

简介: 简单来说,数据结构是一种辅助程序设计并且进行优化的方法论,它不仅讨论数据的存储与处理的方法,同时也考虑到了数据彼此之间的关系与运算,从而极大程度的提高程序执行的效率,减少对内存空间的占用等。不同种类的数据结构适用于不同的程序应用,选择合适正确的数据结构,可以让算法发挥出更大的性能,给设计的程序带来更高效率的算法。

前言

       简单来说,数据结构是一种辅助程序设计并且进行优化的方法论,它不仅讨论数据的存储与处理的方法,同时也考虑到了数据彼此之间的关系与运算,从而极大程度的提高程序执行的效率,减少对内存空间的占用等。不同种类的数据结构适用于不同的程序应用,选择合适正确的数据结构,可以让算法发挥出更大的性能,给设计的程序带来更高效率的算法。


一、堆栈是什么?

1.简要介绍

       堆栈是一组相同的数据类型的组合,所有的操作均在堆栈的顶端去进行,具有后进先出的特性。它是一种抽象的数据结构,具有两个显著特性:①只能从栈顶去进行存取数据的操作;②数据的存取符合后进先出的原则;栈它可以分为顺序栈和链式栈两种类型,它们在不同的问题中都会有广泛的应用。要特别注意链式栈指针域的指针指向,它与基本的链表有一定的差异。两种数据结构的类型如下图所示:


二、堆栈操作的关键代码段

1.类型定义

①顺序栈存储结构的定义

typedef struct {
  selemtype* base;    //栈底指针
  selemtype* top;    //栈顶指针
  int stacksize;  //堆栈大小
}sqstack;

②链式栈存储结构的定义

typedef struct stacknode{
  selemtype data;  //数据元素
  struct stacknode* next;  //指针域
}stacknode,*linklist;
linklist s;   //指针

2.顺序栈的常用操作

①顺序栈的初始化

void initstack(sqstack& s)
{
  s.base = new selemtype[maxsize];   //开拓一块新的堆栈区域,大小需要事先声明,并且将栈底指针指向栈底
  if (!s.base) {
  exit(0);  
  }   //创建失败
  else {
  s.top = s.base;   
  s.stacksize = maxsize;
  }   //创建成功,初始时需要将栈底指针的位置赋给栈顶指针,给栈一个空间大小
}

②判断顺序栈是否为空

bool emptystack(sqstack& s)
{
  if (s.base == s.top) {
  return true;
  }   //如果栈底指针和栈顶指针指向同一个位置的话,也就是初始化下的状态时,就是空的
  else {
  return false;
  }    //反之不为空
}

③ 求顺序栈的长度

int lengthstack(sqstack& s)
{
  int length = s.top - s.base;  //头指针所在的位置减去尾指针所在的位置
  return length;
}

④ 清空顺序栈

void clearstack(sqstack& s)
{
  if (s.base)
  s.top = s.base;  
  //判断如果栈底指针存在,那么直接将栈底的位置赋到栈顶指针的位置即可,就好比初始化下的状态
}

⑤ 销毁顺序栈

void destorystack(sqstack& s)
{
  if (s.base)
  {
  delete s.base;   
  s.stacksize = 0;  
  s.base = s.top = NULL;   //最终两个指针指向一块空的区域
  }
  //判断如果栈底指针存在,那么就说明这个栈存在,然后将栈底指针指向的那块删除,栈的长度直接修改为0即可
}

⑥顺序栈的入栈

int pushstack(sqstack& s,selemtype e)
{
  if (s.top-s.base<s.stacksize) {   //如果此刻栈中元素的长度小于我们栈的总长度,那么说明可以继续入栈
  *s.top = e;   //将新数据入栈到栈顶
  s.top++;   //将栈顶指针向上移动
  return 1;
  }
  else {
  return 0;
  }
}

⑦顺序栈的出栈

int popstack(sqstack& s, selemtype e)
{
  if (s.base == s.top) {   //空栈
  return 0;
  }
  else {
  s.top--;   //将栈顶指针向下移动
  e = *s.top;  //将出栈元素的数据内容保存
  return 1;
  }
}

3.链式栈的常用操作

①链栈的初始化

void initstack(linkstack& s)
{
  s = NULL;   //链式栈的初始化
}

②判断链栈是否为空

bool emptystack(linkstack& s)
{
  if (s == NULL)    //初始化下的状态就是一个空栈
  return true;
  else
  return false;
}

③链栈的入栈

int push(linkstack& s,selemtype e)
{
  linkstack p;
  p = new stacknode;   //创建在链式栈中的新结点
  p->data = e;  //将要入栈的数据元素赋给结点的数据域
  p->next = s;  //链式栈中指针域是向前指的,所以将新结点的指针域指它前面s指针所指向的位置
  s = p;    //再将指针s后移,进行下次的操作
  return 1;
}

④链栈的出栈

int pop(linkstack& s, selemtype e)
{
  if (s == NULL) {
  return 0;
  }
  else {
  linkstack p;
  e=s->data;
  p = s;   
  s = s->next;
  delete p;
  return 1;
  }
}

⑤取栈顶元素

selemtype gettop(linkstack &s)
{
  if (s != NULL)   //栈顶指针存在
  return s->data;   //取出此刻栈顶的数据元素
}

总结

       以上就是我们这节对堆栈的全部学习,堆栈的基本运算我在上面基本都已经讲到,希望可以对你有所帮助。我认为图形与代码的结合是学习数据结构算法的核心关键。用图来理解代码,用代码来实现图形。这样不光可以很好的提高我们的代码编程能力,还可以提高我们的抽象逻辑思维能力。


目录
相关文章
|
1月前
|
存储 算法 C++
【C++数据结构——查找】二分查找(头歌实践教学平台习题)【合集】
二分查找的基本思想是:每次比较中间元素与目标元素的大小,如果中间元素等于目标元素,则查找成功;顺序表是线性表的一种存储方式,它用一组地址连续的存储单元依次存储线性表中的数据元素,使得逻辑上相邻的元素在物理存储位置上也相邻。第1次比较:查找范围R[0...10],比较元素R[5]:25。第1次比较:查找范围R[0...10],比较元素R[5]:25。第2次比较:查找范围R[0..4],比较元素R[2]:10。第3次比较:查找范围R[3...4],比较元素R[3]:15。,其中是顺序表中元素的个数。
137 68
【C++数据结构——查找】二分查找(头歌实践教学平台习题)【合集】
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
61 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
算法 C++
【C++数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】
【数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】 目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果: 任务描述 本关任务:实现二叉排序树的基本算法。 相关知识 为了完成本关任务,你需要掌握:二叉树的创建、查找和删除算法。具体如下: (1)由关键字序列(4,9,0,1,8,6,3,5,2,7)创建一棵二叉排序树bt并以括号表示法输出。 (2)判断bt是否为一棵二叉排序树。 (3)采用递归方法查找关键字为6的结点,并输出其查找路径。 (4)分别删除bt中关键
53 11
【C++数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】
|
1月前
|
存储 人工智能 算法
【C++数据结构——图】最短路径(头歌教学实验平台习题) 【合集】
任务描述 本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。 相关知识 为了完成本关任务,你需要掌握:Dijkst本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。为了完成本关任务,你需要掌握:Dijkstra算法。带权有向图:该图对应的二维数组如下所示:Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下:(1)初始时,S只包含源点,即S={v},v的距离为0。
61 15
|
1月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
48 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
46 10
|
1月前
|
算法 C++
【C++数据结构——图】最小生成树(头歌实践教学平台习题) 【合集】
【数据结构——图】最小生成树(头歌实践教学平台习题)目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:【合集】任务描述 本关任务:编写一个程序求图的最小生成树。相关知识 为了完成本关任务,你需要掌握:1.建立邻接矩阵,2.Prim算法。建立邻接矩阵 上述带权无向图对应的二维数组,根据它建立邻接矩阵,如图1建立下列邻接矩阵。注意:INF表示无穷大,表示整数:32767 intA[MAXV][MAXV];Prim算法 普里姆(Prim)算法是一种构造性算法,从候选边中挑
44 10
|
1月前
|
存储 算法 C++
【C++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。
49 10