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

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

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高频算法详解;