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
