栈及其特点和应用(C++详解版)
像数组或链表一样,栈也是一种数据结构,它包含一系列元素。
但是,与数组和链表不同的是,栈是一个后进先出(LIFO)的结构,这意味着当一个程序从栈中检索元素时,插入到栈中的最后一个元素是第一个被检索的元素(同样,插入的第一个元素是最后一个被检索的元素)。
在想象一个栈的工作方式时,可以想象一下餐厅流水线开始时的一堆盘子。当餐厅的工作人员补充餐盘时,他或她放入的第一个盘子将是最后一个被取走的,如图 1 所示。
图 1 栈的后进先出方式就像餐厅盘子的取用方式
餐厅中一堆盘子的LIFO特性也是栈数据结构的主要特征。放在栈上的最后一个数据元素是从栈中检索的第一个数据。
有以下两种类型的栈数据结构:
例如,计算机系统在执行程序时就会使用栈。当某个函数被调用时,计算机系统会将程序的返回地址、函数的参数以及函数的局部变量保存在栈中。当函数返回时,这些局部变量、参数和返回的地址等都将被从栈上删除。
入栈操作会导致一个值被存储,或者被压入栈。例如,假设有一个空的整数栈,最多可以保存 3 个值。有了这个栈,则可以执行以下入栈操作:
图 2 入栈操作图解
出栈操作将从栈中检索(继而删除)一个值。假设要在如图 2 所示的栈上执行 3 个连续的出栈操作,结果将如图 3 所示。
图 3 出栈操作图解
从图 3 可以看出,最后的出栈操作可将栈清空。
对于静态和动态栈,都需要一个布尔 isEmpty 操作。当栈为空时,isEmpty 操作返回 true,否则返回 false。通过调用该操作,程序员可以在尝试执行出栈操作之前确认栈上有东西。
但是,与数组和链表不同的是,栈是一个后进先出(LIFO)的结构,这意味着当一个程序从栈中检索元素时,插入到栈中的最后一个元素是第一个被检索的元素(同样,插入的第一个元素是最后一个被检索的元素)。
在想象一个栈的工作方式时,可以想象一下餐厅流水线开始时的一堆盘子。当餐厅的工作人员补充餐盘时,他或她放入的第一个盘子将是最后一个被取走的,如图 1 所示。
图 1 栈的后进先出方式就像餐厅盘子的取用方式
餐厅中一堆盘子的LIFO特性也是栈数据结构的主要特征。放在栈上的最后一个数据元素是从栈中检索的第一个数据。
有以下两种类型的栈数据结构:
- 静态栈:又称"顺序栈"。具有固定大小,并以数组形式实现;
- 动态栈:又称"链栈"。可根据需要增长,并以链表形式实现;
栈的应用
如果某个算法需要首先处理序列中最后保存的元素,那么栈对于这种算法而言是非常有用的数据结构。例如,计算机系统在执行程序时就会使用栈。当某个函数被调用时,计算机系统会将程序的返回地址、函数的参数以及函数的局部变量保存在栈中。当函数返回时,这些局部变量、参数和返回的地址等都将被从栈上删除。
栈操作
栈有两个主要操作:入栈(push,也被称为压栈)和出栈(pop,也被称为弹栈)。入栈操作会导致一个值被存储,或者被压入栈。例如,假设有一个空的整数栈,最多可以保存 3 个值。有了这个栈,则可以执行以下入栈操作:
push(5);
push(10);
push(15);
图 2 入栈操作图解
出栈操作将从栈中检索(继而删除)一个值。假设要在如图 2 所示的栈上执行 3 个连续的出栈操作,结果将如图 3 所示。
图 3 出栈操作图解
从图 3 可以看出,最后的出栈操作可将栈清空。
对于静态和动态栈,都需要一个布尔 isEmpty 操作。当栈为空时,isEmpty 操作返回 true,否则返回 false。通过调用该操作,程序员可以在尝试执行出栈操作之前确认栈上有东西。
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频