数据结构：第十七节-初识栈与队列

栈是一种特殊的线性表，具有后进先出（LIFO，Last In First Out）的特性。类似现实生活当中在餐桌上的一摞盘子，只能在盘堆的顶端进行放和拿。

栈具有以下的特点：

1.后进先出（LIFO）：栈中最后插入的元素将会最先被移除。

2.只允许在栈顶操作：栈的基本操作包括压栈（Push）和弹栈（Pop）。压栈操作将元素添加到栈顶，弹栈操作将栈顶元素移除并返回。

3.操作受限：除了压栈和弹栈操作外，栈不允许随机访问或插入、删除中间元素。

4.栈的应用：栈常用于需要临时保存数据并按照相反的顺序访问的情况，如递归函数调用、表达式求值等。

5.时间复杂度：栈的基本操作的时间复杂度通常是 O(1)，即常数时间复杂度。

现在我们思考一个问题，假设有a,b,c三个元素按顺序入栈，有几种出栈方式呢？

有五种出栈方式：

1.c、b、a 出栈：

依次将元素a、b、c都入栈，再依次将栈顶元素c、b、a都出栈。

2.b、c、a 出栈：

先将元素a、b都入栈，再把栈顶元素b出栈，再将c入栈，依次将栈顶元素c、a出栈。

3.b、a、c 出栈：

先将元素a、b入栈，再将栈顶元素b、a出栈，然后将c入栈再出栈。

4.a、b、c 出栈：

将单个a、b、c分别入栈后出栈。

5.a、c、b 出栈：

先将元素 a 入栈再出栈，再将b、c入栈，再依次将栈顶元素c、b 出栈。

栈可以分为以下几个类型：

1.顺序栈：使用数组实现的栈，通常具有固定大小的容量，因此是静态线性表，在顺序栈中，栈的元素在内存中是连续存储的。

2.链式栈：使用链表实现的栈，可以动态地分配内存空间。链式栈中的元素由节点构成，每个节点包含数据和指向下一个节点的指针。

3.动态扩容栈：在顺序栈的基础上增加了动态扩容的能力。当栈满时，会自动分配更大的内存空间，并将原有元素复制到新的内存空间中。

4.双向栈：具有两个栈顶，分别从两端进行入栈和出栈操作。双向栈可以用于一些特定的应用场景，例如双向队列。

5.并行栈：允许同时进行多个栈的入栈和出栈操作。并行栈通常用于并行计算或多线程编程中。

队列也是一种特殊的线性表，具有先进先出（FIFO）的特性。顾名思义，队列就像我们现实当中排队结账，先排的先出。

队列具有以下特点：

1.先进先出（FIFO）：队列中最先插入的元素将会最先被移除。

2.只允许在队首和队尾操作：队列的基本操作包括入队和出队。入队操作将元素添加到队列的尾部，出队操作将队列头部的元素移除并返回。

3.操作受限：除了入队和出队操作外，队列不允许随机访问或在中间插入或删除元素。

4.队列的应用：队列常用于需要按照先后顺序处理数据的情况，如任务调度、消息队列，缓冲区管理等。

5.时间复杂度：队列的基本操作的时间复杂度通常是 O(1)，即常数时间复杂度。

队列可以分为以下几个类型：

1.普通队列：普通队列是最常见的队列类型，可以使用数组或链表来实现，支持基本的入队和出队操作。

2.双端队列：双端队列允许在队列的两端进行入队和出队操作，可以使用数组或链表来实现。它提供了队列和栈的功能，可以在队列的两端执行入队和出队操作。

3.循环队列：循环队列是一种环形结构的队列，通过循环利用数组空间来实现。当队列尾部达到数组末尾时，循环队列会将尾部指针移到数组的开头，实现循环利用。提高了数组空间的利用率，避免了因连续入队导致的队列空间耗尽的问题。

4.优先级队列：优先级队列是一种特殊的队列，其中的元素按照优先级顺序排列。具有最高优先级的元素最先出队，可以使用堆（Heap）等数据结构来实现。

5.阻塞队列：阻塞队列是一种特殊的队列，当队列为空时，出队操作会被阻塞直到队列中有元素。当队列已满时，入队操作也会被阻塞直到队列有空闲空间。通常用于多线程编程中的生产者-消费者模式。

6.并发队列：并发队列是一种线程安全的队列，支持多个线程同时进行入队和出队操作。使用锁或无锁等技术来保证线程安全性。

这节我们先简单介绍栈和队列的定义及分类，感谢观看！欢迎各位的点赞与关注！您的点赞和关注是我学习更新的动力！如有问题，可下方留言！