棧和隊列常見問題及其算法和c++實現
1.實現一個棧，要求實現push，pop，Min（返回最小值的操作）的時間復雜度為O（1）
算法思想：需要設計一個輔助棧，用來存儲當前棧中元素的最小值。額外需要注意push操作，第一個元素不用比較，自動成為最小值入棧，其他元素每次都要和棧頂元素進行比較，小的入棧。
#include<iostream>
#include<stack> //直接用系統中的棧，不需要自己實現
using namespace std;
template<class T>
class Stack
{
public:
void push(const T& x)
{
_stack.push(x);
if (_minstack.empty())
{
_minstack.push(x);
}
else
{
if (x < _minstack.top())
{
_minstack.push(x);
}
else
{
_minstack.push(_minstack.top());
}
}
}
void pop()
{
_stack.pop();
_minstack.pop();
}
T Retmin()
{
return _minstack.top();
}
private:
stack<T> _stack;
stack<T> _minstack;
};
void test()
{
Stack<int> s;
int ret;
s.push(3);
s.push(2);
s.push(5);
s.push(1);
s.push(7);
s.pop();
s.pop();
ret = s.Retmin();
cout << "最小值是:" << ret << endl;
}
int main()
{
test();
return 0;
}
2.元素出棧入棧順序的合法性檢查
算法思想：用for循環將數組1中的元素入棧，每入棧一個與數組2中當前元素進行進行比較，如果相同就出棧，數組2中下一個元素作為當前元素。如果循環結束，而棧中還有元素，就說明數組2不是pop序列。
#include<iostream>
#include<stack>
using namespace std;
bool InvalidCheck(int* stack_in, int* stack_out, int len1, int len2)
{
stack<int> s;
if (len1 != len2)
{
return false;
}
int i = 0, j = 0;
for (i = 0, j = 0; i < len1; i++)
{
s.push(stack_in[i]);
while (s.size()>0 && s.top() == stack_out[j])
{
s.pop();
j++;
}
}
if (s.size() > 0)
return false;
else
return true;
}
int main()
{
int stack_in[] = { 1, 2, 3, 4, 5 };
int stack_out[] = { 4, 5, 1, 2, 3 };
int len1 = sizeof(stack_in) / sizeof(stack_in[0]);
int len2 = sizeof(stack_out) / sizeof(stack_out[0]);
bool ret = InvalidCheck(stack_in, stack_out, len1, len2);
if (ret)
{
cout << "出棧順序合法!" << endl;
}
else
{
cout << "出棧順序不合法!" << endl;
}
return 0;
}
