算法基础：基本数据结构的特点：队列 vs 栈

╰半橙微兮° 2022-11-29 03:11 83阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center_pic_center]  
这篇文章介绍一下基本数据结构中队列和栈的特点和复杂度。

# 线性结构 vs 非线性结构 #

相较于前文中提到的数组和链表，队列和栈都是线性结构的数据结构。数组和链表的区别之一就在于存储方式上是顺序还是链式（随机），而线性和非线性则从数据的逻辑特性上来分类的，比如队列主要满足先进先出，栈满足后进先出，而实现上使用数组还是链表则都是可以的，具体可以进一步根据前文对于链表和数组的分析来使用。

# 队列（Queue） #

## 特点 ##

队列也是最为常见的一种数据结构，队列中的元素满足FIFO（先进先出）

*  元素需满足FIFO：First In First Out
 *  出口端称为队头（Front），入口端称为队尾（Rear）
 *  可以使用数组或者链表来存储数据
 *  操作主要有入队（Enqueue）和出队（Dequeue）
 *  可以根据需要实现循环队列或者双向队列
 *  只能在队尾插入数据，在队头删除数据

## 实现方式 ##

*  数组方式：使用数组方式实现队列，下标0的元素为队头，最后一个元素之后的数组下标为队尾，队尾元素体现为第一个未保存数据的位置，因此实际的数据容量为数组的长度-1
 *  链表方式：使用链表方式实现队列，第一个元素为队头，最后一个元素的next为NULL，队尾元素体现为节点的next指针为NULL的元素，以方便遍历

## 操作说明 ##

### 入队（Enqueue） ###

在队尾插入数据的操作被称为Enqueue，随着新元素的插入，队尾不断后移

### 出队（Dequeue） ###

在队头删除数据的操作被称为Dequeue，随着原有数据的删除，队头不断后移

## 时间复杂度 ##

由于实现方式上可以使用链表或者数组，虽然实现方式不同，不考虑数据元素的查找，入队和出队本身都和队列的长度呈现无关的特性，操作本身的时间复杂度为O(1)

## 循环队列 ##

以数组方式实现的队列为例进行说明，当连续多次执行入队出队操作时，可能会出现对头前已空出多个未保存的数据，而队尾已到数组的尾部，这种情况之下，可以考虑时使用队头前面未使用的空间，这种就是所谓的循环队列的实现示例。需要考虑的是循环队列已满的情况：

> 判断条件: 数组方式下，在顺序存储上，队尾当前已经和队头连起来了，队尾的下一个数据即是队头，比如可以表现为：(队尾下标 + 1)%队列长度 = 队头下标

# 栈（Stack） #

## 特点 ##

栈也是最为常见的一种数据结构，队列中的元素满足FILO（先进后出）

*  元素需满足FILO：First In Last Out
 *  最后元素保存的位置称为栈顶（top），最早元素保存的位置称为栈底（bottom）
 *  可以使用数组或者链表来存储数据
 *  操作主要有压栈（push）和弹栈（pop）
 *  只能在栈底进行数据插入数据和删除

## 实现方式 ##

*  数组方式：使用数组方式实现栈，下标0的元素为栈底，最后一个元素之后的数组下标为栈顶，尾部元素体现为第一个未保存数据的位置
 *  链表方式：使用链表方式实现栈，第一个元素为栈底，最后一个元素的next为NULL，栈顶体现为节点的next指针为NULL的元素

## 操作说明 ##

### 压栈（push） ###

新元素只能在栈顶不断插入，新的元素的位置成为新的栈顶

### 弹栈（pop） ###

弹栈操作实际就是删除操作也只能在栈顶进行，弹栈之后的元素的位置成为新的栈顶

## 时间复杂度 ##

不考虑查找的过程，无论那种实现，弹栈操作和压栈操作本身的时间复杂度都是O(1)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center_pic_center]: /images/20221124/79d23e95c8714381bc6dc70b3ba998c6.png