【数据结构】 栈

栈结构，通俗易懂，特点：先进后出，后进先出。

以下，仅对于栈结构常用的操作进行实现

包括：

????????入栈（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;
}

栈结构是最简单的数据结构，很多数据结构都会用到栈结构，所以简单的栈结构常用的操作需掌握。

若有纰漏，欢迎指正

（编辑：ASP站长网）