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