栈和队列相关面试题-创新互联
// 1、实现一个栈，要求实现Push（出栈）、 Pop（入栈）、Min（返回最小值的操作） 的时间复杂度为O(1)
// 【剑指offer 面试题21】
template
class StackWithMin
{
public:
void push(const T& value);
void pop();
const T& min() const;
protected:
stack
stack
};
template
void StackWithMin
{
_data.push(value);
if (_min.size() == 0 || value < _min.top())
{
_min.push(value);
}
else
{
_min.push(_min.top());
}
}
template
void StackWithMin
{
assert(_data.size() > 0 && _min.size() > 0);
_data.pop();
_min.pop();
}
template
const T& StackWithMin
{
assert(_data.size() > 0 && _min.size() > 0);
return _min.top();
}
void test_StackWithMin()
{
StackWithMin
st.push(8);
st.push(5);
st.push(3);
st.push(2);
st.push(2);
int min = st.min();
st.pop();
st.pop();
st.pop();
min = st.min();
}
// 2、使用两个栈实现一个队列
// 【剑指offer 面试题7】
template
class CQueue
{
public:
void appendTail(const T& node);
T deleteHead();
protected:
stack
stack
};
template
void CQueue
{
_stack1.push(node);
}
template
T CQueue
{
if (_stack2.size() <= 0)
{
while (_stack1.size() > 0)
{
T& data = _stack1.top();
_stack2.push(data);
_stack1.pop();
}
}
if (_stack2.size() == 0)
{
throw exception("queue is empty");
}
T head = _stack2.top();
_stack2.pop();
return head;
}
void test_CQueue()
{
CQueue
q.appendTail(1);
q.appendTail(2);
q.appendTail(3);
q.deleteHead();
q.deleteHead();
q.deleteHead();
try
{
q.deleteHead();
}
catch (const exception& e)
{
cout< } } ////3、使用两个队列实现一个栈 // 【剑指offer 面试题 7 扩展】 //题目：用两个队列实现一个栈。队列的声明如下，请实现它的pop和push函数。 //思路：入栈动作时，如果内部两个队列都为空的话，将数据压入其中一个队列(代码中为m_queue1)。如果其中一个队列已经有数据了，则将数据压入已经有数据的那个队列。出栈动作时，先将有数据的那个队列，除了最后一个入队的数据之外的所有数据输出到另外一个空的队列，然后最后那个数据也出队。 #include template class CStack { public: void push(const T& node); T pop(); private: queue queue }; template void CStack { if ((_queue1.empty() && _queue2.empty()) || _queue1.size()) { _queue1.push(node); } else { _queue2.push(node); } } template T CStack { 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.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 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://abwzjs.com/article/dhooip.html
