栈和队列

引子

在讨论栈和队列之前,需要先讨论一下数组和链表

数据结构	随机访问	查找	插入	删除
数组	1	n	n	n
链表	n	n	1	1
栈	n	n	1	1
队列	n	n	1	1

讨论以下几个问题:

• 为什么数组访问的复杂度是O(1)而链表是O(n)?

数组是连续储存的,且元素的大小固定.那么随机访问任意index,可以通过计算偏移进行寻址. 这里以c++的一段代码作为例子,js的数组是用对象实现的,不方便直观讨论.

int main(void)
{
    int array[5]; 
    void * p = &array; //0x72fe10
    int * p1 = &array[0]; //0x72fe10
    int * p2 = &array[1]; //0x72fe14
    int * p5 = &array[4]; //0x72fe20
    int * p6 = &array[5]; //0x72fe24
   return 0;
};

数组访问a[3],首先a记录了首地址&start,其次偏移量size固定,那么 a[3]的地址可以计算得出&start + 4*size,仅通过一次计算便可以访问.回顾一下在链表中getNode(index)的实现:

    getNode(index) {
        if (index >= this._length_ || index < 0) {
            throw new Error('Index out of bounds')
        }
        let node = this.head
        for (let i = 0; i < index; i++) {
            node = node.next
        }
        return node
    }

因为链表的地址是不连续的,那么要访问随机地址,就需要遍历index个节点,故复杂度为O(n)

特别的,由于头尾指针的存在,访问链表头尾的复杂度也为O(1),这也是栈和队列效率高的原因所在

• 为什么在数组中间插入和删除的复杂度是O(n) 回顾一下在二分插入排序中我们做的事情

function binaryInsertionSort<T>(nums: T[]) {
  for (let i = 0; i < nums.length; i++) {
    let [left, right] = [0, i - 1]
    while (left <= right) {
      const mid = (right + left) >> 1
      if (cmp.lt(nums[i], nums[mid])) {
        right = mid - 1
      } else {
        left = mid + 1
      }
    }

    for (let j = i - 1; j >= left; j--) {
      ;[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]]
    }
  }
  return nums
}

我们在找到待插入的位置index以后,还需要把大于index所有元素右移一位以便给待插入的元素腾出位置,删除同理.普通的插入排序也有同样的问题,移动是隐式进行的.这样的情况在链表上就不会发生,链表的插入和删除在拿到待插入删除位置的情况下只需要更改一下指向就完成了,复杂度为O(1)

• 数组链表的一点补充 因为计算机缓存的特性,读内存一一片一片读的,这会使得数组的随机访问效率更高. 数组是需要声明容量的,扩容时有开销,而链表就没有这样的问题. 链表元素随机删除要算上查找的复杂度

栈

code here Stack的原意是叠着的一摞东西,比如一堆盘子,它有自己的高度. 栈只能在尾部增删,一摞盘子只能抽走顶层的盘子让不能从中间开始. 拥有一个关键性质:LIFO(Last In First Out/后进先出) 优先访问最近操作的元素 比如普通枪的弹夹,第一发子弹必定是最后那颗被压进栈的子弹.而队列更像是左轮手枪 :) 对整个栈使用LIFO,就可以完成Stack的reverse.

队列

code here Queue,FIFO(First In First Out/先进先出),名称足够形象,不需要解释. 队列只能在队首删,在队尾增. 队列的作用是保存了入队的顺序.

双端队列

code here 如果把Stack和Queue合起来,你就得到了一个双端队列(Deque) 双端队列可以在首尾增删. 可以方便的用数组在模拟一个双端队列 即:array. push( ) pop( ) shift( ) unshift( ) 双端队列在限制使用条件的情况下可以分别当做栈和队列来使用. 如果不限制使用条件,则不能保证栈和队列创建时所隐含的顺序信息.