济南全网营销型网站建设,通州网站开发公司,建设网站好学吗,做网站怎么导入源码目录
栈存储结构详解
进栈和出栈
栈的具体实现
栈的应用
什么是队列#xff08;队列存储结构#xff09; 栈存储结构详解 同顺序表和链表一样#xff0c;栈也是用来存储逻辑关系为 一对一 数据的线性存储结构#xff0c;如图 1 所示。 图 1 栈存储结构示意…目录
栈存储结构详解
进栈和出栈
栈的具体实现
栈的应用
什么是队列队列存储结构 栈存储结构详解 同顺序表和链表一样栈也是用来存储逻辑关系为 一对一 数据的线性存储结构如图 1 所示。 图 1 栈存储结构示意图 从图 1 我们看到栈存储结构与之前所学的线性存储结构有所差异这缘于栈对数据 存 和 取 的过程有特殊的要求
栈只能从表的一端存取数据另一端是封闭的如图 1 所示在栈中无论是存数据还是取数据都必须遵循先进后出的原则即最先进栈的元素最后出栈。拿图 1 的栈来说从图中数据的存储状态可判断出元素 1 是最先进的栈。因此当需要从栈中取出元素 1 时根据先进后出的原则需提前将元素 3 和元素 2 从栈中取出然后才能成功取出元素 1。 因此我们可以给栈下一个定义即栈是一种只能从表的一端存取数据且遵循 先进后出 原则的线性存储结构。 通常栈的开口端被称为栈顶相应地封口端被称为栈底。因此栈顶元素指的就是距离栈顶最近的元素拿图 2 来说栈顶元素为元素 4同理栈底元素指的是位于栈最底部的元素图 2 中的栈底元素为元素 1。 图 2 栈顶和栈底
进栈和出栈
基于栈结构的特点在实际应用中通常只会对栈执行以下两种操作
向栈中添加元素此过程被称为进栈入栈或压栈从栈中提取出指定元素此过程被称为出栈或弹栈
栈的具体实现
栈是一种 特殊 的线性存储结构因此栈的具体实现有以下两种方式
顺序栈采用顺序存储结构可以模拟栈存储数据的特点从而实现栈存储结构链栈采用链式存储结构实现栈结构
两种实现方式的区别仅限于数据元素在实际物理空间上存放的相对位置顺序栈底层采用的是数组链栈底层采用的是链表。有关顺序栈和链栈的具体实现会在后续章节中作详细讲解。
栈的应用
基于栈结构对数据存取采用 先进后出 原则的特点它可以用于实现很多功能。 例如我们经常使用浏览器在各种网站上查找信息。假设先浏览的页面 A然后关闭了页面 A 跳转到页面 B随后又关闭页面 B 跳转到了页面 C。而此时我们如果想重新回到页面 A有两个选择
重新搜索找到页面 A使用浏览器的回退功能。浏览器会先回退到页面 B而后再回退到页面 A。 浏览器 回退 功能的实现底层使用的就是栈存储结构。当你关闭页面 A 时浏览器会将页面 A 入栈同样当你关闭页面 B 时浏览器也会将 B入栈。因此当你执行回退操作时才会首先看到的是页面 B然后是页面 A这是栈中数据依次出栈的效果。 不仅如此栈存储结构还可以帮我们检测代码中的括号匹配问题。多数编程语言都会用到括号小括号、中括号和大括号括号的错误使用通常是丢右括号会导致程序编译错误而很多开发工具中都有检测代码是否有编辑错误的功能其中就包含检测代码中的括号匹配问题此功能的底层实现使用的就是栈结构。 同时栈结构还可以实现数值的进制转换功能。例如编写程序实现从十进制数自动转换成二进制数就可以使用栈存储结构来实现。 什么是队列队列存储结构 队列和栈一样也是一种对数据的存和取有严格要求的线性存储结构。 与栈结构不同的是队列的两端都开口要求数据只能从一端进从另一端出如图 1 所示 图 1 队列存储结构
通常称进数据的一端为 队尾出数据的一端为 队头数据元素进队列的过程称为 入队出队列的过程称为 出队。
不仅如此队列中数据的进出要遵循 先进先出 的原则即最先进队列的数据元素同样要最先出队列。拿图 1 中的队列来说从数据在队列中的存储状态可以分析出元素 1 最先进队其次是元素 2最后是元素 3。此时如果将元素 3 出队根据队列 先进先出 的特点元素 1 要先出队列元素 2 再出队列最后才轮到元素 3 出队列。
栈和队列不要混淆栈结构是一端封口特点是先进后出而队列的两端全是开口特点是先进先出。
因此数据从表的一端进从另一端出且遵循 先进先出 原则的线性存储结构就是队列。 队列存储结构的实现有以下两种方式
顺序队列在顺序表的基础上实现的队列结构链队列在链表的基础上实现的队列结构 两者的区别仅是顺序表和链表的区别即在实际的物理空间中
数据集中存储的队列是顺序队列分散存储的队列是链队列 实际生活中队列的应用随处可见比如排队买 XXX、医院的挂号系统等采用的都是队列的结构。 拿排队买票来说所有的人排成一队先到者排的就靠前后到者只能从队尾排队等待队中的每个人都必须等到自己前面的所有人全部买票成功并从队头出队后才轮到自己买票。这就不是典型的队列结构吗
