Java

1.栈

栈(Stack)也是一种特殊的线性表，是限定仅在表尾进行插入和删除运算的线性表，是一种后进先出(LIFO)的数据结构，只能在一端进行输入或输出数据的操作。堆栈把第一个放入该堆栈的数据放在最底下，而把后续放入的数据放在已有数据的顶上，表尾称为栈顶(top)，表头称为栈底(bottom)。堆栈的物理存储可以用顺序存储结构，也可以用链式存储结构。向堆栈中输入数据的操作称为"压栈"，从堆栈中输出数据的操作称为"弹栈"。

2. 栈的常用方法

使用java.util包中的Stack类创建一个堆栈对象，堆栈对象可以使用以下方法：

• public Object push(Object data)
  输入数据，实现压栈操作

• public synchronized Object pop()
  输出数据，实现弹栈操作

• public boolean empty()
  测试堆栈是否为空，如果空，返回true，否则返回false

• public synchronized Object peek()
  查看堆栈顶端的数据，但不删除该数据

• public synchronized int search(Object o)
  返回对象在栈中的位置，最顶端的位置是1，向下一次增加，如果堆栈不含此数据，则返回-1.

由于任何类都是Object类的子类，因此可以把任何一个对象压入堆栈

堆栈是很灵活的数据结构，使用堆栈可以节省内存的开销。比如，递归是一种很消耗内存的算法，可以借助堆栈消除大部分递归，达到和递归算法同样的目的。

3. 用链表实现栈

可以采用链表的方法来实现栈

• 用方法addFirst(Object element)实现进栈操作。
• 用方法removeFirst()实现出栈
• 用方法getFirst()实现栈顶数据查询
• 用方法isEmpty()实现栈是否为空