面试经典算法-栈与队列

在互联网招聘的面试环节中，手撕算法环节往往会与数据结构的考察相结合。各种经典的算法都离不开常用数据结构的支持。在之前的分享中，我们对链表结构进行了分析，由浅入深的掌握了链表的基本操作和变形算法。

今天，我们同样将从最基础的数据结构栈与队列出发，挖掘常见线性结构的处理思想。

1 结构定义

栈

栈也叫堆栈，是一种在操作系统以及CPU指令设计中经常使用的数据结构。由于栈对线性存储元素的受限操作，使得其能够在很多程序设计的场景中获得特殊的效用。

栈的特点可以总结为四个字“先进后出”，意味着最先存入栈中的元素最后才能被取出。栈的基本操作有入栈（PUSH）和出栈（POP），分别代表着存值与取值。同时，每个栈都有一个指针TOP，指向栈顶元素。栈规定只能在栈顶进行插入和删除以及取栈顶元素。栈的插值与删除示例可见下图。

在C++ STL中为我们方便的封装好了模板<stack>，同时还有对栈的一系列常用操作：

stack<int> s; //栈的定义
s.empty(); //如果栈为空返回true，否则返回false  
s.size(); //返回栈中元素的个数  
s.pop(); //删除栈顶元素但不返回其值  
s.top(); //返回栈顶的元素，但不删除该元素  
s.push(X); //在栈顶压入新元素，参数X为要压入的元素

队列

队列是一种和栈十分类似的线性结构，根本区别在于插值与取值的位置不同。栈可以看作是半封闭式的结构，元素的进出只能在栈顶一个方向；而队列可看作是中通的结构，如流水线式，一方进，一方出。因此队列的特征总结为四个字即为“先进先出”。

队列为表征头尾，有两个指针队头（FRONT）与队尾（REAR）分别指向队列插入和删除的位置。其插入和删除的示例如下图。

在C++ STL中同样为我们方便的封装好了模板<queue>，同时还有对队列的一系列常用操作：

queue<int> q; //队列的定义
q.empty(); // 如果队列为空返回true，否则返回false  
q.size();  //返回队列中元素的个数  
q.pop();  //删除队列首元素但不返回其值  
q.front(); // 返回队首元素的值，但不删除该元素  
q.push(X); //在队尾压入新元素，X为要压入的元素
q.back(); //返回队列尾元素的值，但不删除该元素

2 高频算法

0x00 Leetcode 115 最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。

解题思路

这是一道比较基础的题，重点是掌握出入栈的顺序。首先分析题目，需要在常数时间内检索到最小元素，我们知道单个元素出栈本身就已经是常数时间。这意味着要在栈顶存放最小元素。

因此可以先设置一个存储栈用于存放所有的元素；此外还需设置一个辅助栈来存放当前存储栈中所有元素的最小值。如此一来，即可通过取出辅助栈栈顶的元素获得存储栈中的最小值。

代码流程：（以插入序列4 3 2 5 6为例）

PUSH操作

01 初始判断。若存储栈为空，则说明第一个入栈的元素就是最小元素。此时存储栈与辅助栈都需要插入新元素。插入4：

02 若存储栈不为空，则判断新元素与辅助栈栈顶元素的大小。若新元素比辅助栈栈顶元素大，则只需在存储栈中插入新元素；若新元素比辅助栈栈顶元素小或相等，说明新元素为新的最小值，则需要在存储栈和辅助栈中同时插入新元素。

03 重复执行02，可得：

POP操作
判断存储栈栈顶元素与辅助栈栈顶元素是否相等，如若相等，则两个栈栈顶元素都需要删去；否则，只需要删去存储栈中栈顶元素即可。

C++代码

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> stack1;
    stack<int> stack2;

    void push(int x) {
        if(stack2.empty())
            stack2.push(x);
        else if(x <= stack2.top())
            stack2.push(x);
        stack1.push(x);
    }

    void pop() {
        if(stack2.top() == stack1.top())
            stack2.pop();
        stack1.pop();
    }

    int top() {
        return stack1.top();
    }

    int getMin() {
        return stack2.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

0x01 Leetcode 225 用队列实现栈

使用队列实现栈的下列操作：
push(x) -- 元素x入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空

解题思路
这题思路可参考上题，同样也需要借助另个辅助队列用于临时元素的存储。实现过程可见动画：
01 删除栈顶元素

02 栈顶插入元素

C++代码

class MyStack {
public:
    MyStack() {        
    }
    void push(int x) {
        std::queue<int> temp;
        temp.push(x);
        while(!data.empty()){
            temp.push(data.front());
            data.pop();
        }
        while(!temp.empty()){
            data.push(temp.front());
            temp.pop();
        }
    }
    int pop() {
        int x = data.front();
        data.pop();
        return x;
    }
    int top() {
        return data.front();
    }
    bool empty() {
        return data.empty();
    }
private:
    std::queue<int> data;
};

0x02 Leetcode 232 用栈实现队列

使用栈实现的队列下列操作：
push(x) -- 将一个元素放入队列的尾部
pop() -- 从队列首部移除元素
peek() -- 返回队列首部的元素
empty() -- 返回队列是否为空

解题思路
思路与上题类似，同样是两个过程：
01 删除队列头部元素；

02 队列尾部插入元素；

C++代码

class MyQueue {
public:
    MyQueue() {
    }
    void push(int x) {
        std::stack<int> temp_stack;
        while(!data.empty()){
            temp_stack.push(data.top());
            data.pop();
        }
        temp_stack.push(x);
        while(!temp_stack.empty()){
            data.push(temp_stack.top());
            temp_stack.pop();
        }
    }
    int pop() {
        int x = data.top();
        data.pop();
        return x;
    }
    int peek() {
        return data.top();
    }
    bool empty() {
        return data.empty();
    }
private:
    std::stack<int> data;
};

3 总结

栈和队列是最基础的数据结构之一，但是越基础的东西有时候反而越能产生妙用。上面三个算法的难度虽然都不大，但是其中却蕴含了对于线性表的充分理解。很多复杂的机制内部或许都是采用了比较简洁的转换，在不同场景下越基础的结构或许越能够带来性能上的提升。

本来堆应该也放在这一篇中来讲的，但是堆涉及到二叉树的一些定义，所以打算放到下一篇跟二叉树一起讲。就酱，拜拜～

关注我的公众号：
回复【秋招】可获得计算机基础知识总结资料；
回复【算法】可获得BAT高频算法详解；