首先呢,偶们先来回顾一下栈和队列的特征:
栈呢,只能在末端上进行操作,具有先进后出的特点。
队列呢,只能在队头删除,队尾插入,具有先进先出的特点。
偶们应该利用栈和队列的特征来解决一下几个问题:
1.使用两个栈实现一个队列
2.使用两个队列实现一个栈
3.元素出栈、入栈顺序的合法性。如入栈的序列(1,2,3,4,5),出栈序列为(4,5,3,2,1)
4.一个数组实现两个栈
5.实现一个栈,要求实现Push(出栈)、Pop(入栈)、Min(返回最小值的操作)的时间复杂度为O(1)
先来看第一个问题:
使用两个栈实现一个队列
思路:栈(先进后出) 队列(先进先出)
假设有两个栈为是s1,s2。将s1作为基础栈,而s2只是暂时维护数据栈。
若压入1,2,3。则输出的也应该是1,2,3。
“入队”:栈只能从栈顶出。所以现将s1中的数据压入s2中(如图)。
“出队”:从s2中弹出即可。
代码实现:
#includetemplate class StackToQueue//栈s1为基本栈,s2维护栈 { public: StackToQueue() :_size(0) {} public: void StackToQueuePush(const T& d)//s1入队 { s1.push(d); ++_size; } void StackToQueuePop()//s2出队 { if(s2.empty()) { while(!s1.empty())//将栈s1--->s2 { s2.push(s1.top()); s1.pop(); } } s2.pop(); --_size; } void Print() { while(!s1.empty()) { cout< s1;//使用库函数stack stack s2; size_t _size;//栈中元素个数 };
2.使用两个队列实现一个栈
思路:队列(先进先出),栈(后进先出)
队列和栈插入数据时都是在末端操作。删除数据不同,栈还是在末端操作而队列在队头操作。
假设有队列q1,q2。
“出栈”:假如现有个n数据,将数据压入q1,然后将n-1个数据弹入q2,将第n个数据弹出,此时 s1队列为空,将q2中的前n-1个数据弹入q1,将第n个弹出。此时q2队列为空,以此类推,知道弹出所有 数据。
代码实现:
templateclass QueueToStack { public: QueueToStack() :_size(0) {} public: void QueueStackPush(const T& d)//q1入栈 { q1.push(d); ++_size; } void QueueStackPop()//出栈 { size_t sz = 0; if(_size) { if(q2.empty()) { sz = _size - 1; while(sz--) { q2.push(q1.front()); q1.pop(); } q1.pop(); --_size; } else //(q1.empty()) { sz = _size - 1; while(sz--) { q1.push(q2.front()); q2.pop(); } q2.pop(); --_size; } } } size_t Size() { return _size; } T& Top()//栈顶元素 { return q1.back(); } protected: queue q1; queue q2; size_t _size;//队列中元素的个数 };
3.元素出栈、入栈顺序的合法性。如入栈的序列(1,2,3,4,5),出栈序列为(4,5,3,2,1)
看到此题,首先想到栈的特征是后进先出。这就使得栈的出栈顺序有多种。
举一个简单的例子:
假如有一个入栈序列为1,2,3。出栈序列就有1,2,3、2,1,3、3,2,1、2,3,1、1,3,2共5种。
解题思路:
若要验证出入栈的合法性。首先呢,我们应该有两个数组将入栈序列和出栈序列保存起来。假设Push数组存入栈,Pop数组存出栈。从头开始判断数据是否相同,若相同,Push和Pop数组下标加加。若不同,应将数据保存起来,以便下一次比较。这就有一个问题。如何将数据保存起来呢,还要便于取出呢?这就需要一个栈将其保存。若不相同,将其压栈。比较下一个数据,如不相同,还要将栈中的数据弹出比较,相同弹出,不同继续压栈。
代码实现:
//借助两个数组以及一个栈 #include#include bool IsVail(int *Push,int *Pop,int n) { assert(Push);//数组元素不为NULL assert(Pop); stack s; int i = 0; int j = 0; for(j=0;j 4.一个数组实现两个栈
解题思路:
(1)可将数组以奇数为下标的当为栈1,以偶数为下标的当为栈2。
(2)将数组一分为二,左边为栈1,右边为栈2。
(3)数组从左边开始为栈1,从右边开始为栈2。
分析:
思路(1),(2)虽然能解决问题,但是会浪费空间。若栈1存满,需要扩容。而栈2可能空无元素。
思路(3)可解决此缺憾。当栈1,栈2的栈顶相遇时,需要扩容。
以下用静态和动态分别实现:
(1)静态
代码实现
#define SIZE 10 templateclass ArrayToStack { public: ArrayToStack() :_top1(0)//栈1从头开始 ,_top2(SIZE-1)//栈2从尾开始 {} public: //void Push2(const T& d)//从头压栈 //{ // _a[_top1++] = d; //} //void Push3(const T& d)//从尾部压栈 //{ // _a[_top2--] = d; //} void Push(const T& d,int choice)//给标志,若choice为0,压入栈1,若为1,压入栈2 { if(choice == 0) { _a[_top1++] = d; } if(choice == 1) { _a[_top2--] = d; } } void Pop(int choice)//choice为0,弹出栈1,choice为1,弹出栈2 { if(choice == 0) { if(_top1 == 0) return; else _top1--; } if(choice == 1) { if(_top2 == 0) return; else _top2++; } } size_t size(int choice) { if(choice == 0) { return _top1; } if(choice == 1) { return _top2; } } T& Top(int choice) { if(choice == 0) { return _a[_top1]; } if(choice == 1) { return _a[_top2]; } } protected: T _a[SIZE];//数组 int _top1;//栈1的栈顶 int _top2;//栈2的栈顶 }; (2)动态
代码实现
class ArrayToStack { public: ArrayToStack() :_a(NULL) ,_top1(0) ,_top2(0) ,_capacity(0) {} ~ArrayToStack() { if(_a) { delete[] _a; } } public: void _CheckCapacity()//扩容 { if(_a == NULL) { _capacity = 3; _a = new T[_capacity]; _top1 = 0; _top2 = _capacity-1; } else { if(_top1 == _top2) { int capacity = _capacity; //保存之前的容量,在下面复制时方便找到最后一个元素 _capacity = 2*_capacity; int i = 0; int j = 0; T* tmp = new T[_capacity]; for(i=0;i<_top1;i++)//将原来的复制到新开辟的空间上 { tmp[i] = _a[i]; } int k = _capacity - 1;//扩容后的最后一位 for(j=capacity-1;j>_top2;j--) { tmp[k--] = _a[j]; } _top2 = k;//将_top2更新 delete[] _a; _a = tmp; } } } void Print() { int i = 0; int j = 0; for(i=_top1-1;i>=0;i--) { cout<<_a[i]<<" "; } cout<5.实现一个栈,要求实现Push(入栈)、Pop(出栈)、Min(返回最小值的操作)的时间复杂度为O(1)
看到此题,我们都知道Push(入栈)、Pop(出栈)的时间复杂度为O(1)。而解决此题的难点在于Min(返回最小值的操作)的时间复杂度为O(1)。我们不可能从头开始遍历,这样复杂度不可能为O(1)
解决此题的方法有如下两种:
(1)使用一个栈
每一次入栈都压两次,第一次压入原始数据,第二次压入当前栈中最小的。在第二压栈之前,需和上一次的比较,若小于则压栈,否则将上一次的再次压栈。出栈时,每次都弹出两次。
(2)使用两个栈
第一个栈用来保存原始数据,第二栈用保存当前栈中最小值。第一次两个栈中都压入,若再次压入栈,需要和当前栈2中的元素比较,若小于等于则入栈,否则只压入栈1。
分析:
若要是数据量庞大,可见第一种方法使用的空间很大。
此处实现的是第二种方法:
栈的简单实现:
templateclass Stack { public: Stack()//构造函数 :_a(NULL) ,_top(0) ,_capacity(0) {} ~Stack() { if(_a) { delete[] _a; _a = NULL; } } Stack(Stack & s) { size_t i = 0; _top = s._top; _capacity = s._top; _a = new T[_top]; for(i=0;i<_top;i++) { _a[i] = s._a[i]; } } Stack & operator=(Stack & s) { if(this != &s) { size_t i = 0; delete[] _a; _top = s._top; _capacity = s._capacity; _a = new T[_top]; for(i=0;i<_top;i++) { _a[i] = s._a[i]; } } return *this; } public: void CheckCapacity()//检容 { if(_top == _capacity) { _capacity = _capacity*2+3; T* tmp = new T[_capacity]; size_t i = 0; for(i=0;i<_top;i++) { tmp[i] = _a[i]; } delete[] _a; _a = tmp; } } public: void Push(const T& x)//插入 { CheckCapacity(); _a[_top++] = x; } void Pop()//栈顶删除 { _top--; } T& Top()//返回栈顶元素 { return _a[_top-1]; } bool Empty()//栈是否为空 { return _top == 0; } size_t Size()//元素个数 { return _top; } private: T* _a; size_t _top; size_t _capacity; }; 返回最小值操作:
templateclass StackMin { public: StackMin() :_size(0) {} public: void M_Push(const T& d) { if(s1.Empty() && s2.Empty()) { s1.Push(d); s2.Push(d); } else { if(s2.Top() < d) { s1.Push(d); } else { s1.Push(d); s2.Push(d); } } ++_size; } void M_Pop() { if(s1.Top() == s2.Top()) { s1.Pop(); s2.Pop(); } else { s1.Pop(); } --_size; } T& MinMem() { return s2.Top(); } size_t M_Size() { return _size; } protected: Stack s1;//栈1 Stack s2;//栈2 size_t _size;//栈中元素的个数 }; 创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
本文名称:栈&队列的那些应用---常见面试题-创新互联
文章出自:http://cdkjz.cn/article/digspd.html