数据结构-栈和队列（1）
文章目录
- 前言
- 一、栈
- 1、概念
- 2、实现栈
- 1.1、数组实现
- 1.2、链表实现
- 二、队列
- 1、概念
- 2、实现队列
- 2.1、数组实现
- 2.2、链表实现
- 三、小练
- 总结
前言
本篇博客的学习目标是：学习栈和队列的概念，实现方式。代码请期待下一篇博客。
一、栈
1、概念
栈：是一种特殊的线性表，它只允许在固定的一段进行插入删除操作。
栈顶和栈底：进行数据插入删除的一端叫做栈顶，另一端叫做栈底。
压栈（push）：数据插入栈叫做压栈/进栈/入栈。
出栈（pop）：数据从栈删除叫做出栈。
注意： 1、无论压栈还是出栈，都在栈顶实现。2、栈遵循：后进先出的原则。
2、实现栈
1.1、数组实现
1>、简单分析：
2>、具体实现：
1.2、链表实现
1>、双向链表实现栈
2>、单链表实现栈
二、队列
1、概念
队列：也是一种特殊的线性表，它只允许在一端插入，另一端删除。
对头队尾：删除的一端叫队头，插入的一端叫队尾。
2、实现队列
2.1、数组实现
2.2、链表实现
三、小练
总结
- 数组和链表的选择：栈用数组(顺序表)，队列用单链表(链表)。相对效率较高，空间浪费少。
- 栈和队列区别：栈是在一端进行插入删除，而队列是在一端插入，另一端删除
- 栈顶栈底和队头队尾：栈的栈顶是插入删除的一端，另一端是栈底。而队列的队头是删除一端，队尾是插入的一端。
- 栈和队列入已经出的区别：栈的入和出顺序对结果出有影响，因为它规定只在一端入栈、出栈，栈遵循后入先出。队列遵循先入先出，队列入和出的顺序对结果出不影响。
- 栈和队列实现：基本上是顺序表和链表的内容，比如压栈、出栈就是尾插、尾删。只是限制了一些条件。