【STL】序列式容器--stack和queue

比眉伴天荒 2022-06-13 04:24 163阅读 0赞

【STL】常用容器总结，带有复习性质的学习更有效率；

--------------------

**【栈和队列】**

栈和队列相关的问题在面试中真的是被问的不要不要的，下面我先从栈和队列的数据结构开始复习，最后做几道栈和队列的相关面试题作为巩固；

【栈】： 一种先进后出的结构，在操作系统中应用广泛；在STL中的栈容器，底层默认是deque作为数据结构（queue也是一样），但是由于双端队列用的比较少，而且比较复杂，没有过多研究，同样list和vector都可以作为栈的底层数据结构；

栈和队列都不允许被遍历，所以都没有迭代器，栈最常见的操作就是pop和push，操作的对象都是栈顶元素；

【队列】：一种先进先出的数据结构，底层数据结构和栈一致，同时也不允许遍历，所以没有迭代器；同时队列提供队头队尾的插入和删除操作，但是可以提供的元素只有队头（front）；

上面就是栈和队列的结构总结，下面就做一些具体的例子，来更深刻的了解一下；

【两个栈实现一个队列】

#include<iostream>
    #include<stack>
    
    using namespace std;
    
    //两个栈实现一个队列（先进先出的特性）
    
    template<typename T>
    class Queue
    {
    public:
        void Push(const T& value)
        {
            s1.push(value);
        }
    
        T Pop()
        {
            if(s1.empty() && s2.empty())
                return T();
    
            if(s2.empty())
            {
                while(!s1.empty())
                {
                    s2.push(s1.top());
                    s1.pop();
                }
            }
            s2.pop();
        }
    
        T Front()
        {
            if(s1.empty() && s2.empty())
            {
                return T();
            }
            else
            {
                if(!s2.empty())
                    return s2.top();
                else
                {
                    while(!s1.empty())
                    {
                        s2.push(s1.top());
                        s1.pop();
                    }
                    return s2.top();
                }
            }
        }
    private:
        stack<T> s1;
        stack<T> s2;
    };
    
    int main()
    {
        Queue<int> q;
        for(int i = 0; i < 5; i++)
        {
            q.Push(i);
        }
    
        cout<<q.Front()<<endl;
        q.Pop();
        cout<<q.Front()<<endl;
        system("pause");
        return 0;
    }

【两个队列实现一个栈】

//两个队列实现一个栈（后进先出特性）
    #include<iostream>
    #include<queue>
    
    using namespace std;
    
    template<typename T>
    class Stack
    {
    public:
        void Push(const T& val)
        {
            if(q1.empty() && !q2.empty())
            {
                q2.push(val);
            }
            else
            {
                q1.push(val);
            }
        }
    
        void Pop()
        {
            if(q1.empty() && !q2.empty())
            {
                while(q2.size() > 1)
                {
                    q1.push(q2.front());
                    q2.pop();
                }
                q2.pop();
            }
            else if(q2.empty() && !q1.empty())
            {
                while(q1.size() > 1)
                {
                    q2.push(q1.front());
                    q1.pop();
                }
                q1.pop();
            }
            else
            {
                return;
            }
        }
    
        T top()
        {
            if(q1.empty() && q2.empty())
                return T();
            if(q1.empty())
                return q2.back();
            else
                return q1.back();
        }
    private:
        queue<T> q1;
        queue<T> q2;
    };
    
    int main()
    {
        Stack<int> s;
    
        for(int i = 0; i < 5; ++i)
        {
            s.Push(i);
        }
    
        cout<<s.top()<<endl;
        s.Pop();
        cout<<s.top()<<endl;
        system("pause");
        return 0;
    }

【判断出入栈的合法性】

#include<iostream>
    #include<vector>
    #include<stack>
    
    using namespace std;
    
    //判断出栈的合法性，没有重复元素
    template<typename T>
    bool JudgeStack(vector<T> input, vector<T> output)
    {
        stack<T> s;
        int i = 0;
        int j = 0;
    
        while(j < output.size())
        {
            while(s.empty() || s.top() != output[j])
            {
                if(i == input.size())
                return false;
                if(i == input.size())
                    break;
                s.push(input[i++]);
            }
            if(s.top() == output[j])
                s.pop();
            j++;
        }
    
        if(s.empty())
            return true;
        return false;
    }
    
    int main()
    {
        int arr[] = {
       1,2,3,6,5};
        vector<int> v1(arr, arr+5);
        int str[] = {
       3,2,5,1,6};
        vector<int> v2(str,str+5);
    
        cout<<JudgeStack(v1,v2)<<endl;
    
        return 0;
    }

【O(1)的栈】：实现一个栈，要求实现Push（入栈）、Pop（出栈）、Min（返回最小值的操作）的时间复杂度为O(1)

#include<iostream>
    #include<stack>
    
    using namespace std;
    
    template<typename T>
    class Stack
    {
    public:
        void Push(const T& val)
        {
            if(s.empty() || val < s.top())
            {
                s.push(val);
                s.push(val);
            }
            else
            {
                T tmp = s.top();
                s.push(val);
                s.push(tmp);
            }
        }
    
        void Pop()
        {
            s.pop();
            s.pop();
        }
    
        T Min()
        {
            if(!s.empty())
                return s.top();
        }
    private:
        stack<T> s;
    };
    
    int main()
    {
        Stack<int> s;
        s.Push(4);
        s.Push(3);
        s.Push(2);
        s.Push(5);
        cout<<s.Min()<<endl;
        s.Pop();
        cout<<s.Min()<<endl;
        return 0;
    }

以前写的博客链接：  
[面试题之两个队列实现一个栈][Link 1]  
[面试题之用两个栈实现一个队列][Link 2]  
[ 判断出入栈的合法性][Link 3]

[Link 1]: http://blog.csdn.net/bitboss/article/details/52526424
[Link 2]: http://blog.csdn.net/bitboss/article/details/52526553
[Link 3]: http://blog.csdn.net/bitboss/article/details/52592498