首先呢,偶们先来回顾一下栈和队列的特征:
栈呢,只能在末端上进行操作,具有先进后出的特点。
队列呢,只能在队头删除,队尾插入,具有先进先出的特点。
偶们应该利用栈和队列的特征来解决一下几个问题:
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中弹出即可。
代码实现:
#include <stack>
template <class T>
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.top()<<" ";
s1.pop();
}
while(!s2.empty())
{
cout<<s2.top()<<" ";
s2.pop();
}
}
size_t Size()
{
return _size;
}
T& Back()
{
if(s2.empty())
{
return s1.top();
}
else
{
return s2.end();
}
}
T& Front()
{
if(s1.empty())
{
return s2.top();
}
else
{
return s1.end();
}
}
bool Empty()
{
return _size==0;
}
T& Top()
{
if(!s1.empty())
{
return s1.top();
}
else
{
return s2.top();
}
}
void Pop()
{
s1.pop();
--_size;
}
protected:
stack<int> s1;//使用库函数stack
stack<int> s2;
size_t _size;//栈中元素个数
};
2.使用两个队列实现一个栈
思路:队列(先进先出),栈(后进先出)
队列和栈插入数据时都是在末端操作。删除数据不同,栈还是在末端操作而队列在队头操作。
假设有队列q1,q2。
“出栈”:假如现有个n数据,将数据压入q1,然后将n-1个数据弹入q2,将第n个数据弹出,此时 s1队列为空,将q2中的前n-1个数据弹入q1,将第n个弹出。此时q2队列为空,以此类推,知道弹出所有 数据。
代码实现:
template <class T>
class 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<int> q1;
queue<int> 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 <stack>
#include <assert.h>
bool IsVail(int *Push,int *Pop,int n)
{
assert(Push);//数组元素不为NULL
assert(Pop);
stack<int> s;
int i = 0;
int j = 0;
for(j=0;j<n;)//出栈序列下标
{
for(i=0;i<n;i++)//入栈序列下标
{
if(Push[i] != Pop[j])//不相同
{
if(s.empty())//栈空
{
s.push(Push[i]);//入栈
continue;//跳出本次循环
}
else
{
if(Pop[i] == s.top())//栈不为空,不同需和栈中数据比较
{
s.pop();//相同弹出
j++;
}
else
{
s.push(Push[i]);//不同继续压栈
}
}
}
else
{
j++;
}
}
}
if(i == j) //出栈合法条件
{
return true;
}
else
{
return false;
}
}
int main()
{
int arr1[5] = {1,2,3,4,5};
int arr2[5] = {4,3,5,2,1};
bool ret = IsVail(arr1,arr2,5);
if(ret)
{
cout<<"出栈顺序合法"<<endl;
}
else
{
cout<<"出栈顺序不合法"<<endl;
}
return 0;
}
4.一个数组实现两个栈
解题思路:
(1)可将数组以奇数为下标的当为栈1,以偶数为下标的当为栈2。
(2)将数组一分为二,左边为栈1,右边为栈2。
(3)数组从左边开始为栈1,从右边开始为栈2。
分析:
思路(1),(2)虽然能解决问题,但是会浪费空间。若栈1存满,需要扩容。而栈2可能空无元素。
思路(3)可解决此缺憾。当栈1,栈2的栈顶相遇时,需要扩容。
以下用静态和动态分别实现:
(1)静态
代码实现
#define SIZE 10
template <class T>
class 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<<endl;
for(j=_top2+1;j<_capacity;j++)
{
cout<<_a[j]<<" ";
}
}
public:
void Push(const T& d,int choice)
{
_CheckCapacity();
if(choice == 0)//压入栈1
{
_a[_top1++] = d;
}
if(choice == 1)//压入栈2
{
_a[_top2--] = d;
}
}
void Pop()
{
if(choice == 0)//弹出栈1
{
if(_top1 == 0)
return;
else
_top1--;
}
if(choice == 1)//弹出栈2
{
if(_top2 == 0)
return;
else
_top2++;
}
}
protected:
T* _a;//数组
int _top1;//栈1的栈顶
int _top2;//栈2的栈顶
int _capacity;//容量
};
5.实现一个栈,要求实现Push(入栈)、Pop(出栈)、Min(返回最小值的操作)的时间复杂度为O(1)
看到此题,我们都知道Push(入栈)、Pop(出栈)的时间复杂度为O(1)。而解决此题的难点在于Min(返回最小值的操作)的时间复杂度为O(1)。我们不可能从头开始遍历,这样复杂度不可能为O(1)
解决此题的方法有如下两种:
(1)使用一个栈
每一次入栈都压两次,第一次压入原始数据,第二次压入当前栈中最小的。在第二压栈之前,需和上一次的比较,若小于则压栈,否则将上一次的再次压栈。出栈时,每次都弹出两次。
(2)使用两个栈
第一个栈用来保存原始数据,第二栈用保存当前栈中最小值。第一次两个栈中都压入,若再次压入栈,需要和当前栈2中的元素比较,若小于等于则入栈,否则只压入栈1。
分析:
若要是数据量庞大,可见第一种方法使用的空间很大。
此处实现的是第二种方法:
栈的简单实现:
template <class T>
class Stack
{
public:
Stack()//构造函数
:_a(NULL)
,_top(0)
,_capacity(0)
{}
~Stack()
{
if(_a)
{
delete[] _a;
_a = NULL;
}
}
Stack(Stack<T>& 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<T>& operator=(Stack<T>& 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;
};
返回最小值操作:
template <class T>
class 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<T> s1;//栈1
Stack<T> s2;//栈2
size_t _size;//栈中元素的个数
};
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。