栈和队列 相关 面试题
//1、实现一个栈，要求实现Push（出栈）、Pop（入栈）、Min（返回最小值的操作）的时间复杂度为O(1)
//【剑指offer面试题21】
template<classT>
classStackWithMin
{
public:
voidpush(constT&value);
voidpop();
constT&min()const;
protected:
stack<T>_min;//记录每次出栈压栈最小值
stack<T>_data;//存数据
};
template<classT>
voidStackWithMin<T>::push(constT&value)
{
_data.push(value);
if(_min.size()==0||value<_min.top())
{
_min.push(value);
}
else
{
_min.push(_min.top());
}
}
template<classT>
voidStackWithMin<T>::pop()
{
assert(_data.size()>0&&_min.size()>0);
_data.pop();
_min.pop();
}
template<classT>
constT&StackWithMin<T>::min()const
{
assert(_data.size()>0&&_min.size()>0);
return_min.top();
}
voidtest_StackWithMin()
{
StackWithMin<int>st;
st.push(8);
st.push(5);
st.push(3);
st.push(2);
st.push(2);
intmin=st.min();
st.pop();
st.pop();
st.pop();
min=st.min();
}
//2、使用两个栈实现一个队列
//【剑指offer面试题7】
template<classT>
classCQueue
{
public:
voidappendTail(constT&node);
TdeleteHead();
protected:
stack<T>_stack1;
stack<T>_stack2;
};
template<classT>
voidCQueue<T>::appendTail(constT&node)
{
_stack1.push(node);
}
template<classT>
TCQueue<T>::deleteHead()
{
if(_stack2.size()<=0)
{
while(_stack1.size()>0)
{
T&data=_stack1.top();
_stack2.push(data);
_stack1.pop();
}
}
if(_stack2.size()==0)
{
throwexception("queueisempty");
}
Thead=_stack2.top();
_stack2.pop();
returnhead;
}
voidtest_CQueue()
{
CQueue<int>q;
q.appendTail(1);
q.appendTail(2);
q.appendTail(3);
q.deleteHead();
q.deleteHead();
q.deleteHead();
try
{
q.deleteHead();
}
catch(constexception&e)
{
cout<<e.what();
}
}
////3、使用两个队列实现一个栈
//【剑指offer面试题7扩展】
//题目：用两个队列实现一个栈。队列的声明如下，请实现它的pop和push函数。
//思路：入栈动作时，如果内部两个队列都为空的话，将数据压入其中一个队列(代码中为m_queue1)。如果其中一个队列已经有数据了，则将数据压入已经有数据的那个队列。出栈动作时，先将有数据的那个队列，除了最后一个入队的数据之外的所有数据输出到另外一个空的队列，然后最后那个数据也出队。
#include<queue>
template<classT>
classCStack
{
public:
voidpush(constT&node);
Tpop();
private:
queue<T>_queue1;
queue<T>_queue2;
};
template<classT>
voidCStack<T>::push(constT&node)
{
if((_queue1.empty()&&_queue2.empty())||_queue1.size())
{
_queue1.push(node);
}
else
{
_queue2.push(node);
}
}
template<classT>
TCStack<T>::pop()
{
assert(!(_queue1.empty()&&_queue2.empty()));
Tnode;
if(_queue1.size())
{
while(_queue1.size()>1)
{
node=_queue1.front();
_queue1.pop();
_queue2.push(node);
}
node=_queue1.front();
_queue1.pop();
}
else//_queue2有数据_queue1空
{
while(_queue2.size()>1)
{
node=_queue2.front();
_queue2.pop();
_queue1.push(node);
}
node=_queue2.front();
_queue2.pop();
}
returnnode;
}
voidtest_CStack()
{
CStack<char>testStack;
testStack.push('a');
testStack.push('b');
testStack.push('c');
charch=testStack.pop();
printf("%c\n",ch);
ch=testStack.pop();
printf("%c\n",ch);
testStack.push('d');
ch=testStack.pop();
printf("%c\n",ch);
}
//4、元素出栈、入栈顺序的合法性。如入栈的序列（1,2,3,4,5），出栈序列为（4,5,3,2,1）
//【剑指offer面试题22】
boolIsPopOrder(constint*pPush,constint*pPop,intnLength)
{
boolbPossible=false;
if(pPush!=NULL&&pPop!=NULL&&nLength>0)
{
constint*pNextPush=pPush;
constint*pNextPop=pPop;
stack<int>stackData;
while(pNextPop-pPop<nLength)
{
while(stackData.empty()||stackData.top()!=*pNextPop)
{
if(pNextPush-pPush==nLength)
{
break;
}
stackData.push(*pNextPush);
pNextPush++;
}
if(stackData.top()!=*pNextPop)//if(pNextPush-pPush==nLength)跳出的
{
break;//不匹配
}
stackData.pop();
pNextPop++;
}
if(stackData.empty()&&pNextPop-pPop==nLength)
{
bPossible=true;
}
}
returnbPossible;
}
voidtest_IsPopOrder()
{
intPushArry[]={1,2,3,4,5};
intPopArray1[]={3,2,5,4,1};
intPopArray2[]={3,2,5,1,4};
intPopArray3[]={3,2,5,1,1};
boolret1=IsPopOrder(PushArry,PopArray1,5);
boolret2=IsPopOrder(PushArry,PopArray2,5);
boolret3=IsPopOrder(PushArry,PopArray3,5);
}
//5、一个数组实现两个栈
//https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter10/Exercise10_1_2.cpp
classarrayWithTwoStack
{
public:
arrayWithTwoStack(intsize)
:_top1(0)
,_top2(size-1)
,_len(size)
{
_s=newint[size];
}
boolisEmpty(intindex);//index指定哪个栈
voidpush(intindex,intdata);
intpop(intindex);
private:
int_top1;
int_top2;//两个栈顶坐标
int_len;//数组长度
int*_s;//
};
boolarrayWithTwoStack::isEmpty(intindex)
{
if(index==0&&_top1==0)
{
returntrue;
}
if(index==1&&_top2==_len-1)
{
returntrue;
}
returnfalse;
}
voidarrayWithTwoStack::push(intindex,intdata)
{
//已满
if(_top1>=_top2)
{
throwexception("error:overflow");
}
//对栈1操作
if(index==0)
{
_s[_top1]=data;
_top1++;
}
elseif(index==1)
{
_s[_top2]=data;
_top2--;
}
}
//出栈
intarrayWithTwoStack::pop(intindex)
{
intret;
if(index==0)
{
//栈1空
if(_top1==0)
{
throwexception("error:stack0isempty");
}
else
{
ret=_s[--_top1];
}
}
elseif(index==1)
{
//栈2空
if(_top2==_len-1)
{
throwexception("error:stack1isempty");
}
else
{
ret=_s[++_top2];
}
}
returnret;
}
voidtest_arrayWithTwoStack()
{
arrayWithTwoStackS(6);
//s012354s1
S.push(0,1);
S.push(0,2);
S.push(0,3);
try{
S.push(1,4);
S.push(1,5);
}
catch(exceptione)
{
cout<<e.what()<<endl;
}
S.pop(0);
S.pop(1);
S.pop(1);
boolem=S.isEmpty(1);
}
声明：本站所有文章资源内容，如无特殊说明或标注，均为采集网络资源。如若本站内容侵犯了原著者的合法权益，可联系本站删除。
