数据结构第2章 栈和队列

发布时间:2024年01月03日

名人说:莫听穿林打叶声,何妨吟啸且徐行。—— 苏轼《定风波·莫听穿林打叶声》
本篇笔记整理:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊)

0、思维导图

在这里插入图片描述

栈和队列

1、栈

栈是一种遵循后进先出(LIFO,Last In First Out)原则的数据结构。可以想象成一摞盘子,最后放上去的盘子会最先拿掉。
在这里插入图片描述

1)特点

“后进先出(LIFO)”
在这里插入图片描述

2)分类

①顺序栈
在这里插入图片描述

采用顺序存储的栈结构。

  • 1??入栈和出栈
    在这里插入图片描述

  • 2??判断栈满空

    说明:栈顶指针top表示当前栈顶元素的位置、MAXSIZE是数组容量大小。

    • a.满:top == MAXSIZE - 1

    • b.空:top == -1

②链栈

采用链式存储的栈结构
在这里插入图片描述

  • a.入栈和出栈

在这里插入图片描述

  • b.判断栈满空

    说明:top为栈顶指针

    • 栈满:一般不存在此类情况

    • 栈空:top == NULL

③共享栈
共享栈通常是指在程序设计中,多个线程共享同一个栈空间的概念,如下图,两个顺序栈共享内存空间。
在这里插入图片描述

判断栈空、栈满

  • 栈空:top0=-l 时0号栈为空,topl=MaxSize时1号栈空;
  • 栈满:两个栈顶指针相邻(topl-top0=l)。时

3)应用

①函数调用(一般递归较为常见)

②表达式求值
在这里插入图片描述

  • 前缀表达式

    • 运算符位于操作数之前
  • 中缀表达式

    • 运算符位于操作数之间
  • 后缀表达式

    • 运算符位于操作数之后
  • 前中后缀转换

    • 1??中缀转前缀

      • 转换步骤

        • 1、加括号

        • 2、前移运算符

        • 3、去括号

      • 举例在这里插入图片描述

    • 2??中缀转后缀

      • 转换步骤

        • 1、加括号

        • 2、后移运算符

        • 3、去括号

    • 举例在这里插入图片描述

③括号匹配

在这里插入图片描述

④深度优先搜索

2、队列

队列是一种遵循先进先出(FIFO,First In First Out)原则的数据结构。可以想象成排队买票,最先排队的人最先买到票。

在这里插入图片描述

1)特点

“ 先进先出(FIFO)”
在这里插入图片描述

2)分类

①顺序队列

使用顺序存储的队列结构

  • 入队和出队
    在这里插入图片描述

  • 判断满与空

    • 队头指针front和队尾指针rear分别指示当前队头元素和队尾元素的位置

    • 满:rear == MAXSIZE - 1

    • 空:front == rear

②循环队列

队列的头尾相接的顺序队列结构
在这里插入图片描述

  • 判断满与空

    • 队头指针front和队尾指针rear分别指示当前队头元素和队尾元素的位置。Maxsize指队列的数组大小。

    • 满:(rear + 1) % Maxsize == front,其中%表示取模运算。

    • 空:front == rear。

    • 元素个数:(rear - front + Maxsize) % Maxsize

③链式队列

使用链式存储的队列结构
在这里插入图片描述

  • 判断满与空

    说明:头指针front和尾指针rear分别指向当前队头元素和队尾元素。

    • 满:一般不存在此类情况
    • 空:front == NULL且rear == NULL。

④双端队列
两端都可以进行入队和出队操作的队列
在这里插入图片描述

  • 输出受限的双端队列

    • 一端可插入和删除,另一端只允许插入
      在这里插入图片描述
  • 输入受限的双端队列

    • 一端可进行插入和删除,另一端只允许删除
      在这里插入图片描述

3)应用

①层次遍历

②计算机系统

  • 资源管理

  • 消息缓冲

  • 页面替换算法

③广度优先搜索

上述内容笔记部分图片来源网络,侵删。
参考内容:
1.《王道数据结构》
2.【LeetCode】括号匹配问题
3.数据结构电子讲义
4.数据结构共享栈

Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder)
点赞加关注,收藏不迷路!本篇文章对你有帮助的话,还请多多点赞支持!

文章来源:https://blog.csdn.net/qq_51646682/article/details/135314756
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。