我们本节主要来训练一下我们的代码基本功，我们需要实现以下三个功能。
如果你都会的话，那证明栈和队列这部分的基本功不错。
题1、用队列实现栈
可以实现用两个队列来去实现，也可以用一个队列来实现，我们这里用一个队列来实现（因为两个队列实现有手就行）
//用一个队列来实现的栈 class MyStack { public: MyStack() {} void push(int x) { int k = q.size(); q.push(x); //1、先将该元素放进来。 for(int i = 0;i < k; i++){ //2、让之前所有的元素一一出来，然后重新一一push进去。 q.push(q.front()); q.pop(); } } int pop() { int x = q.front(); q.pop(); return x; } int top() { return q.front(); } bool empty() { return q.empty(); } queue<int> q; };
核心思想就是 出来后 重新让其插进出。
由于队列的特点是可以同时对两头进行操作，所以我们就让其（一个数）转一圈再回来
题2、用栈实现队列
根据栈后进先出的特性，我们需要采取的措施就是倒栈，即把一个栈中的元素倒到另外一个栈中。
这是解决本题的核心思路。
另外，在倒栈的时候，需要注意这么几点：1、每一次倒stIn里面的元素必须要倒完。2、stOut如果不为空，绝对不可以再往其里面倒数。
所以，说人话就是：必须要stOut这个栈空了，我才让stIn倒，而要倒，我就一次性倒完。
当然了，同样可以采用类似于上面第一种题的做法，即将一个栈中的元素全部倒过来，用于存储pop后原栈中的数据。然后将新插的元素压入栈后，再将这个存储栈倒回来。
不过，这种算法在时间复杂度上为O(N)，不比上面的O(1)。
//用栈实现队列 class MyQueue { public: MyQueue() {} void push(int x) { stIn.push(x); } int pop() { if(stOut.empty()){ while(!stIn.empty()){ stOut.push(stIn.top()); stIn.pop(); } } int k = stOut.top(); stOut.pop(); return k; } int peek() { int k = pop(); stOut.push(k); return k; }bool empty() { return stIn.empty() && stOut.empty(); } stack<int> stIn; stack<int> stOut; };
题3、实现环形队列
我们可以用两种方式实现，一个是用原生数组实现；还有一种是用循环链表实现
//（1）用原生数组实现 class MyCircularQueue { public: MyCircularQueue(int k) { _capacity = k; _a = new int[_capacity]; _fast = 0; _count = 0; } bool enQueue(int value) { if(_count < _capacity){ _a[_fast++] = value; _fast %= _capacity; _count++; return true; } else return false; } bool deQueue() { if(_count > 0){ _count--; return true; } else return false; } int Front() { if(_count > 0){ int m = (_fast + _capacity - _count) % _capacity; return _a[m]; } else return -1; } int Rear() { if(_count > 0){ int k = (_fast + _capacity - 1) % _capacity; return _a[k]; } else return -1; } bool isEmpty() { return _count == 0; } bool isFull() { return _count == _capacity; } int* _a; int _capacity; int _fast; int _count; };
在这里需要注意一下几个点：
1、如果用原生数组，插入一个数，指针往后走，那么需要注意，数组的右边是队尾，左边是队头。
2、删除数据是从队头删除。
3、注意我们一直都是尾插！
//（2）用单链表实现 //实际上，单链表和循环队列基本就是一个模子。我们这里只需要再自己去定义一下容量大小就可以了。 class MyCircularQueue { public: MyCircularQueue(int k) { _capacity = k; } bool enQueue(int value) { if(_capacity > ll.size()){ ll.push_back(value); return true; } else return false; } bool deQueue() { if(ll.size() > 0){ ll.erase(ll.begin()); return true; } else return false; } int Front() { if(ll.size() == 0)return -1; return ll.front(); } int Rear() { if(ll.size() == 0)return -1; return ll.back(); }bool isEmpty() { return ll.empty(); } bool isFull() { return _capacity == ll.size(); } list<int> ll; int _capacity; };
好啦，本节的内容就到这里啦~~
