3.2 的基本概念★1◎4

3.2 的基本概念★1◎4

3.2 栈的基本概念★1◎4

  栈本质上是一种只能在一端进行插入和删除操作的线性表,其中可操作端称为“栈顶”,不可操作端称为“栈底”。如图3-1所示,栈底指针一直不变,栈顶指针永远指向下一个要写入的结点:

  栈是一种“先进后出”的数据结构,一串数据依次全部进入栈,然后依次出栈,则这串数据的次序将倒置。比如线性表(2000,2001,2002,2003,2004)中的元素依次全部进入一个栈,然后出栈的次序为:2004,2003,2002,2001,2000,如图3-2所示。

  一串数据依次通过一个栈,并不能保证出栈的数据次序总是倒置,这与每个元素的出栈顺序有关,只有采用“全部入栈、全部出栈”的操作才能使数据次序倒置。事实上,只要操作得当,可以保证一串数据元素通过栈后仍然保持次序不变,如表3-2所示。

表3-2 (2001,2002,2003,2004)过栈示例

操    作

等待入栈元素

栈中元素

出栈元素

入栈 2002,2003,2004 2001  

续表

操    作

等待入栈元素

栈中元素

出栈元素

出栈 2002,2003,2004 2001
入栈 2003,2004 2002  
出栈 2003,2004 2002
入栈 2004 2003  
出栈 2004 2003
入栈 2004  
出栈 2004

  
  栈常常应用于括号匹配、表达式求解和递归代替等。

3.2 的基本概念★1◎4