| title | date | order | categories | tags | permalink | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
栈和队列 |
2014-01-25 08:46:13 -0800 |
2 |
|
|
/pages/dd3588/ |
队列和栈都是操作受限的线性表：前者先进先出，后者先进后出。
在 LIFO(后进先出) 数据结构中，将首先处理添加到队列中的最新元素。
栈是一个 LIFO(后进先出) 数据结构。栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。通常，插入操作在栈中被称作入栈 push 。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈 pop ，将始终删除队列中相对于它的最后一个元素。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。
从栈的定义可以看出，栈只支持两个基本操作：入栈 push() 和 出栈 pop() ，也就是在栈顶插入一个数据和从栈顶删除一个数据。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。
栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。
相比数组和链表，栈只是对操作进行了限制，似乎并没有任何优势。为什么不直接使用数组或者链表？为什么还要用这个“操作受限”的“栈”呢？
特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。
（1）函数调用栈
（2）表达式求值
（3）表达式匹配
可以借助栈来检查表达式中的括号是否匹配
在 FIFO 数据结构中，将首先处理添加到队列中的第一个元素。
队列是典型的 FIFO 数据结构。插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。 删除（delete）操作也被称为出队（dequeue)。 你只能移除第一个元素。
队列：先进先出的线性表。
队列是一种“操作受限”的线性表，只允许在一端插入数据，在另一端删除数据。
队列的最基本操作：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。
队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
队满的判断条件是 tail == n，队空的判断条件是 head == tail。
循环队列是一种较为特殊的队列。
循环队列的要点是确定好 队空和队满的判定条件。
在用数组实现的非循环队列中，队满的判断条件是 (tail+1) % n == head，队空的判断条件是 head == tail。
为什么需要队列和为什么需要栈，是同样的道理，参考 为什么需要栈
（1）阻塞队列
阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是：
- 在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；
- 如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
（2）并发队列
线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。