（1）栈
#pragma once
#include<cassert>
#include<string>
#include <iostream>
using namespace std;
template<class T>
class Stack
{
public:
Stack()
:_a(NULL)
, _size(0)
, _capacity(0)
{}
~Stack()
{
if (_a)
{
delete[] _a;
_a = NULL;
}
}
void Push(const T& x)//压栈
{
_Checkcapacity();
_a[_size] = x;
_size++;
}
void Pop()//出栈
{
assert(_size > 0);
--_size;
}
size_t Size()
{
return _size;
}
bool Empty()//判断栈是否为空
{
return _size == 0;
}
T& Top()//显示栈顶元素
{
assert(_size > 0);
return _a[_size-1];
}
void _Checkcapacity()
{
if (_size >= _capacity)
{
size_t newCapacity = _capacity == 0 ? 3 : _capacity * 2;
T* tmp = new T[newCapacity];
for (size_t i = 0; i < _size; ++i)
{
tmp[i] = _a[i];
}
delete[] _a;
_a = tmp;
_capacity = newCapacity;
}
}
protected:
T* _a;
size_t _size;
size_t _capacity;
};
//测试代码
void TestStack()
{
Stack<int> s1;
s1.Push(1);
s1.Push(2);
s1.Push(3);
s1.Push(4);
while (!s1.Empty())
{
cout << s1.Top() << " ";
s1.Pop();
}
cout << endl;
Stack<string> s2;
s2.Push("11");
s2.Push("22");
s2.Push("33");
s2.Push("44");
while (!s2.Empty())
{
cout << s2.Top() << " ";
s2.Pop();
}
cout << endl;
}
（2）队列
#pragma once
template<class T>
struct QueueNode
{
T _data;
QueueNode<T>* _next;
QueueNode(const T& x)
:_data(x)
, _next(NULL)
{}
};
template<class T>
class Queue
{
typedef QueueNode<T> Node;
public:
Queue()
:_head(NULL)
, _tail(NULL)
{}
void Push(const T& x)
{
if (_tail == NULL)
{
_head = _tail = new Node(x);
}
else
{
_tail->_next = new Node(x);
_tail = _tail->_next;
}
}
void Pop()
{
if(_head)
{
Node* next = _head->_next;
delete _head;
_head = next;
}
}
T& Front()
{
assert(_head);
return _head->_data;
}
size_t Size()
{
size_t n = 0;
Node* cur = _head;
while (cur && cur != _tail)
{
++n;
cur = cur->_next;
}
return n;
}
bool Empty()
{
return _head == NULL;
}
protected:
Node* _head;
Node* _tail;
};
//测试代码
void TestQueue()
{
Queue<int> q;
q.Push(1);
q.Push(2);
q.Push(3);
q.Push(4);
cout << "Size?" << q.Size() << endl;
while (!q.Empty())
{
cout << q.Front() << " ";
q.Pop();
}
cout << endl;
}
2.实现栈和队列的面试题。 （1）实现一个栈，要求实现Push（出栈）、Pop（入栈）、
Min（返回最小值的操作）的时间复杂度为O(1)
#pragma once #include <stack> #include <iostream> using namespace std; template<class T> class MinStack { public: MinStack() {} void Push(const T& x) { s.push(x); if (m.empty() || x < m.top()) m.push(x); else m.push(m.top()); } void Pop() { if (!m.empty() || !s.empty()) { m.pop(); s.pop(); } } T& Min() { return m.top(); } protected: stack<T> s; stack<T> m; };
（2）使用两个栈实现一个队列
#pragma once
#include <stack>
#include <iostream>
using namespace std;
template<class T>
class Queue
{
public:
Queue()
{}
void Push(const T& x)
{
s1.push(x);
}
void Pop()
{
if (s1.empty() && s2.empty())
{
return;
}
if (s2.empty)
{
while (!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
}
s2.pop();
}
size_t Size()
{
return s1.size() + s2.size();
}
bool Empty()
{
return (s1.empty() && s2.empty());
}
T& Front()
{
if (s1.empty() && s2.empty())
{
return;
}
if (s2.empty())
{
while (!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
}
return s2.top();
}
protected:
stack<T> s1;
stack<T> s2;
};
（3）使用两个队列实现一个栈
#pragma once
#include <queue>
#include <iostream>
using namespace std;
template<class T>
class Stack
{
public:
Stack()
{}
void Push(const T& x)
{
if (q1.empty() && q2.empty())
{
q1.push(x);
}
else if (q1.empty())
{
q1.push(x);
}
else
{
q2.push(x);
}
}
void Pop()
{
T cur = 0;
if (q2.empty()&& (!q1.empty()))
{
while (q1.size() > 1)
{
T& tmp = q1.front();
q1.pop();
q2.push(tmp);
}
cur = q1.front();
q1.pop();
cout << cur << endl;
}
else if (q1.empty() && (!q2.empty())
{
while (q2.size() > 1)
{
T& tmp = q2.front();
q2.pop();
q1.push(tmp);
}
cur = q2.front();
q2.pop();
cout << cur << endl;
}
else
{
return NULL;
}
}
protected:
queue<T> q1;
queue<T> q2;
};
（4）判断元素出栈、入栈顺序的合法性。如：入栈的序列（1,2,3,4,5），出栈序列为（4,5,3,2,1）是合法序列，入栈的序列（1,2,3,4,5），出栈序列为（1,5,3,2,4）是不合法序列
#pragma once
#include <iostream>
#include <stack>
using namespace std;
bool Judge(int* InArr, int* OutArr, size_t size)
{
stack<int> s;
int i = 0;
int j = 0;
for (size_t i = 0; i < size; i++)
{
s.push(InArr[i]);
while (!s.empty() && s.top() == OutArr[j])
{
s.pop();
j++;
}
}
return s.empty();
}
void TestJudge()
{
int inarr[5] = { 1, 2, 3, 4, 5 };
int outarr[5] = { 4, 5, 2, 3, 1 };
cout << Judge(inarr, outarr, 5) << endl;
}
（5）一个数组实现两个栈
template<class T>
class TwoStack
{
public:
TwoStack()
:_a(NULL)
, _sz1(0)
, _sz2(0)
, _capacity(0)
{
_CheckCapacity();
}
~TwoStack()
{
if (_a)
delete[] _a;
}
void Push1(const T& d)
{
_CheckCapacity();
_a[_sz1++] = d;
}
void Push2(const T& d)
{
_CheckCapacity();
_a[_sz2--] = d;
}
void Pop1()
{
if (_sz1 > 0)
--_sz1;
}
void Pop2()
{
if (_sz2 < _capacity - 1)
_sz2++;
}
size_t Size1()
{
return _sz1;
}
size_t Size2()
{
return _capacity - 1 - _sz2;
}
bool Empty1()
{
return _sz1 == 0;
}
bool Empty2()
{
return _sz2 == _capacity - 1;
}
T& Top1()
{
if (_sz1>0)
{
return _a[_sz1 - 1];
}
}
T& Top2()
{
if (_sz2 < _capacity - 1)
return _a[_sz2 + 1];
}
private:
void _CheckCapacity()
{
if (_a == NULL)
{
_capacity += 3;
_a = new T[_capacity];
_sz2 = _capacity - 1;
return;
}
if (_sz1 == _sz2)
{
size_t OldCapacity = _capacity;
_capacity = _capacity * 2;
T* tmp = new T[_capacity];
for (size_t i = 0; i < _sz1; i++)
{
tmp[i] = _a[i];
}
for (size_t j = OldCapacity - 1, i = _capacity - 1; j>_sz2; j--, i--)
{
tmp[i] = _a[j];
}
delete[] _a;
_a = tmp;
_sz2 += _capacity / 2;
}
}
private:
T* _a;
size_t _sz1;
size_t _sz2;
size_t _capacity;
};
//测试代码
void TestTwoStack()
{
TwoStack<int> s;
s.Push1(1);
s.Push1(2);
s.Push1(3);
s.Push1(4);
s.Push1(5);
s.Push2(1);
s.Push2(2);
s.Push2(3);
s.Push2(4);
s.Push2(5);
cout << "s1:" << s.Size1() << endl;
cout << "s2:" << s.Size2() << endl;
while (!s.Empty1())
{
cout << s.Top1() << endl;
s.Pop1();
}
while (!s.Empty2())
{
cout << s.Top2() << endl;
s.Pop2();
}
}