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