数据结构-栈和队列（1）

文章目录

前言

本篇博客的学习目标是：学习栈和队列的概念，实现方式。代码请期待下一篇博客。

一、栈

1、概念

栈：是一种特殊的线性表，它只允许在固定的一段进行插入删除操作。
栈顶和栈底：进行数据插入删除的一端叫做栈顶，另一端叫做栈底。

压栈（push）：数据插入栈叫做压栈/进栈/入栈。
出栈（pop）：数据从栈删除叫做出栈。
注意： 1、无论压栈还是出栈，都在栈顶实现。2、栈遵循：后进先出的原则。

2、实现栈

1.1、数组实现

1>、简单分析：

2>、具体实现：

1.2、链表实现

1>、双向链表实现栈

2>、单链表实现栈

二、队列

1、概念

队列：也是一种特殊的线性表，它只允许在一端插入，另一端删除。
对头队尾：删除的一端叫队头，插入的一端叫队尾。

2、实现队列

2.1、数组实现

2.2、链表实现

三、小练

总结

1. 数组和链表的选择：**栈用数组(顺序表)，队列用单链表(链表)**。相对效率较高，空间浪费少。
2. 栈和队列区别：栈是在一端进行插入删除，而队列是在一端插入，另一端删除
3. 栈顶栈底和队头队尾：栈的栈顶是插入删除的一端，另一端是栈底。而队列的队头是删除一端，队尾是插入的一端。
4. 栈和队列入已经出的区别：栈的入和出顺序对结果出有影响，因为它规定只在一端入栈、出栈，栈遵循后入先出。队列遵循先入先出，队列入和出的顺序对结果出不影响。
5. 栈和队列实现：基本上是顺序表和链表的内容，比如压栈、出栈就是尾插、尾删。只是限制了一些条件。