最强梳理！堆栈和队列的区别

堆栈和队列在数据结构中是最基础，但同时也是最重要的概念，很多小伙伴对两者不是很了解，本文就言简意赅的带大家了解一下堆栈和队列。

栈与队列是两种重要的特殊线性表，从结构上讲，两者都是线性表，但从操作上讲，两者支持的基本操作却只是线性表操作的子集，是操作受限制的线性表。栈与队列两者最大的区别在于，栈元素后进先出(LIFO，Last In First Out)，而队列元素先进先出(FIFO，First In First Out)。此外，针对队列这一特殊数据结构，有时需考虑队列元素的优先级的关系，即根据用户自定义的优先级排序，出队时优先弹出优先级更高(低)的元素，优先队列能更好地满足实际问题中的需求，而在优先队列的各种实现中，堆是一种最高效的数据结构。本文分别介绍了顺序栈、链式栈、链式队列和循环队列以及对应与前两种队列实现的最大/最小优先级队列，还有两种堆结构，最大堆与最小堆的基本结构，并给出了相应的C++类代码实现。

栈(Stack)

栈是限定只能在表头进行插入(入栈)与删除(出栈)操作的线性表，表头端称为栈顶，表尾端称为栈底。

设有栈 $S=(a_1, a_2,…, a_n)$ ，则一般称 $a_1$ 为栈底元素，$a_n$为栈顶元素，按 $a_1, a_2,…,a_n$ 的顺序依次进栈，则根据元素入栈的规定，从栈顶到栈底的元素依次为 $a_n,…,a_2, a_1$，出栈时弹出的第一个元素为栈顶元素，即 $a_n$，也就是说栈是按后进先出的原则进行。故，栈可称为后进先出(Last In First Out, LIFO)的线性表。

栈有顺序表和链表两种实现方式。

顺序栈(Sequence Stack)

在顺序实现中，利用一组地址连续的存储单元即数组依次存放从栈底到栈顶的数据元素，将数据类型为ElemType的数据元素存放在数组中，并用count存储数组中存储的栈的实际元素个数。每次插入新的栈顶元素，如栈未满，则操作成功，count值加一，而当删除栈顶元素时，如栈不空，操作成功，并且count值减一。

队列是一种先进先出(First In First Out，FIFO)的线性表，只允许在一端进行插入(入队)操作，而在另一端进行删除(出队)操作。

在队列中，允许入队操作的一端称为队尾，允许出队操作的一端称为队头。

设有队列 $q=(a_1, a_2,…,a_n)$，则 $a_1$ 称为队头元素，$a_n$ 称为队尾元素，队列中元素是按 $a_1, a_2,…,a_n$ 的顺序入队，同时也要求按照相同的顺序出队。

队列也有两种存储结构：顺序存储结构和链式存储结构。

一、什么是堆栈?

堆栈是一种线性数据结构，遵循后进先出即LIFO规则：添加到堆栈的第一个元素是最后一个要删除的元素，而添加到堆栈的最后一个元素是第一个要删除的元素。

栈

知识点概述

后进先出(Last In First Out，LIFO)的线性序列，称为“栈”。栈也是一种线性表，只不过它是操作受限的线性表，只能在一端进出操作。进出的一端称为栈顶(top)，另一端称为栈底(base)。栈可以用顺序存储，也可以用链式存储，分别称为顺序栈和链栈。

堆栈

堆栈的定义及基本运算

堆栈简称为栈，是限定只能在表的一端进行插入和删除操作的线性表。在表中，允许插入和删除的一端称作“栈顶”，另一端称作“栈底”。通常将元素插入栈顶的操称作为“入栈”(进栈或压栈)，称删除栈顶元素的操作为“出栈”)表

在堆栈结构中有两种操作：

push

pop

1.1 push

push，将元素存储到堆栈上，如图所示，将3存到堆栈上。

1.2 pop

pop，从堆栈中移除一个元素，如图所示，将3从堆栈上移除。

二、什么是队列?

队列是一种抽象数据类型和线性数据结构，基于FIFO(先进先出)，即先插入的元素将在队列中最先被访问。

队列包含两种操作：

enqueue

dequeue

2.1 enqueue

enqueue，将数据存储到队列中，如图所示，将12存到队列中。

2.2 dequeue

dequeue，将数据从队列中移除，如图，将10从队列中移除。

三、堆栈和队列的区别

3.1 工作原则

堆栈：遵循后进先出 (LIFO) 原则，最后插入的元素首先被删除。

队列：遵循先进先出 (FIFO) 原则，第一个添加的元素首先从列表中删除。

3.2 操作

堆栈：

队列：

3.3 工作原则

堆栈：pop 操作用于从堆栈中删除元素，而 push 操作用于将元素插入堆栈中。

队列：dequeue出队操作从队列中删除元素，enqueue入队操作将元素插入队列。

3.4 类型

堆栈：没有任何类型。

队列：分为三种类型：循环队列、优先队列、双端队列。

3.5 使用场景

堆栈：用于解决递归问题。

队列：用于解决具有顺序处理的问题。

3.6 线性集合

堆栈：垂直。

队列：水平。

四、堆栈和队列相似之处

4.1 线性数据结构

堆栈和队列都是线性数据结构，这意味着元素是按顺序存储的，并且在一次运行中访问。

4.2 大小灵活

堆栈和队列的大小都是灵活的，这意味着它们可以根据运行时的要求进行增长和收缩。

总结

堆栈和队列是比较常见的数据结构，本文用精简的语言解释了什么是堆栈以及什么是队列，最后还进行了比较，至于到底使用堆栈还是使用队列，还是要看场景，具体问题具体分析。