【移动应用开发技术】浅谈栈和队列的有关面试题

【移动应用开发技术】浅谈栈和队列的有关面试题

最近本博主在复习数据结构，不不不！！！应该是预习，因为把上学期学的基本上全都还给脑四了，之前写过有关实现库里边栈和队列的文章，经过这几天的坚持不懈的努力，硬是啃了几道有关栈和队列的面试频率较高的题，今天就和大家分享一下下啦！（一）实现一个栈结构使得poppushmin(获得栈中最小元素)操作的时间复杂度为O(1)思路：可以用两个栈来实现，一个栈用来push,pop,一个栈用来保存这个过程的最小值，比如有一组数要入栈s1:8,9,10,3,2,2s2: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