栈:后进先出的数据结构

这篇具有很好参考价值的文章主要介绍了栈:后进先出的数据结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

栈与队列

在计算机科学中,栈(Stack)是一种常见的数据结构,它的特殊性在于遵循后进先出(Last-In-First-Out,LIFO)的原则。栈被广泛应用于各种计算机算法和程序设计中,它的简单而有效的特性使得它在解决许多问题时都能发挥重要作用。

栈的工作原理

栈的工作原理可以类比成一个物理上的堆叠,就像一叠盘子。最先放入的盘子位于底部,最后放入的盘子位于顶部,而取盘子的时候总是从顶部开始取。这种特性决定了栈的后进先出的行为。具体来说,栈支持以下两个基本操作:

  1. 入栈(Push)

  2. 将元素放入栈的顶部。新元素会成为栈顶,而原来的栈顶元素会下移一个位置。
  3. 出栈(Pop)

  4. 从栈的顶部取出栈顶元素。取出后,栈顶下移一个位置。

这里笔者用字符画生动的做了一个图来供大家理解原理

初始状态:   栈为空

入栈操作:
1. 将元素A入栈
   栈顶
   ------
   |  A |
   ------

2. 将元素B入栈
   栈顶
   ------
   |  B |
   ------
   |  A |
   ------

3. 将元素C入栈
   栈顶
   ------
   |  C |
   ------
   |  B |
   ------
   |  A |
   ------

出栈操作:
1. 执行出栈操作
   栈顶
   ------
   |  B |
   ------
   |  A |
   ------

2. 再次执行出栈操作
   栈顶
   ------
   |  A |
   ------

3. 执行出栈操作后,栈为空
   栈为空

栈还通常提供一个**查看栈顶(Peek)**的操作,用于查询当前栈顶的元素而不将其移出栈。

栈的应用示例:表达式求值

考虑一个实际应用的例子:数学表达式的求值。我们要解析一个数学表达式并计算其结果。这里我们以中缀表达式为例,中缀表达式是我们通常使用的数学表达式,例如 "3 + 5 * ( 2 - 8 )". 我们可以通过栈来实现表达式的求值。

  1. 操作数栈(Operand Stack)

  2. 我们使用一个栈来存储操作数,即数字。当解析到一个数字时,将其入栈。
  3. 运算符栈(Operator Stack)

  4. 我们使用另一个栈来存储运算符。当解析到一个运算符时,需要根据运算符的优先级和结合性来判断是否需要进行计算。

例如,考虑表达式 "3 + 5 * ( 2 - 8 )":

  1. 遇到 "3",将其入操作数栈。
  2. 遇到 "+",由于运算符栈为空,直接入栈。
  3. 遇到 "5",将其入操作数栈。
  4. 遇到 "",由于 "" 的优先级高于 "+",将其入运算符栈。
  5. 遇到 "(",将其入运算符栈。
  6. 遇到 "2",将其入操作数栈。
  7. 遇到 "-",由于 "-" 的优先级低于 "",弹出 "" 运算符并进行计算,结果入操作数栈。
  8. 遇到 "8",将其入操作数栈。
  9. 遇到 ")",弹出运算符栈中的 "(",弹出 "*" 运算符并进行计算,结果入操作数栈。
  10. 弹出运算符栈中的 "+" 运算符并进行计算,得到最终结果。

通过使用栈,我们可以按照正确的顺序解析表达式并计算出结果。

浏览器进退(使用栈)

想象你正在使用一个浏览器浏览网页,每当你访问一个新的网页时,浏览器会将该网页的信息存储在一个栈中,表示你的浏览历史。如果你想后退,浏览器会从栈中弹出当前网页,然后显示前一个网页。如果你想前进,浏览器可以从另一个栈中弹出被后退时移出的网页,然后显示它。下面笔者用一个C++代码来实现这个功能

#include <iostream>
#include <stack>
#include <string>

class Browser {
private:
    std::stack<std::string> backStack;  // 后退栈
    std::stack<std::string> forwardStack;  // 前进栈
    std::string currentURL;  // 当前网页的URL

public:
    Browser() {
        currentURL = "about:blank";  // 默认打开空白页面
    }

    void visit(const std::string& url) {
        backStack.push(currentURL);
        currentURL = url;
        while (!forwardStack.empty()) {
            forwardStack.pop();  // 访问新页面后,前进栈被清空
        }
    }

    bool canGoBack() {
        return !backStack.empty();
    }

    bool canGoForward() {
        return !forwardStack.empty();
    }

    void goBack() {
        if (canGoBack()) {
            forwardStack.push(currentURL);
            currentURL = backStack.top();
            backStack.pop();
        }
    }

    void goForward() {
        if (canGoForward()) {
            backStack.push(currentURL);
            currentURL = forwardStack.top();
            forwardStack.pop();
        }
    }

    std::string getCurrentURL() {
        return currentURL;
    }
};

