本文共 2012 字，大约阅读时间需要 6 分钟。

​栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊在于栈和队列的基本操作是线性表操作的子集，他们是操作受限的线性表。但是从数据类型角度看，他们是和线性表大不相同的抽象数据类型。

栈是限定仅在表尾进行插入或者删除操作的线性表。表尾端称“栈顶”，表头端称“栈底”，不含元素的空表称“空栈”。栈最主要的特性为“先进后出”。

栈和线性表类似，有两种存储表示方法：顺序存储和链式存储

以下是对顺序栈抽象数据类的基本实现：

CStack.hpp

#include 
   
    ​const static int DEFAULT_CAPACITY = 0xffff; //栈默认容量大小宏定义template
    
     class CStack{private:  int m_iTop; //栈顶  int m_iCapacity; //栈容量大小  T *m_pDataArray; //指向栈内数据的指针​public:  //默认无参构造函数  CStack() :m_iTop(0), m_iCapacity(DEFAULT_CAPACITY)  {    //初始化栈数据数组    m_pDataArray = new T[m_iCapacity];  }  //构造函数，指定栈大小  CStack(int capacity) :m_iTop(0), m_iCapacity(capacity)  {    m_pDataArray = new T[m_iCapacity];  }​  //析构函数  ~CStack()  {    delete[]m_pDataArray;    m_pDataArray = nullptr;  }​​  //入栈  void push(T t);  //获取栈顶元素  T top();  //出栈  T pop();  //清空栈  void clear() { m_iTop = 0; }  int capacity() { return m_iCapacity; }  int size() { return m_iTop; }  bool empty() { return 0 == m_iTop; }  bool full() { return m_iTop == m_iCapacity; }​  //遍历栈元素，打印输出  void traverse(){    for (int i = 0; i < m_iTop; i++)      std::cout << m_pDataArray[i] << " ";​    std::cout << std::endl;  }};​template
     
      T CStack
      
       ::pop(){  if (empty())    throw "empty stack.";​  return m_pDataArray[--m_iTop];}​template
       
        T CStack
        
         ::top(){ if (empty()) throw "empty stack.";​ return m_pDataArray[m_iTop - 1];}​template
         
          void CStack
          
           ::push(T t){ if (full()) throw "full stack.";​ m_pDataArray[m_iTop] = t; m_iTop++;}
          
         
        
       
      
     
    
   

main.cpp

#include "CStack.hpp"#include 
   
    using namespace std;int main(int argc, char** argv){  CStack
    
      stack(5);  for (int i = 0; i < 5; i++)    stack.push(i);  cout << "size: " << stack.size() << endl;  stack.traverse();​  cout << stack.pop() << endl;  stack.traverse();​  stack.clear();  stack.traverse();​  //for (int i = 0; i < 5; i++)  //  stack.push(i);  //stack.push(6);​  system("pause");  return 0;}
    
   

执行结果：

栈的应用可以说有很多，比如编译器中符号匹配的检验、数制转换、汉诺塔问题求解等，可以看出栈这种结构是比较强大而且有趣的。

--|END|--

转载地址：http://neiii.baihongyu.com/