数据结构第三章栈和队列（1）定义和特点

数据结构

⚡️数据结构-第一章
⚡️抽象数据类型案例
⚡️数据结构-第二章&＃xff08;1&＃xff09;-线性结构
⚡️数据结构-第二章&＃xff08;2&＃xff09;-线性表的顺序表示和实现
⚡️数据结构-第二章&＃xff08;3&＃xff09;-顺序表&＃xff08;含代码&＃xff09;
⚡️数据结构-第二章&＃xff08;4&＃xff09;-顺序表案例&＃xff08;含代码&＃xff09;
⚡️数据结构-第二章&＃xff08;5&＃xff09;-链式存储结构
⚡️数据结构-第二章&＃xff08;6&＃xff09;-单链表基本操作的实现
⚡️数据结构-第二章&＃xff08;7&＃xff09;-双向链表和循环链表
⚡️数据结构-第二章&＃xff08;8&＃xff09;-线性表的应用&＃xff08;线性表合并&＃xff09;

前言

  栈和队列是两种重要的线性结构。从数据结构角度看&＃xff0c;栈和队列也是线性表&＃xff0c;但她们是受限的线性表。

栈&＃xff1a;只能在队尾插入&＃xff0c;只能在队尾删除。

队列&＃xff1a;只能在队尾插入&＃xff0c;只能在队头删除。

  如下图&＃xff0c;我们可以将栈想象成手电筒放电池的部分、子弹匣等&＃xff0c;为什么呢&＃xff1f;我们以子弹匣为例&＃xff0c;子弹只能从弹匣尾部放入&＃xff0c;也只能从弹匣尾部弹出。栈就是这个原理&＃xff1a;只能从队尾插入&＃xff0c;也只能从队尾删除。

  如下图&＃xff0c;我们可以将队列想象成人在排队面试&＃xff0c;为什么呢&＃xff1f;你想一群人排队面试&＃xff0c;前面的人很定先面试&＃xff0c;也先走&＃xff0c;来了一个人要排队&＃xff0c;必须排在队尾&＃xff0c;对吧。队列就是这个原理&＃xff1a;只能从队尾插入&＃xff0c;只能从队头删除。

一、栈的定义和特点

栈的定义&＃xff1a;

  栈&＃xff08;stack&＃xff09;是限定在表尾进行插入或删除操作的线性表。因此&＃xff0c;对栈来说&＃xff0c;表尾端有着特殊的含义&＃xff0c;称为“栈顶&＃xff08;top&＃xff09;”&＃xff0c;相应地&＃xff0c;表头端称为栈底&＃xff08;bottom&＃xff09;&＃xff0c;不含元素的栈称为空栈。

栈的特点&＃xff1a;

  如下图所示&＃xff1a;栈的修改是按后进先出的原则进行的&＃xff0c;因此栈又称为后进先出&＃xff08;last in first out&＃xff09;的线性表&＃xff08;简称LIFO结构&＃xff09;

栈和一般线性表对比&＃xff1a;

二、队列的定义和特点

队列的定义&＃xff1a;

  和栈相反&＃xff0c;队列&＃xff08;queue&＃xff09;是一种先进先出&＃xff08;first in first out&＃xff09;简称FIFO的线性表。它是只允许在表的一端进行插入&＃xff0c;在另外一端删除的数据结构。
在队列中&＃xff0c;允许插入的一端叫做队尾&＃xff08;rear&＃xff09;&＃xff0c;允许删除的一端则称为队头&＃xff08;front&＃xff09;。

三、栈和队列的应用案例

3.1 进制转换&＃xff08;栈&＃xff09;

3.2 括号匹配的检验&＃xff08;栈&＃xff09;

3.3 表达式求值&＃xff08;栈&＃xff09;

3.4 舞伴问题&＃xff08;栈&＃xff09;

总结

期待大家和我交流&＃xff0c;留言或者私信&＃xff0c;一起学习&＃xff0c;一起进步&＃xff01;