---
title: 栈和队列
date: 2014-01-25 16:46:13
order: 02
categories:
  - 算法
tags:
  - 数据结构
  - 线性表
  - 栈
  - 队列
permalink: /pages/4f160a46/
---

# 栈和队列

> **队列**和**栈**都是**操作受限**的**线性表**：前者先进先出，后者先进后出。

## 栈

### 栈是什么

在 **LIFO(后进先出)** 数据结构中，将首先处理添加到队列中的最新元素。

**栈是一个 LIFO(后进先出) 数据结构**。**栈是一种“操作受限”的线性表**，只允许在一端插入和删除数据。通常，插入操作在栈中被称作入栈 push 。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈 pop ，将始终删除队列中相对于它的最后一个元素。

![img](https://raw.githubusercontent.com/dunwu/images/master/snap/20220320200148.png)

**当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构**。

从栈的定义可以看出，栈只支持两个基本操作：**入栈 `push()`** 和 **出栈 `pop()`** ，也就是在栈顶插入一个数据和从栈顶删除一个数据。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 `O(1)`。

栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作**顺序栈**，用链表实现的栈，我们叫作**链式栈**。

### 为什么需要栈

相比数组和链表，栈只是对操作进行了限制，似乎并没有任何优势。为什么不直接使用数组或者链表？为什么还要用这个“操作受限”的“栈”呢？

特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。

### 栈的应用场景

（1）**函数调用栈**

![img](https://raw.githubusercontent.com/dunwu/images/master/snap/20220310091000.jpg)

（2）**表达式求值**

![img](https://raw.githubusercontent.com/dunwu/images/master/snap/20220310091100.jpg)

（3）**表达式匹配**

可以借助栈来检查表达式中的括号是否匹配

## 队列

在 FIFO 数据结构中，将首先处理添加到队列中的第一个元素。

队列是典型的 FIFO 数据结构。插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。 删除（delete）操作也被称为出队（dequeue)。 你只能移除第一个元素。

### 什么是队列

**队列：先进先出的线性表**。

**队列是一种“操作受限”的线性表**，只允许在一端插入数据，在另一端删除数据。

队列的最基本操作：**入队 `enqueue()`**，放一个数据到队列尾部；**出队 `dequeue()`**，从队列头部取一个元素。

![img](https://raw.githubusercontent.com/dunwu/images/master/snap/20220320200213.png)

队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫作**顺序队列**，用链表实现的队列叫作**链式队列**。

队满的判断条件是 `tail == n`，队空的判断条件是 `head == tail`。

### 循环队列

循环队列是一种较为特殊的队列。

循环队列的要点是确定好 **队空和队满的判定条件**。

在用数组实现的非循环队列中，队满的判断条件是 `(tail+1) % n == head`，队空的判断条件是 `head == tail`。

![img](https://raw.githubusercontent.com/dunwu/images/master/snap/20220322214822.png)

### 为什么需要队列

为什么需要队列和为什么需要栈，是同样的道理，参考 为什么需要栈

### 队列的应用场景

（1）**阻塞队列**

**阻塞队列**其实就是在队列基础上增加了阻塞操作。简单来说，就是：

- 在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；
- 如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

![img](https://raw.githubusercontent.com/dunwu/images/master/snap/20220310092908.jpg)

![img](https://raw.githubusercontent.com/dunwu/images/master/snap/20220310093026.jpg)

（2）**并发队列**

线程安全的队列我们叫作**并发队列**。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

## 参考资料

- [数据结构与算法之美](https://time.geekbang.org/column/intro/100017301)
- [Leetcode：栈和队列](https://leetcode-cn.com/leetbook/detail/queue-stack/)