作为一名程序猿，想在面试的时候游刃有余，首先要熟练掌握数组、字符串、链表、树、栈、队列这几种基础的数据结构。
1 栈与队列
栈是一个非常常见的数据结构，其特点是先进后出，操作系统在函数调用便会使用栈结构。
栈是一个不考虑排序的数据结构，因此查找最大最小元素的时间复杂度为 O(n)，若想要在 O(1) 时间内得到栈的最大最小值，则需要对栈做特殊的设计。
与栈不同的是，队列是先进先出，虽然这两个数据结构看起来针锋相对，但其实他们两个可以相互实现，可以用两个栈实现队列：
-
设置一个插入栈 A（先进后出），一个弹出栈 B（先进后出）；
-
若要插入元素，直接插入到队列 A 中；
-
若要弹出元素，（1）若弹出栈 B 中有元素，则弹出栈顶元素；（2）若弹出栈 B 为空，则将插入栈 A 中的元素依次插入 B 中，此时，若 B 不为空则弹出栈顶元素，否则抛出异常。
也可以用两个队列实现栈：
-
设置两个空队列；
-
若要插入元素，选择非空队列插入元素，若两个都是空队列则随机选一个；
-
若要弹出元素，将非空队列的元素（除最后一个元素外）依次插入到空队列中，然后将最后一个元素弹出。
