栈结构,通俗易懂,特点:先进后出,后进先出。
以下,仅对于栈结构常用的操作进行实现
包括:
入栈(push),出栈(pop),判空(empty),栈顶元素(GetTop)
#include <iostream>
using namespace std;
template<class T>
class Stack
{
public:
Stack(T size) // 初始化数组大小
:top(0) //栈顶指针
, _size(size)
{
_array = new T[size]; // top指向最后一个元素时,再往下跳会越界,所以多开一个
}
~Stack()
{
if (_array)
{
delete[] _array;
}
}
public:
void Push(const T val)
{
if (top >= _size)
{
cout << "overflow" << endl;
return;
}
else
{
_array[top] = val;
top++;
}
}
T Pop()
{
T ret;
if (top < 0)
{
cout << "underflow" << endl;
return -1;
}
else
{
top--;
ret = _array[top];
}
return ret;
}
bool isEmpty()
{
return top == 0;
}
T Top()
{
if (!isEmpty())
{
return _array[top - 1];
}
else
{
cout << "error:stack is empty!" << endl;
}
}
void Show()
{
if (isEmpty())
{
cout << "stack has no data!" << endl;
return;
}
for (size_t i = 0; i < top; i++)
{
cout << _array[i] << " ";
}
cout << endl;
}
private:
size_t top;
size_t _size;
T* _array;
};
void Test()
{
Stack<int> stk(5);
stk.Push(1);
stk.Push(2);
stk.Push(3);
stk.Push(4);
stk.Push(5);
stk.Show();
cout << stk.Top() << endl;
cout << stk.Pop() << endl;
cout << stk.Pop() << endl;
cout << stk.Pop() << endl;
cout << stk.Top() << endl;
stk.Show();
}
int main()
{
Test();
system("pause");
return 0;
}