創(chuàng)新互聯(lián)專注于石拐網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗。 熱誠為您提供石拐營銷型網(wǎng)站建設(shè)，石拐網(wǎng)站制作、石拐網(wǎng)頁設(shè)計、石拐網(wǎng)站官網(wǎng)定制、微信小程序服務(wù)，打造石拐網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供石拐網(wǎng)站排名全網(wǎng)營銷落地服務(wù)。
// 1、實現(xiàn)一個棧，要求實現(xiàn)Push（出棧）、 Pop（入棧）、Min（返回最小值的操作） 的時間復(fù)雜度為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、使用兩個棧實現(xiàn)一個隊列
// 【劍指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、使用兩個隊列實現(xiàn)一個棧 // 【劍指offer 面試題 7 擴展】 //題目：用兩個隊列實現(xiàn)一個棧。隊列的聲明如下，請實現(xiàn)它的pop和push函數(shù)。 //思路：入棧動作時，如果內(nèi)部兩個隊列都為空的話，將數(shù)據(jù)壓入其中一個隊列(代碼中為m_queue1)。如果其中一個隊列已經(jīng)有數(shù)據(jù)了，則將數(shù)據(jù)壓入已經(jīng)有數(shù)據(jù)的那個隊列。出棧動作時，先將有數(shù)據(jù)的那個隊列，除了最后一個入隊的數(shù)據(jù)之外的所有數(shù)據(jù)輸出到另外一個空的隊列，然后最后那個數(shù)據(jù)也出隊。 #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 有數(shù)據(jù) _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、一個數(shù)組實現(xiàn)兩個棧 // 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 ; // 數(shù)組長度 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); } 
當前名稱：棧和隊列相關(guān)面試題
文章轉(zhuǎn)載：http://weahome.cn/article/jjgjjj.html
重慶分公司
重慶分公司
