【数据结构】--几道栈和队列面试题

用两个栈实现一个队列

1、思路分析 拿到这道题，会有以下几种思路： 思路一：

入队时，将所有的元素压入到s1中出队时，将s1中的所有元素倒入到s2中，然后让s2中栈顶的元素出栈，然后将s2中所有的元素倒入到s1中

问题所在：我们不难发现，在这种解法中，要进行来回倒栈，时间复杂度就会比较大，做起来也比较麻烦 思路二： 说明：是对第一种的优化我们不难发现，其实在进行倒栈的时候，没必要进行最后一个元素的倒入

入队时，先判断s1是否为空，如果不为空，说明所有的元素都在s1中，此时将入队的元素直接压入s1中；如果s1为空，将s2中所有的元素倒入到s1中，将入队的元素压入s1中出队时，如果s2不为空，将s2栈顶的元素弹出，如果s2为空，将s1中除最后一个元素压入s2中，将最后一个元素出栈

说明：这种方法其实是将两个栈更进一步的同时利用。每次出队后，并不将元素“倒回”s1，如果赶上下次还是出队操作，效率会高一些。 思路三：

入队时，将所有的元素压入s1出队时，判断s2是否为空，如果为不为空，直接将栈顶的元素弹出，如果s2为空，将s1中的元素倒入s2中，将最后一个元素弹出

2、代码实现

（说明：对第三种方法的实现） #include<iostream> #include<stack> using namespace std; template<class T> class Queue { public: Queue() {} void Push(const T& x) { s1.push(x); } void Pop() { if(s1.empty() && s2.empty()) cout<<"队列为空，无法进行删除！"<<endl; if(s2.empty()) { while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } } s1.pop(); } bool Empty() { return ((s1.empty()) && (s2.empty())); } T& Front() { if(s1.empty() && s2.empty()) { cout<<"队列为空！"<<endl; } if(s2.empty()) { while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } } return s2.top(); } private: stack<T>s1; stack<T>s2; };

---

用两个队列实现一个栈

1、思路分析 说明：队列是先进先出，栈是先进后出，因此我们在尽心出栈的时候，要将其中一个队列中的除最后一个元素先倒入到第二个队列中，然后将一个队列中的元素出队列 入队列的时候，要保证两个队列中有一个是空的出队列时，将一个不为空的队列的size-1个元素倒入另一个，然后将最后一个元素出队列2、代码实现 #include<iostream> #include<queue> using namespace std; template<class T> class Stack { public: Stack(){} void Push(const T&x) { if (q1.empty() && q2.empty()) q1.push(x); else if (!q1.empty()) q1.push(x); else q2.push(x); } void Pop() { T ret = 0; if (!q1.empty()) { while (q1.size() > 1) { T& temp = q1.front(); q1.pop(); q2.push(temp); } ret = q1.front(); q1.pop(); cout << ret << endl; } else { while (q2.size() > 1) { T& temp = q2.front(); q2.pop(); q1.push(temp); } ret = q2.front(); q2.pop(); cout << ret << endl; } } private: queue<T> q1; queue<T> q2; }; void Test() { Stack<int> s1; s1.Push(1); s1.Push(2); s1.Push(3); s1.Push(4); s1.Push(5); s1.Push(6); s1.Pop(); s1.Pop(); s1.Pop(); }

---

实现一个栈，它的push,pop,得到栈的最小元素的Min函数的操作时间复杂度都为O（1）

1、思路分析： 要得到栈的最小元素 思路一： 每次压入数的时候，将所有的数进行排序，将最小的数放在栈顶，就保证了在O（1）的时间复杂度内得到最小的元素。但是这种做法不能保证最后入栈的元素最先出栈，已经不符合栈的特点了。 思路二： 我们加入一个辅助栈，当辅助栈不为空的时候，将压入的值压入两个栈，否则将要压入的值和辅助栈的值进行比较，如果比辅助栈的值小的话，就将此值压入到辅助栈中，否则就将辅助栈栈顶的值再进行压入一次。就是说辅助栈栈顶的值一直都是最小值。

2、代码实现

#include<iostream> #include<stack> using namespace std; template<class T> class MinStack { public: MinStack(){} void Push(const T& x) { s1.push(x); if (min.empty() || x < min.top()) min.push(x); else min.push(min.top()); } void Pop() { if (!min.empty() && !s1.empty()) { s1.pop(); min.pop(); } } const T& Min()const { return min.top(); } private: stack<T> s1; stack<T> min; };

---

判断元素出栈入栈的合法性

1、思路分析 压入一个元素和给定的出栈的元素进行比较，如果相等的话，就继续往后走，直到给定的入栈序列和出栈序列完全匹配。 当入栈序列的值和出栈序列的值不相同时，继续进行入栈序列的压入，直到匹配，如果将入栈序列的值全部压入还没有和出栈序列的值相等的，就说明不匹配。2、代码实现 #include<iostream> using namespace std; #include<stack> bool Judge(int* inarr,int* outarr,int size) { stack<int> s; int i = 0; int j = 0; for(i = 0; i<size; i++) { s.push(inarr[i]); while(!s.empty() && s.top() == outarr[j]) { s.pop(); j++; } } return s.empty(); } void Test() { int inarr[5] = {1,2,3,4,5}; int outarr[5] = {4,5,3,2,1}; cout<<Judge(inarr,outarr,5)<<endl; }

---

用一个数组实现两个栈

1、思路分析 思路一：将数组的下标为0的位置当做第一个栈的栈底，下标为1的位置当做第二个栈的栈底，将数组的偶数位置看做第一个栈的存储空间，奇数位置看做第二个栈的存储空间。

思路二：从中间分别向两边压栈 将数组的中间位置看做两个栈的栈底，压栈时栈顶指针分别向两边移动，当任何一边到达数组的起始位置或是数组尾部，则开始扩容。

思路三：从两边向中间压栈 将数组的起始位置看作是第一个栈的栈底，将数组的尾部看作第二个栈的栈底，压栈时，栈顶指针分别向中间移动，直到两栈顶指针相遇，则扩容。

方案二和方案一当两栈中元素不同时，比较浪费空间，方案三节省空间 - 2、代码实现

template<class T> class TwoStack { public: TwoStack() :_a(NULL) , _top1(0) , _top2(0) , _capacity(0) { _CheckCapacity(); } ~TwoStack() { if (_a) delete[] _a; } void Push1(const T& d) { _CheckCapacity(); _a[_top1++] = d; } void Push2(const T& d) { _CheckCapacity(); _a[_top2--] = d; } void Pop1() { if (_top1 > 0) --_top1; } void Pop2() { if (_top2 < _capacity-1) _top2++; } size_t Size1() { return _top1; } size_t Size2() { return _capacity -1- _top2; } bool Empty1() { return _top1 == 0; } bool Empty2() { return _top2 == _capacity - 1; } T& Top1() { if (_top1>0) { return _a[_top1-1]; } } T& Top2() { if (_top2 < _capacity - 1) return _a[_top2+1]; } private: void _CheckCapacity() { if (_a == NULL) { _capacity += 3; _a = new T[_capacity]; _top2 = _capacity - 1; return; } if (_top1 == _top2) { size_t OldCapacity = _capacity; _capacity = _capacity * 2; T* tmp = new T[_capacity]; for (size_t i = 0; i < _top1; i++) { tmp[i] = _a[i]; } for (size_t j = OldCapacity-1,i=_capacity-1; j>_top2;j--,i--) { tmp[i] = _a[j]; } delete[] _a; _a = tmp; _top2 += _capacity / 2; } } private: T* _a; size_t _top1; size_t _top2; size_t _capacity; };

---