最近本博主在复习数据结构，不不不！！！应该是预习，因为把上学期学的基本上全都还给脑四了，之前写过有关实现库里边栈和队列的文章，经过这几天的坚持不懈的努力，硬是啃了几道有关栈和队列的面试频率较高的题，今天就和大家分享一下下啦！
（一）实现一个栈结构 使得pop push min(获得栈中最小元素)操作的时间复杂度为O(1)
思路：可以用两个栈来实现，一个栈用来push,pop,一个栈用来保存这个过程的最小值，
比如有一组数要入栈
s1:8,9,10,3,2,2
s2:8,3,2,2
要实现这种功能我们可以通过给第二个栈中的每个元素添加一个计数器，当有重复元素进栈的时候，只需给计数器加加即可，那么问题来了，当元素很多的时候，这种方法很浪费空间，所以最好的方法就是重复元素只要比当前第二个栈的栈顶元素小，都可以进栈哦
#include<iostream>
#include<stack>
using namespace std;
template<class T>
class Stack
{
public:
void Push(const T& d)
{
if(_s2.empty()||_s2.top()>=d)
{
_s2.push(d);
}
_s1.push(d);
}
void Pop()
{
if(_s1.top()==_s2.top())
{
_s2.pop();
}
_s1.pop();
}
T min()
{
if(_s2.empty())
{
return -1;
}
return _s2.top();
}
void PrintStack()
{
while(!_s1.empty())
{
cout<<_s1.top()<<" ";
_s1.pop();
}
cout<<"over"<<endl;
}
private:
stack<T>_s1;
stack<T>_s2;
};
void test()
{
Stack<int>_s;
_s.Push(9);
_s.Push(10);
_s.Push(8);
_s.Push(5);
_s.Push(2);
_s.Push(2);
_s.Push(23);
_s.PrintStack();
_s.min();
cout<<_s.min()<<endl;
}
int main()
{
test();
system("pause");
return 0;
}（二）两个队列实现一个栈
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
template<typename T>
class Stack
{
public:
void Push(const T& d)
{
//刚开始如果两个队列都为空，则给q1压入数据
if(q1.empty()&&q2.empty())
{
q1.push(d);
return;
}
//如果q2不为空q1为空，则给q2压入数据
if(!q2.empty()&&q1.empty())
{
q2.push(d);
return;
}
//如果q1不为空，q2为空。则给q1压入数据
if(!q1.empty()&&q2.empty())
{
q1.push(d);
}
}
T Pop()
{
//如果q2为空，将q1中元素（除了最顶部）一次出队压入q2中，然后再将q1中剩下的那个元素弹出
if(q2.empty())
{
while(q1.size()>1)
{
q2.push(q1.front());
q1.pop();
}
T& data=q1.front();
q1.pop();
return data;
}
//如果q2不为空，将q2中元素一次出队（除了最定部元素）压入q1中，然后再将q2中剩下的那个元素弹出
else
{
while(q2.size()>1)
{
q1.push(q2.front());
q2.pop();
}
T& data=q2.front();
q2.pop();
return data;
}
}
private:
queue<T>q1;
queue<T>q2;
};
void test()
{
Stack<int>q1;
q1.Push(1);
q1.Push(2);
q1.Push(3);
q1.Push(4);
cout<<q1.Pop()<<endl;
}
int main()
{
test();
system("pause");
return 0;
}
（三）一个数组实现两个栈
#include<iostream>
#include<assert.h>
using namespace std;
template<typename T>
class TwoStack
{
public:
//栈的构造函数实现
TwoStack()
:_a(0)
,_top1(0)
,_top2(0)
,_Capacity(0)
{}
//栈的析构函数实现
~TwoStack()
{
if(_a!=NULL)
{
delete [] _a;
}
}
//栈的拷贝构造函数实现
TwoStack(const TwoStack<T>& ts)
:_a(new T[ts._Capacity-ts._top2+ts._top1])
,_top1(ts._top1)
,_top2(ts._top2)
,_Capacity(ts._Capacity-ts._top2+ts._top1)
{
//逐次拷贝两个栈对应的数组序列
for(size_t i=0;i<=ts._top1;i++)
{
_a[i]=ts._a[i];
}
for(size_t i=ts._Capacity-1;i>=ts._top2;i--)
{
_a[i]=ts._a[i];
}
}
//栈的赋值运算符重载函数的实现
TwoStack<T>& operator=(const TwoStack<T>& ts)
{
_top1=ts._top1;
_top2=ts._top2;
_Capacity=ts._Capacity;
for(size_t i=0;i<_Capacity;i++)
{
_a[i]=ts._a[i];
}
return *this;
}
//压栈函数
void Push(const T& d,int choice )
{
_CheckCapacity();
if(choice==1)
{
_a[_top1++]=d;
}
if(choice==2)
{
_a[_top2--]=d;
}
}
//元素出栈函数
void Pop(int choice)
{
if(choice==1)
{
assert(_top1>0);
--_top1;
}
if(choice==2)
{
assert(_top2<_Capacity-1);
++_top2;
}
}
//求栈顶元素函数
T&Top(int choice)
{
if(choice==1)
{
return _a[_top1-1];
}
if(choice==2)
{
return _a[_top2+1];
}
}
//判空函数
bool empty(int choice)
{
if(choice==1)
{
return _top1==0;
}
if(choice==2)
{
return _top2==_Capacity-1;
}
}
//求栈的元素个数函数
size_t Size(int choice)
{
if(choice==1)
{
cout<<"栈1的元素个数为："<<endl;
return _top1;
}
if(choice==2)
{
cout<<"栈2的元素个数为："<<endl;
return _Capacity-1-_top2;
}
}
//容量检测函数
void _CheckCapacity()
{
if(_a==NULL)
{
//保证如果数组为空的时候至少能开辟到空间
_a=new T[2*_Capacity+3];
_top2=_Capacity-1;
}
//当两个栈顶相遇时需要开辟空间
if(_top1==_top2)
{
size_t _oldCapacity=_Capacity;
//开辟新空间
T* _tmp=new T[_Capacity*2+3];
//将原来的内容拷贝到新的空间，然后释放原来的旧空间
for(size_t i=0;i<=_top1;i++)
{
_tmp[i]=_a[i];
}
for(size_t i=_Capacity-1;i>=_top2;i--)
{
_tmp[i]=_a[i];
}
delete []_a;
_a=_tmp;
_top2=_Capacity-1-(_oldCapacity-1-_top2);
}
}
void print()
{
cout<<"栈1为："<<endl;
for(size_t i=0;i<_top1;i++)
{
cout<<_a[i]<<" ";
}
cout<<"over"<<endl;
cout<<"栈2为："<<endl;
for(size_t i=_Capacity-1;i>_top2;i--)
{
cout<<_a[i]<<" ";
}
cout<<"over"<<endl;
}
private:
T* _a;//数组
size_t _top1;
size_t _top2;
size_t _Capacity;
};
void test()
{
TwoStack<int> ts1;
ts1.Push(1,1);
ts1.Push(2,1);
ts1.Push(3,1);
ts1.Push(4,1);
ts1.Pop (1);
ts1.Size(1);
ts1.Push(4,2);
ts1.Push(5,2);
ts1.Push(6,2);
ts1.Push(7,2);
ts1.print();
TwoStack<int>ts2(ts1);
cout<<"ts2----------"<<endl;
ts2.print();
TwoStack<int>ts3;
ts3=ts1;
cout<<"ts3----------"<<endl;
ts3.print();
}
int main()
{
test();
system("pause");
return 0;
}（四）出栈，入栈顺序的合法性
#include<iostream>
#include<assert.h>
#include<stack>
using namespace std;
template<class T>
bool IsValid(const T* stack_in,const T* stack_out,size_t size1,size_t size2)
{
assert(stack_in);
assert(stack_out);
stack<T>s;
//如果两个序列不相等，则直接返回
if(size1!=size2)
{
return false;
}
s.push(*stack_in++);
--size1;
while(size2)
{
//输入序列为1,2,3,4,5输出序列为1,3,2,4,5
if(s.top()==*stack_out)
{
s.pop();
stack_out++;
--size2;
continue;
}
if(s.empty()&&size1)
{
s.push(*stack_in++);
--size1;
}
while((s.top()!=*stack_out)&&size1)
{
s.push(*stack_in++);
--size1;
}
if(size1==0&&(s.top()!=*stack_out))
{
return false;
}
}
return true;
}
int main()
{
int arr1[]={1,2,3,4,5};
int arr2[]={4,3,5,2,1};
size_t size1=sizeof(arr1)/sizeof(arr1[0]);
size_t size2=sizeof(arr2)/sizeof(arr2[0]);
bool ret=IsValid(arr1,arr2,size1,size2);
cout<<ret<<endl;
getchar();
return 0;
}（五）两个栈实现一个队列
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
template<typename T>
class Queue
{
public:
//队列入队操作
void Push(const T& d)
{
_s1.push(d);
}
//队列出队操作
void Pop()
{
if(_s1.empty()&&_s2.empty())
{
cout<<"Queue is empty"<<endl;
}
if(!_s1.empty ()&&_s2.empty())
{
while(!_s1.empty())
{
_s2.push(_s1.top());
_s1.pop();
}
}
if(_s1.empty ()&&!_s2.empty())
{
cout<<_s2.top()<<" ";
_s2.pop();
}
}
bool Empty()
{
return (_s1.()==0&&_s2.size()==0);
}
private:
stack<T>_s1;
stack<T>_s2;
};
void test()
{
Queue<int>s1;
s1.Push(1);
s1.Push(2);
s1.Push(3);
s1.Push(4);
s1.Pop();
s1.Pop();
s1.Pop();
}
int main()
{
test();
system("pause");
return 0;
}免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