int main() {
    Browser browser;

    browser.visit("https://www.example.com");
    std::cout << "当前页面:" << browser.getCurrentURL() << std::endl;

    browser.visit("https://www.openai.com");
    std::cout << "当前页面:" << browser.getCurrentURL() << std::endl;

    if (browser.canGoBack()) {
        browser.goBack();
        std::cout << "后退后页面:" << browser.getCurrentURL() << std::endl;
    }

    if (browser.canGoForward()) {
        browser.goForward();
        std::cout << "前进后页面:" << browser.getCurrentURL() << std::endl;
    }

    return 0;
}

总结

栈是一种简单而强大的数据结构,遵循后进先出的原则。它可以通过入栈和出栈操作来完成许多算法和程序设计中的任务,如函数调用、括号匹配、表达式求值等。通过栈,我们可以更好地理解数据结构和算法之间的关系,以及如何应用它们解决实际问题。

 文章来源地址https://www.toymoban.com/news/detail-682299.html

到了这里,关于栈:后进先出的数据结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法 数据结构分类 数据结构类型介绍 数据结构线性非线性结构 算法合集 (一)

     数据结构分为:                            a.线性结构                            b.非线性结构  a.线性结构:                       数据与结构存在一对一的线性关系; a . 线性结构 存储 分为:                                   顺序存储

    2024年02月10日
    浏览(49)
  • 结构化数据、非结构化数据、半结构化数据

    结构化的数据一般是指可以使用关系型数据库表示和存储,可以用二维表来逻辑表达实现的数据。例如:需要多少个属性,每个属性什么类型,每个属性的取值范围等等,类似下图所示, 提前定义好了一个二维矩阵的元数据 ,包含有列名称、列的类型、列的约束等:   可见

    2024年02月09日
    浏览(64)
  • 【数据结构】何为数据结构。

    🚩 WRITE IN FRONT 🚩    🔎 介绍:\\\"謓泽\\\"正在路上朝着\\\"攻城狮\\\"方向\\\"前进四\\\" 🔎 🏅 荣誉:2021|2022年度博客之星物联网与嵌入式开发TOP5|TOP4、2021|2022博客之星TOP100|TOP63、阿里云专家博主、掘金优秀创作者、全网粉丝量6w+、全网访问量100w+ 🏅 🆔 文章内容由 謓泽 原创 如需相关

    2024年02月08日
    浏览(60)
  • 数据结构和算法——数据结构

    目录 线性结构  队列结构的队列 链表结构的队列 链表的面试题 单向链表应用场景 约瑟夫环问题 栈结构 中缀表达式 前缀表达式 后缀表达式 非线性结构 图 递归解决迷宫问题 递归解决八皇后问题 顺序存储方式,顺序表 常见的顺序存储结构有:数组、队列、链表、栈 链式存

    2024年02月07日
    浏览(54)
  • 【数据结构】什么是数据结构?

    🦄 个人主页 :修修修也 🎏 所属专栏 :数据结构 ⚙️ 操作环境 : Visual Studio 2022 目录 🎏数据结构的定义 🎏结语 数据结构(Data Structure)是计算机 存储 , 组织数据的方式 ,指 相互之间存在一种或多种特定关系的数据元素的集合 . 这么讲可能有些抽象,放一张图大家可能好理解一

    2024年02月07日
    浏览(51)
  • 【数据结构(一)】初识数据结构

    ❣博主主页: 33的博客❣ ▶文章专栏分类: Java从入门到精通◀ 🚚我的代码仓库: 33的代码仓库🚚 🫵🫵🫵 关注我带你学更多数据结构知识 数据结构是计算机存储,组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合,从这篇文章开始,我们将一起进入数

    2024年04月09日
    浏览(56)
  • 数据结构(王道)——数据结构之 树

           树的概念补充: 结点之间的关系描述    结点、树的属性描述: 有序树、无序树: 1、第i层至多有m^(i-1)个结点 2、高度为h的m叉树至多有(m^h-1)/(m-1)个结点   3、高度为h的m叉树至少有h个结点 高度为h,度为m的树至少有h+m-1个结点   4、具有n个结点的m叉树的最小高度

    2024年02月17日
    浏览(50)
  • 数据结构与算法 --- 数据结构绪论

    早期人们都把计算机理解为数值计算工具,就是感觉计算机当然是用来计算的,所以计算机解决问题,应该是先从具体问题中抽象出一个适当的数据模型,设计出一个解此数据模型的算法,然后再编写程序,得到一个实际的软件。 可现实中,我们更多的不是解决数值计算的问

    2024年02月14日
    浏览(53)
  • 【数据结构】数据结构中的栈

    该篇文章来了解数据结构中的 栈 ,栈与队列都为一种线性存储结构,同时栈与队列在逻辑结构上,都只能在头或者尾进行对数据的操作; 栈是一种 LIFO(Last in,First out)的结构 ,翻译过来即是 后进先出的一种结构 ;栈无论是出数据还是入数据都 只能从栈顶位置按顺序进行

    2024年02月05日
    浏览(49)
  • 数据结构初探:揭开数据结构奥秘

    🌈个人主页: 聆风吟 🔥系列专栏: 数据结构、算法模板、汇编语言 🔖少年有梦不应止于心动,更要付诸行动。      💬 文章主要介绍:本系列主要对数据结构的进行由浅入深的讲解,希望对你今后的学习有一定的帮助。如果有发现错误的地方还请在评论区告知,非

    2024年02月02日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包