• 基本介绍
  • 四个问题
• 232
• 225

基本介绍

栈，先进后出
队列,先进先出

四个问题

1. C++中stack 是容器么？
2. 我们使用的stack是属于哪个版本的STL？
3. 我们使用的STL中stack是如何实现的？
4. stack 提供迭代器来遍历stack空间么？

首先大家要知道 栈和队列是STL（C++标准库）里面的两个数据结构。

C++标准库是有多个版本的，要知道我们使用的STL是哪个版本，才能知道对应的栈和队列的实现原理。

那么来介绍一下，三个最为普遍的STL版本：

1. HP STL 其他版本的C++ STL，一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码。

2. P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。

3. SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。

接下来介绍的栈和队列也是SGI STL里面的数据结构， 知道了使用版本，才知道对应的底层实现。

1. 栈中所有元素必须符合先进后出的原则，所以栈不提供走访功能，也不提供迭代器。不像set map中提供迭代器iterator来遍历所有元素
   栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。
   所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

232

//用两个栈来实现队列的基本功能
    stack<int> stkin;
    stack<int> stkout;
    MyQueue() {

    }
    //push就是给stkinpush一个元素
    void push(int x) {
        stkin.push(x);

    }
    //pop中
    //先将stkin的元素加入到stkout中，此时stkout的顶层元素就是
    //队列队首的元素，将stkout pop一下，再依次把stkout元素加入到
    //stkin中，完成队列元素的pop
    int pop() {
        while(!stkin.empty())
        {
            stkout.push(stkin.top());
            stkin.pop();
        }
        int x =stkout.top();
        stkout.pop();
        while(!stkout.empty())
        {
            stkin.push(stkout.top());
            stkout.pop();
        }
        return x;

    }
    //和pop同理，区别是这次的stkout不用pop
    int peek() {
        while(!stkin.empty())
        {
            stkout.push(stkin.top());
            stkin.pop();
        }
        int x =stkout.top();
        while(!stkout.empty())
        {
            stkin.push(stkout.top());
            stkout.pop();
        }
        return x;
    }
    //检测stkin是否是空
    bool empty() {
        return stkin.empty();

    }

225

//用两个队列来实现stack的功能
    queue<int> que1;
    queue<int> que2;
    MyStack() {

    }
    //que1用来push，基本存储
    void push(int x) {
        que1.push(x);

    }
    //出列的基本思想：
    /*
    获得que1的size，将size-1个元素pop到que2中暂时存储，从而获得que1队尾元素
    再将que2赋值给que1，再清空que2，完成pop
    */
    int pop() {
        int size = que1.size();
        size--;
        while (size--) { // 将que1 导入que2，但要留下最后一个元素
            que2.push(que1.front());
            que1.pop();
        }

        int result = que1.front(); // 留下的最后一个元素就是要返回的值
        que1.pop();
        que1 = que2;            // 再将que2赋值给que1
        while (!que2.empty()) { // 清空que2
            que2.pop();
        }
        return result;

    }
    //STL提供back来获得队尾元素
    int top() {
        return que1.back();

    }
    
    bool empty() {
        return  que1.empty();
    }