栈的简介及C++模板实现 _栈的简

0. 数据结构图文解析系列数据结构系列文章数据结构图文解析之：数组、单链表、双链表介绍及C++模板实现数据结构图文解析之：栈的简介及C++模板实现数据结构图文解析之：队列详解与C++模板实现数据结构图文解析之：树的简介及二叉排序树C++模板实现.数据结构图文解析之：AVL树详解及C++模板实现数据结构图文解析之：二叉堆详解及C++模板实现数据结构图文解析之：哈夫曼树与哈夫曼编码详解及C++模板实现
回到顶部
1. 栈的简介1.1栈的特点
栈(Stack)是一种线性存储结构，它具有如下特点：

栈中的数据元素遵守”先进后出"(First In Last Out)的原则，简称FILO结构。
限定只能在栈顶进行插入和删除操作。

1.2栈的相关概念
栈的相关概念：

栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。
压栈：栈的插入操作，叫做进栈，也称压栈、入栈。
弹栈：栈的删除操作，也叫做出栈。

例如我们有一个存储整型元素的栈，我们依次压栈：{1,2,3}

文章插图

在压栈的过程中，栈顶的位置一直在”向上“移动，而栈底是固定不变的。
如果我们要把栈中的元素弹出来：

文章插图

出栈的顺序为3、2、1 ，顺序与入栈时相反，这就是所谓的”先入后出“ 。
在弹栈的过程中，栈顶位置一直在”向下“移动，而栈底一直保持不变。
如果你玩过一种称为汉诺塔的益智玩具，你就会知道游戏中小圆盘的存取就是一种先进后出的顺序，一个圆柱就是一个栈：

文章插图

1.3 栈的操作
栈的常用操作为：

弹栈，通常命名为pop
压栈，通常命名为push
求栈的大小
判断栈是否为空
获取栈顶元素的值

1.4 栈的存储结构
栈既然是一种线性结构，就能够以数组或链表（单向链表、双向链表或循环链表）作为底层数据结构。
本文我们以数组、单向链表为底层数据结构构建栈。
回到顶部
2. 基于数组的栈实现当以数组为底层数据结构时，通常以数组头为栈底，数组头到数组尾为栈顶的生长方向：

文章插图

2.1 栈的抽象数据类型
栈提供了如上所述操作的相应接口。
template<typename T>class ArrayStack{public: ArrayStack(int s = 10); //默认的栈容量为10 ~ArrayStack(); public: T top(); //获取栈顶元素 void push(T t); //压栈操作 T pop(); //弹栈操作 bool isEmpty(); //判空操作 int size(); //求栈的大小 private: int count; //栈的元素数量 int capacity; //栈的容量 T * array; //底层为数组};

count 为栈的元素数量， capacity为栈的容量， count<=capacity ，当栈满的时候， count = capacity 。
本实现中不支持栈的动态扩容，栈满的时候无法再插入元素。栈的容量在定义栈的时候就需要指定，默认的栈容量为10 。

2.2 栈的具体实现
栈的实现还是相对简单的，很容易理解。这里就不再画蛇添足了。
/*栈的判空操作*/template <typename T>bool ArrayStack<T>::isEmpty(){ return count == 0; //栈元素为0时为栈空}; /*返回栈的大小*/ template <typename T>int ArrayStack<T>::size(){ return count;}; /*插入元素*/template <typename T>void ArrayStack<T>::push(T t){ if (count != capacity) //先判断是否栈满 { array[count++] = t;}}; /*弹栈*/template <typename T>T ArrayStack<T>::pop(){ if (count != 0) //先判断是否是空栈 { return array[--count]; }}; /*获取栈顶元素*/template <typename T>T ArrayStack<T>::top(){ if (count != 0) { return array[count - 1]; }}; 2.3 栈的代码测试
int _tmain(int argc, _TCHAR* argv[]){ ArrayStack <int> p(5); for (int i = 0; i < 5; i++) { p.push(i); } cout << "栈的大小:"<<p.size() << endl; cout << "栈是否为空:"<<p.isEmpty() << endl; cout << "栈顶元素："<<p.top() << endl; cout << "依次出栈:" << endl; while (!p.isEmpty()) { cout << p.pop() << endl; } getchar(); return 0;}