栈和队列的相关面试题(详解)

xiaoxiao2021-02-28  13

#include<iostream> #include<stack> #include<queue> using namespace std; //实现一个栈,要求实现Push(入栈) Pop(出栈) Min(返回最小值的操作) 时间复杂度为O(1) //方法一:用两个栈实现,先同时往s1,和min里面入第一个元素,接着s1正常入,同时_min入的时候用s1栈顶相比,如果小于s1栈顶,则就往_min里面扔原来栈里面的,否则扔s1栈顶的 template <class T> class Minstack { public: void Push(const T& x) { _s1.push(x); if (_min.empty() || x <= _min.top()) { _min.push(x); } else { _min.push(_min.top()); } } void Pop() { _min.pop(); _s1.pop(); } T& Min() { return _min.top(); } bool Empty() { if (_min.empty) { return true; } else { return false; } } protected: stack <T> _s1; stack <T> _min; }; int main() { Minstack<int> m; m.Push(10); m.Push(7); m.Push(9); m.Push(4); cout << m.Min() << endl; m.Pop(); cout << m.Min() << endl; system("pause"); return 0; } //方法二 上面的方法最小栈_min里面的数据太多 ,优化。最小栈_min里面只存小于栈顶元素,或等于栈顶元素的值,出栈时最小栈_min只出和_s栈顶相同的元素 template <class T> class MinStack { public: void Push(const T& x) { _s.push(x); if (_min.empty() || x <= _min.top()) { _min.push(x); } } void Pop() { _s.pop(); if (_s.top() == _min.top()) { _min.pop(); } } T& Min() { return _min.top(); } bool Empty() { if (_min.empty()) { return true; } else { return false; } } private: stack<int> _s; stack <int> _min; }; int main() { MinStack<int>s1; s1.Push(3); s1.Push(2); s1.Push(1); cout << s1.Min() << " "; s1.Pop(); cout << s1.Min() << " "; s1.Pop(); cout << s1.Min() << " "; system("pause"); return 0; } //方法三 引用计数(最终方法,也是最好的方法) 因为上面的方法如果连续重复的数据很多,_min栈里也就会有重复的数据,想想如果栈里存储的是结构体,也就浪费空间了 template <class T> class MinStack { public://内部类 在外面用不了除非指定这个类域 封装 struct valref { T _value; size_t _count; valref( T data) :_value(data) , _count(0) {} }; typedef struct valref valref; public: void Push(const T& x) { _s1.push(x); if (_min.empty() || x < (_min.top())._value) { _min.push(valref(x)); } else if ((_min.top())._value == x) { _min.top()._count += 1; } } void Pop() { if (_s1.top() == (_min.top())->value) { (_min.top())->count -= 1; if (_min.top()->count < 0) { _min.pop(); } _s1.pop(); } else { _s1.pop(); } } T& Min() { return (_min.top())._value; } private: stack<T> _s1; stack<valref> _min; }; int main() { MinStack<int> s; s.Push(5); s.Push(9); s.Push(3); s.Push(4); cout << s.Min() << endl; system("pause"); return 0; } //问题二 用两个栈实现一个队列 //大体思路:两个栈叫做_push,_pop,入的时候往_push这个栈里面入,出的时候往从_pop这个栈里面出,如果这个栈里面没数据了,就把_push里面的数据往_pop里面出.等到两个栈里面都没有数据就结束了 template<class T> class QueuebytwoStack { public: void Push(const T& x) { _pushs.push(x); } void Pop() { if (_pops.empty()) { while (!_pushs.empty()) { _pops.push(_pushs.top()); _pushs.pop(); } } _pops.pop(); } T& Front() { if (_pops.empty()) { while (!_pushs.empty()) { _pops.push(_pushs.top()); _pushs.pop(); } } return _pops.top(); } bool Empty() { return (_pushs.empty() && _pops.empty()); } size_t Size() { return(_pushs.size() + _pops.size()); } private: stack<int>_pushs; stack<int>_pops; }; int main() { QueuebytwoStack<int> q; q.Push(1); q.Push(2); q.Push(3); q.Push(5); q.Pop(); cout << q.Front() << endl; while (!q.Empty()) { cout << q.Front() << " "; q.Pop(); } system("pause"); return 0; } //问题三 用两个队列实现一个栈 template<class T> class StackbytwoQueue {public: void Push(const T&x) { if (!q1.empty()) { q1.push(x); } else { q2.push(x); } } void Pop() { queue<T>*pemptyQ = &q1; queue<T>*pnonemptyQ = &q2; if (!pemptyQ->empty()) { swap(pemptyQ, pnonemptyQ); } while (pnonemptyQ->size() > 1) { pemptyQ->push(pnonemptyQ->front()); pnonemptyQ->pop(); } pnonemptyQ->pop(); } T& Top() { if (!q1.empty()) { return q1.back(); } else { return q2.back(); } } bool Empty() { if (q1.empty()) { return (q2.size()==0); } else { return (q1.size() == 0); } } size_t Size() { if (q1.empty()) { return q2.size(); } else { return q1.size(); } } private: queue<T> q1; queue<T> q2; }; void test() { StackbytwoQueue<int> s; s.Push(1); s.Push(2); s.Push(3); s.Push(4); cout << s.Size() << endl; /*s.Pop(); s.Pop(); cout << s.Size() << endl;*/ while (!s.Empty()) { cout << s.Top() << " "; s.Pop(); } } int main() { test(); system("pause"); return 0; } //4.一个数组实现两个栈 #include<assert.h> template<class T> class TwoStack { public: TwoStack()//构造 :_a(new T[2]) ,_size1(0) ,_size2(1) , _capacity(2) {} void CheckCapacity() { if (_size1 == _size2) { int NewCapacity = _capacity * 2 + 3; T* tmp = new T[NewCapacity]; for (int i = 0; i < _size1; i++) { tmp[i] = _a[i]; } int j = NewCapacity - 1; for (int i =_capacity-1 ; i>=_size2 ; i--) { tmp[j] = _a[i]; --j; } _size2 =_size2+NewCapacity-_capacity; _capacity = NewCapacity; delete[] _a; _a= tmp; } } ~TwoStack() { if (_a != NULL) { delete[] _a; } _a = NULL; _size1 = 0; _size2 = 0; _capacity = 0; } void Push1(const T& x)//向栈1中插入 { CheckCapacity(); _a[_size1++] = x; } void Push2(const T& x)//向栈2中插入 { CheckCapacity(); _a[--_size2] = x; } void Pop1()//删除栈1顶元素 { assert(_size1 >= 0); _size1--; } void Pop2()//删除栈2顶元素 { assert(_size2< _capacity ); _size2++; } size_t Size1()//取栈1中元素个数 { return _size1; } size_t Size2()//取栈2中元素个数 { return _capacity - _size2-1; } T& Top1() { return _a[_size1-1]; } T& Top2() { return _a[_size2]; } bool Empty1() { return _size1 == 0; } bool Empty2() { return _size2 == _capacity-1; } private: T* _a;//数组 int _size1;//栈1的栈顶在数组中的下标 int _size2;//栈2的栈顶在数组中的下标 int _capacity; }; int main() { TwoStack<int> s; s.Push1(1); s.Push1(2); s.Push1(3); s.Push1(4); cout << s.Size1() << endl; while (!s.Empty1()) { cout << s.Top1() << " "; s.Pop1(); } cout << endl; TwoStack<int> s2; s2.Push2(1); s2.Push2(2); s2.Push2(3); s2.Push2(4); cout << s2.Size2() << endl; while (!s2.Empty2()) { cout << s2.Top2() << " "; s2.Pop2(); } system("pause"); return 0; } //5.元素出栈,入栈顺序的合法性 如:入栈的序列(1,2,3,4,5),出栈序列为(4,5,3,2,1)则合法,入栈的序列(1,2,3,4,5),出栈序列为(4,5,2,3,1)则不合法 //具体的思路:如果出栈序列中栈顶元素刚好与当前入栈的元素相等,则直接Pop出来,如果不相等则一直将入栈序列的元素往当前栈中放,直到遇见与出栈序列栈顶 //相等的,然后一起Pop。如果已经将入栈序列中的元素入完了,还是没有遇见与出栈序列栈顶的元素相同,则说明出栈序列不和法 #include<iostream> #include<assert.h> #include<vector> #include<stack> #include<queue> using namespace std; bool IsPopOrder(int* Instack, int* Outstack, int length) { if ((Instack == NULL) || (Outstack == NULL) || length <= 0) { return false; } stack<int> s; s.push(Instack[0]); int incount = 1; int outcount = 0; while (outcount<length ) { while ((Outstack[outcount] != s.top()) && (incount < length)) { s.push(Instack[incount]); incount++; } if (s.top() == Outstack[outcount]) { s.pop(); outcount++; } else { return false; } } return true; } int main() { /*int Instack[5] = { 1, 2, 3, 4, 5 }; int Outstack[5] = { 4, 5, 3, 2, 1 };*/ int Instack[5] = { 1, 2, 3, 4, 5 }; int Outstack[5] = { 4, 5, 3, 1, 2 }; cout << IsPopOrder(Instack, Outstack, 5) << endl; system("pause"); return 0; }
转载请注明原文地址: https://www.6miu.com/read-2650344.html

最新回复(0)