计算与数据结构篇 - 栈/队列

栈这种抽象的数据结构

后进者先出，先进者后出，这就是典型的栈的结构。在生活中刷碗的时候，一摞摞盘子，小时候的玩具枪都有点类似栈这个结构。从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。

有时也有所困惑，数组和链表的结构已经非常方便快捷了，为什么还需要栈这个结构呢？栈是为当某个数据集合只涉及在一端插入和删除数据，而抽象存在的。

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

不管是顺序栈还是链式栈，我们存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。

支持动态扩容的顺序栈

如果要实现一个支持动态扩容的栈，我们只需要底层依赖一个支持动态扩容的数组就可以了。当栈满了之后，我们就申请一个更大的数组，将原来的数据搬移到新数组中。

对于出栈操作来说，我们不会涉及内存的重新申请和数据的搬移，所以出栈的时间复杂度仍然是 O(1)。但是，对于入栈操作来说，情况就不一样了。当栈中有空闲空间时，入栈操作的时间复杂度为 O(1)。但当空间不够时，就需要重新申请内存和数据搬移，所以时间复杂度就变成了 O(n)。

对列

对列也是一种特别常用的数据结构，队列跟栈一样，也是一种操作受限的线性表数据结构，两个常用的操作入队和出队，我们常会想起Redis中的list结构中的l/rpop和l/rpush方法。

用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

对于栈来说，我们只需要一个栈顶指针就可以了。但是队列需要两个指针：一个是 start 指针，指向队头；一个是 end 指针，指向队尾。

随着不停地进行入队、出队操作，start 和 end 都会持续往后移动。当 end 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了，在原定义的队列里当空间用尽，统一挪动到head位置。

下面是PHP代码实现的队列类，供大家参考：

<?php
    class Deque  
    { 
        public $queue = array(); 
        
        /**（尾部）入队  **/ 
        public function addLast($value)  
        { 
            return array_push($this->queue,$value); 
        } 
        /**（尾部）出队**/ 
        public function removeLast()  
        { 
            return array_pop($this->queue); 
        } 
        /**（头部）入队**/ 
        public function addFirst($value)  
        { 
            return array_unshift($this->queue,$value); 
        } 
        /**（头部）出队**/ 
        public function removeFirst()  
        { 
            return array_shift($this->queue); 
        } 
        /**清空队列**/ 
        public function makeEmpty()  
        { 
            unset($this->queue);
        } 
        
        /**获取列头**/
        public function getFirst()  
        { 
            return reset($this->queue); 
        } 
     
        /** 获取列尾 **/
        public function getLast()  
        { 
            return end($this->queue); 
        }
     
        /** 获取长度 **/
        public function getLength()  
        { 
            return count($this->queue); 
        }
        
    }

阻塞队列/并发队列

秒杀场景中，我们把预定商品的用户请求，放到预存的队列中，在定时任务中进行消费，实现了一个(生产-消费)的队列使用。
就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。可以有效地协调生产和消费的速度。

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