溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
// 1、實現一個棧，要求實現Push（出棧）、 Pop（入棧）、Min（返回最小值的操作） 的時間復雜度為O(1)
// 【劍指offer 面試題21】
template<class T>
class StackWithMin
{
public:
void push(const T& value);
void pop();
const T& min() const;
protected:
stack<T> _min; // 記錄每次出棧壓棧 最小值
stack<T> _data; // 存數據
};
template<class T>
void StackWithMin<T>::push(const T& value)
{
_data.push(value);
if (_min.size() == 0 || value < _min.top())
{
_min.push(value);
}
else
{
_min.push(_min.top());
}
}
template<class T>
void StackWithMin<T>::pop()
{
assert(_data.size() > 0 && _min.size() > 0);
_data.pop();
_min.pop();
}
template<class T>
const T& StackWithMin<T>::min() const
{
assert(_data.size() > 0 && _min.size() > 0);
return _min.top();
}
void test_StackWithMin()
{
StackWithMin<int> st;
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 T>
class CQueue
{
public:
void appendTail(const T& node);
T deleteHead();
protected:
stack<T> _stack1;
stack<T> _stack2;
};
template<class T>
void CQueue<T>::appendTail(const T& node)
{
_stack1.push(node);
}
template<class T>
T CQueue<T>::deleteHead()
{
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<int> q;
q.appendTail(1);
q.appendTail(2);
q.appendTail(3);
q.deleteHead();
q.deleteHead();
q.deleteHead();
try
{
q.deleteHead();
}
catch (const exception& e)
{
cout<<e.what();
}
}
////3、使用兩個隊列實現一個棧
// 【劍指offer 面試題 7 擴展】
//題目：用兩個隊列實現一個棧。隊列的聲明如下，請實現它的pop和push函數。
//思路：入棧動作時，如果內部兩個隊列都為空的話，將數據壓入其中一個隊列(代碼中為m_queue1)。如果其中一個隊列已經有數據了，則將數據壓入已經有數據的那個隊列。出棧動作時，先將有數據的那個隊列，除了最后一個入隊的數據之外的所有數據輸出到另外一個空的隊列，然后最后那個數據也出隊。
#include <queue>
template<class T>
class CStack
{
public:
void push(const T& node);
T pop();
private:
queue<T> _queue1;
queue<T> _queue2;
};
template <class T>
void CStack<T>::push(const T& node)
{
if ((_queue1.empty() && _queue2.empty()) || _queue1.size())
{
_queue1.push(node);
}
else
{
_queue2.push(node);
}
}
template<class T>
T CStack<T>::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<char> 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<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;
}
}
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<<e.what()<<endl;
}
S.pop(0);
S.pop(1);
S.pop(1);
bool em = S.isEmpty(1);
}
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
