基本数据结构:栈(stack)

时间:2022-02-28 17:54:12

 基本数据结构:栈(stack

作者:C小加 更新时间:2012-8-1

栈(stack)是限制插入和删除只能在一个位置上进行的线性表,该位置在表的末端,叫做栈顶。添加元素只能在尾节点后添加,删除元素只能删除尾节点,查看节点也只能查看尾节点。添加、删除、查看依次为入栈(push)、出栈(pop)、栈顶节点(top)。形象的说,栈是一个先进后出(LIFO)表,先进去的节点要等到后边进去的节点出来才能出来。

 

基本数据结构:栈(stack)

如图1,是一个栈的形象图,top指针指向的是栈顶节点,所以我们可以通过top访问到2节点,但是01节点由于先于2进入这个表,所以是不可见的。如果把0节点当做头节点,2节点当做尾节点,那么栈限制了访问权限,只可以访问尾节点。

 

基本数据结构:栈(stack)

如图2,当添加一个节点3的时候,只能在栈顶节点,也就是尾节点后添加,这样3节点变成了栈顶,2节点变成了不可见节点,访问的时候只能访问到3节点。入栈时限制了插入地址,只能在栈顶添加节点。

 

基本数据结构:栈(stack)

当我们执行出栈的命令时,图2的栈顶元素是3节点,删除的时候只能允许删除栈顶的元素,这样子3节点被删除,top指向删除后的栈顶2节点,如图3所示。

栈有两种是实现结构,一种是顺序存储结构,也就是利用数组实现,一种是链式存储结构,可以用单链表实现。数组实现栈很简单,用一个下标标记top来表示栈顶,top==-1时,栈空,top==0时,表示栈里只有一个元素,通过访问top为下标的数组元素即可。出栈top自减,入栈top自加就OK了。

单链表实现栈要比单链表的实现简单点。我们通过在表的尾端插入来实现push,通过删除尾节点来实现pop,获取尾节点的元素来表示top。我修改了链表那一章的单链表代码,把头节点当做栈顶节点,实现了一个简单的栈模板,仅供学习所用。代码会不定时更新。

代码如下:

 

  
 
 
  1. template<class T> 
  2.  
  3. class stackNode 
  4.  
  5.  
  6.     public
  7.  
  8.     stackNode():next(NULL){} 
  9.  
  10.     T data;//值 
  11.  
  12.     stackNode* next;//指向下一个节点的指针 
  13.  
  14. }; 
  15.  
  16. template<class T> 
  17.  
  18. class mystack 
  19.  
  20.  
  21.     private
  22.  
  23.     unsigned int stacklength; 
  24.  
  25.     stackNode<T>* node;//临时节点 
  26.  
  27.     stackNode<T>* headnode;//尾结点 
  28.  
  29.     public
  30.  
  31.         mystack();//初始化 
  32.  
  33.         unsigned int length();//栈元素的个数 
  34.  
  35.         void push(T x);//入栈 
  36.  
  37.         bool isEmpty();//判断栈是否为空 
  38.  
  39.         void pop();//出栈 
  40.  
  41.         T top();//获得栈顶元素 
  42.  
  43.         void clear();//清空栈 
  44.  
  45.   
  46.  
  47. }; 
  48.  
  49. template<class T> 
  50.  
  51. mystack<T>::mystack() 
  52.  
  53.  
  54.     node=NULL; 
  55.  
  56.     headnode=NULL; 
  57.  
  58.     stacklength=0; 
  59.  
  60.  
  61. template<class T> 
  62.  
  63. inline unsigned int mystack<T>::length(){return stacklength;} 
  64.  
  65. template<class T> 
  66.  
  67. void  mystack<T>::push(T x) 
  68.  
  69.  
  70.     node=new stackNode<T>(); 
  71.  
  72.     node->data=x; 
  73.  
  74.     node->next=headnode;//把node变成头节点 
  75.  
  76.     headnode=node; 
  77.  
  78.     ++stacklength; 
  79.  
  80.  
  81. template<class T> 
  82.  
  83. bool  mystack<T>::isEmpty() 
  84.  
  85.  
  86.     return stacklength==0; 
  87.  
  88.  
  89. template<class T> 
  90.  
  91. void  mystack<T>::pop() 
  92.  
  93.  
  94.     if(isEmpty()) return
  95.  
  96.     node=headnode; 
  97.  
  98.     headnode=headnode->next;//头节点变成它的下一个节点 
  99.  
  100.     delete(node);//删除头节点 
  101.  
  102.     --stacklength; 
  103.  
  104.  
  105. template<class T> 
  106.  
  107. T  mystack<T>::top() 
  108.  
  109.  
  110.     if(!isEmpty()) 
  111.  
  112.     return headnode->data; 
  113.  
  114.  
  115. template<class T> 
  116.  
  117. void  mystack<T>::clear() 
  118.  
  119.  
  120.     while(headnode!=NULL) 
  121.  
  122.     { 
  123.  
  124.         node=headnode; 
  125.  
  126.         headnode=headnode->next; 
  127.  
  128.         delete(node); 
  129.  
  130.     } 
  131.  
  132.     node=NULL; 
  133.  
  134.     headnode=NULL; 
  135.  
  136.     stacklength=0; 
  137.  

很清楚,除了clear函数外,所有的方法的时间复杂度都是O(1)。这种实现方式的缺点在于对newdelete的调用的开销是昂贵的,所以采用数组的方式实现会更好一点。

栈的应用

使用栈的时候一般不用自己重新去写,因为STL给我们实现了一个很安全的栈,可以放心去使用。也可以用数组模拟一个,很简单。

编译器调用函数就用了栈结构,当第一个函数还没执行完毕,调用第二个函数的时候,编译器就会把第一个函数压栈,第二个函数调用完毕的时候,就会取栈顶函数,也就是第一个函数继续执行。

平衡符号 http://acm.nyist.net/JudgeOnline/problem.php?pid=2

中缀转后缀 http://acm.nyist.net/JudgeOnline/problem.php?pid=467

后缀试求值 http://acm.nyist.net/JudgeOnline/problem.php?pid=35

poj 3250 http://acm.pku.edu.cn/JudgeOnline/problem?id=3250

poj 1363 http://acm.pku.edu.cn/JudgeOnline/problem?id=1363

poj 1208 http://acm.pku.edu.cn/JudgeOnline/problem?id=1208

poj 1686 http://acm.pku.edu.cn/JudgeOnline/problem?id=1686

poj 3250 http://acm.pku.edu.cn/JudgeOnline/problem?id=2045

hdu 1022 http://acm.hdu.edu.cn/showproblem.php?pid=1022
   
  
  

 

本文出自 “C小加&SunRise” 博客,请务必保留此出处http://lwxcy.blog.51cto.com/2467073/950320