}
}
////3、使用两个队列实现一个栈
// 【剑指offer 面试题 7 扩展】
//题目：用两个队列实现一个栈。队列的声明如下，请实现它的pop和push函数。
//思路：入栈动作时，如果内部两个队列都为空的话，将数据压入其中一个队列(代码中为m_queue1)。如果其中一个队列已经有数据了，则将数据压入已经有数据的那个队列。出栈动作时，先将有数据的那个队列，除了最后一个入队的数据之外的所有数据输出到另外一个空的队列，然后最后那个数据也出队。
#include
template
class CStack
{
public:
void push(const T& node);
T pop();
private:
queue _queue1;
queue _queue2;
};
template
void CStack::push(const T& node)
{
if ((_queue1.empty() && _queue2.empty()) || _queue1.size())
{
_queue1.push(node);
}
else
{
_queue2.push(node);
}
}
template
T CStack::pop()
{
assert(!(_queue1.empty() && _queue2.empty()));
T node;
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();
}
return node;
}
void test_CStack()
{
CStack testStack ;
testStack.push('a') ;
testStack.push('b') ;
testStack.push('c') ;
char ch = 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】
bool IsPopOrder(const int* pPush, const int* pPop, int nLength)
{
bool bPossible = false;
if (pPush != NULL && pPop != NULL && nLength > 0)
{
const int* pNextPush = pPush;
const int* pNextPop = pPop;
stack 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;
}
}
return bPossible;
}
void test_IsPopOrder()
{
int PushArry[] = {1,2,3,4,5};
int PopArray1[] = {3,2,5,4,1};
int PopArray2[] = {3,2,5,1,4};
int PopArray3[] = {3,2,5,1,1};
bool ret1 = IsPopOrder(PushArry, PopArray1,5);
bool ret2 = IsPopOrder(PushArry, PopArray2,5);
bool ret3 = IsPopOrder(PushArry, PopArray3,5);
}
// 5、一个数组实现两个栈
// https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter10/Exercise10_1_2.cpp
class arrayWithTwoStack
{
public:
arrayWithTwoStack(int size)
:_top1(0)
,_top2(size - 1)
,_len(size)
{
_s = new int[size];
}
bool isEmpty(int index);// index指定哪个栈
void push(int index, int data);
int pop(int index);
private:
int _top1;
int _top2; // 两个栈顶坐标
int _len ; // 数组长度
int* _s; //
};
bool arrayWithTwoStack::isEmpty(int index)
{
if (index == 0 && _top1 == 0)
{
return true;
}
if (index == 1 && _top2 == _len - 1)
{
return true;
}
return false;
}
void arrayWithTwoStack::push(int index, int data)
{
// 已满
if (_top1 >= _top2)
{
throw exception("error: overflow");
}
// 对栈1操作
if (index == 0)
{
_s[_top1] =data;
_top1++;
}
else if (index == 1)
{
_s[_top2] = data;
_top2--;
}
}
//出栈
int arrayWithTwoStack::pop(int index)
{
int ret;
if (index == 0)
{
//栈1空
if (_top1 == 0)
{
throw exception("error: stack 0 is empty");
}
else
{
ret = _s[--_top1];
}
}
else if (index == 1)
{
//栈 2 空
if (_top2 == _len - 1)
{
throw exception("error: stack 1 is empty");
}
else
{
ret = _s[++_top2];
}
}
return ret;
}
void test_arrayWithTwoStack()
{
arrayWithTwoStack S(6);
// s0 123 54 s1
S.push(0,1);
S.push(0,2);
S.push(0,3);
try{
S.push(1,4);
S.push(1,5);
}
catch(exception e)
{
cout< }
S.pop(0);
S.pop(1);
S.pop(1);
bool em = S.isEmpty(1);
}
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
网页题目：栈和队列相关面试题-创新互联
文章转载：http://cdkjz.cn/article/dhooip.html
