5.堆栈算法

简介: 5.堆栈算法

1.堆栈算法

堆栈是一种抽象数据类型(ADT),通常用于大多数编程语言。它被命名为堆栈,因为它的行为类似于真实世界的堆栈,例如 - 一副牌或一堆盘子等。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2GDNiX7i-1681054051383)(5.堆栈算法.assets/image-20230323111909639.png)]

真实世界的堆栈仅允许在一端进行操作。例如,我们只能从堆叠顶部放置或移除卡或板。同样,Stack ADT仅允许一端的所有数据操作。在任何给定时间,我们只能访问堆栈的顶部元素。

此功能使其成为LIFO数据结构。LIFO代表Last-in-first-out。这里,首先访问最后放置(插入或添加)的元素。在堆栈术语中,插入操作称为 PUSH 操作,删除操作称为 POP 操作。

堆栈表示

下图描绘了一个堆栈及其操作 -

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-k6He7emz-1681054051385)(5.堆栈算法.assets/image-20230323111922816.png)]

堆栈可以通过数组,结构,指针和链接列表来实现。堆栈可以是固定大小的堆栈,也可以具有动态调整大小的感觉。在这里,我们将使用数组实现堆栈,这使得它成为固定大小的堆栈实现。

基本操作

堆栈操作可能涉及初始化堆栈,使用它然后取消初始化。除了这些基本内容之外,堆栈还用于以下两个主要操作 -

  • push() - 在堆栈上推送(存储)一个元素。
  • pop() - 从堆栈中删除(访问)一个元素。

当数据被推入堆栈时。

要有效地使用堆栈,我们还需要检查堆栈的状态。出于同样的目的,将以下功能添加到堆栈中 -

  • peek() - 获取堆栈的顶部数据元素,而不删除它。
  • isFull() - 检查堆栈是否已满。
  • isEmpty() - 检查堆栈是否为空。

在任何时候,我们都维护指向堆栈上最后一个PUSHed数据的指针。由于此指针始终表示堆栈的顶部,因此命名为 top 。的 顶部 指针提供栈顶部的值,而无需实际删除它。

首先,我们应该了解支持堆栈功能的过程

窥视()

peek()函数的算法

begin procedure peek
   return stack[top]
end procedure

用C编程语言实现peek()函数

int peek() {
   return stack[top];
}

已满()

isfull()函数的算法

begin procedure isfull
   if top equals to MAXSIZE
      return true
   else
      return false
   endif
end procedure

在C编程语言中实现isfull()函数

bool isfull() {
   if(top == MAXSIZE)
      return true;
   else
      return false;
}

是空的()

isempty()函数的算法

begin procedure isempty
   if top less than 1
      return true
   else
      return false
   endif
end procedure

在C编程语言中实现isempty()函数略有不同。我们将top初始化为-1,因为数组中的索引从0开始。因此我们检查top是否低于零或-1以确定堆栈是否为空。这是代码

bool isempty() {
   if(top == -1)
      return true;
   else
      return false;
}

推动操作

将新数据元素放入堆栈的过程称为推送操作。推送操作涉及一系列步骤 -

  • 第1步 - 检查堆栈是否已满。
  • 步骤2 - 如果堆栈已满,则产生错误并退出。
  • 步骤3 - 如果堆栈未满,则 从上到下 增加下一个空白区域。
  • 第4步 - 将数据元素添加到堆栈位置,top指向该位置。
  • 第5步 - 返回成功。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wXxAP8C7-1681054051386)(5.堆栈算法.assets/image-20230323111954363.png)]

如果链表用于实现堆栈,那么在步骤3中,我们需要动态分配空间。

PUSH操作的算法

推送操作的简单算法可以推导如下

begin procedure push: stack, data
   if stack is full
      return null
   endif
   top ← top + 1
   stack[top] ← data
end procedure

在C中实现这个算法非常容易。请参阅以下代码 -

void push(int data) {
   if(!isFull()) {
      top = top + 1;   
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

流行操作

从堆栈中删除内容时访问内容称为弹出操作。在pop()操作的数组实现中,实际上并未移除数据元素,而是将 top 递减到堆栈中的较低位置以指向下一个值。但是在链表实现中,pop()实际上删除了数据元素并释放了内存空间。

Pop操作可能涉及以下步骤 -

  • 第1步 - 检查堆栈是否为空。
  • 第2步 - 如果堆栈为空,则产生错误并退出。
  • 步骤3 - 如果堆栈不为空,则访问 top 指向的数据元素。
  • 第4步 - 将top的值减1。
  • 第5步 - 返回成功。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-e5qZmpcQ-1681054051386)(5.堆栈算法.assets/image-20230323112016760.png)]

流行操作算法

一个简单的Pop操作算法可以推导如下

begin procedure pop: stack
   if stack is empty
      return null
   endif
   data ← stack[top]
   top ← top - 1
   return data
end procedure

在C中实现该算法如下

实例

int pop(int data) {
 if(!isempty()) {
    data = stack[top];
    top = top - 1;   
    return data;
 } else {
    printf("Could not retrieve data, Stack is empty.\n");
 }
}
目录
相关文章
|
Python
什么是Python中的内存池(Memory Pool)?
什么是Python中的内存池(Memory Pool)?
200 0
网络基础之三
网络基础之三
237 0
|
9月前
|
存储 人工智能 OLAP
百炼融合AnalyticDB,10分钟创建网站AI助手
百炼融合AnalyticDB,10分钟创建网站AI助手。本课程由阿里云产品经理陈茏久分享,涵盖大模型行业变革、向量数据库驱动RAG服务化探索、方案优势及应用场景、产品选型配置及最新发布等内容。通过整合通义百炼和AnalyticDB,用户可快速搭建具备企业私域知识的AI助手,实现智能客服、教育、汽车等多行业的应用升级。教程详细介绍了从环境搭建到知识库配置的全流程,并提供了免费试用资源,帮助用户低成本体验核心能力。
317 7
|
传感器 数据采集 监控
LabVIEW电压电流实时监测系统
LabVIEW电压电流实时监测系统
244 0
|
11月前
|
运维 网络协议
IP 地址类别:权威指南
IP 地址类别:权威指南
1451 4
|
存储 API Swift
Ceph Reef(18.2.X)之Swift操作对象存储网关
这篇文章详细介绍了Ceph Reef(18.2.X)中通过Swift API操作对象存储网关的方法,包括创建用户、子用户、配置环境变量、以及使用swift命令行工具进行存储桶和对象的管理。
145 7
Ceph Reef(18.2.X)之Swift操作对象存储网关
|
12月前
|
算法
串ababaaababaa的next和串ababaabab的nextval
本文介绍了计算字符串的next数组和nextval数组的方法,通过分析两个具体的例子来展示如何计算这些数组,这些数组通常用于KMP算法中。
579 0
串ababaaababaa的next和串ababaabab的nextval
|
存储 网络协议 网络性能优化
一文详细理解计算机网络体系结构(考试和面试必备)
这篇文章提供了C++基础知识的快速概述,包括C++的特点、面向对象设计、组成部分、标准、学习建议、应用领域、源文件、编译器、类与对象、编译执行步骤、分号与块、标识符、基本数据类型、typedef、枚举类型、变量定义与声明等。
411 0
一文详细理解计算机网络体系结构(考试和面试必备)
|
存储 Java Apache
|
存储 安全 Java
【面试题精讲】Queue 与 Deque 的区别
【面试题精讲】Queue 与 Deque 的区别