一 栈：是一种表，限制插入和删除只能在一个位置，也即是表的末端（也是栈的顶）进行。
基本操作：push 和 pop。
二 栈的数组实现：
运用数组来存储元素，和栈操作先关的是theArray（一个数组实例）和topOfStack（指向栈顶元素，对于空栈，它的值是-1）。
push操作：将某个元素 item 推入栈中，使得 topOfStack 增1然后置 theArray[topOfStack] = item.
pop操作： 将栈顶严肃弹出，我们置返回值为 theArray[topOfStack]，然后 topOfStack 减1.
三 时间复杂度：
显然都是常数时间运行，O(1)。
java代码实现：
package com.xuyunyu.demo;
/**
*
* generic type class MyStack to implement the stack with array
* @author Administrator
*
* @param <AnyType>
*/
public class MyStack<AnyType>
{
/**
* the capacity of the stack
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* the array to store the elements
*/
private AnyType[] theItems;
/**
* the pointer to point to the top of the stack
*/
private int TopOfStack;
/**
* constructor
*
* to initial the stack
*/
public MyStack ()
{
clear();
}
/**
* clear the stack
*/
public void clear()
{
theItems = ( AnyType [] ) new Object[DEFAULT_CAPACITY];
TopOfStack = -1;
}
/**
* get the capacity of the stack
* @return
*/
public int size()
{
return DEFAULT_CAPACITY;
}
/**
* get the actual counts of
* the element stored in the stack
* @return
*/
public int getCountOfElement()
{
return TopOfStack + 1;
}
/**
* get the top element of the stack
* @return
*/
public AnyType getTopElement()
{
return theItems[TopOfStack];
}
/**
* judge if the stack is empty
* @return true if the stack is empty,false or not
*/
public boolean isEmpty()
{
return TopOfStack == -1;
}
/**
* judge if the stack is full
* @return true if the stack is full,false or not
*/
public boolean isFull()
{
return (TopOfStack + 1) == theItems.length;
}
/**
* push an item to the stack
* the TopOfStack INC ,and then store the item
* @param item
*/
public void push(AnyType item)
{
if(isFull())
throw new IndexOutOfBoundsException();
TopOfStack++;
theItems[TopOfStack] = item;
}
/**
* return the item on the top and then make one decrement of the TopOfStack
* @return
*/
public AnyType pop()
{
if(isEmpty() )
throw new IndexOutOfBoundsException(); AnyType ItemPulled = theItems[TopOfStack];
theItems[TopOfStack] = null;
TopOfStack--;
return ItemPulled;
} }
注意：这是一个泛型类，更加具有复用性。
四 测试代码：
package com.xuyunyu.demo; public class test_MyStack
{
public static void main(String[] args)
{
MyStack<Integer> stack = new MyStack<Integer>();
System.out.println("counts of the stack: " + stack.getCountOfElement());
System.out.println("size of the stack: " + stack.size());
//System.out.println("top element of the stack: " + stack.getTopElement()); stack.push(17);
System.out.println("counts of the stack: " + stack.getCountOfElement());
System.out.println("top element of the stack: " + stack.getTopElement()); stack.push(30);
System.out.println("counts of the stack: " + stack.getCountOfElement());
System.out.println("top element of the stack: " + stack.getTopElement()); stack.clear();
System.out.println("counts of the stack: " + stack.getCountOfElement()); System.out.println("push to the stack:" );
for (int i = 0; i < stack.size(); i++)
{
System.out.print(" " + i);
stack.push(i);
}
System.out.println(); System.out.println("pop from the stack:" );
for (int i = 0; i < stack.size(); i++)
{
System.out.print(" " + stack.pop());
} } }
期待输出如下：
counts of the stack: 0
size of the stack: 10
counts of the stack: 1
top element of the stack: 17
counts of the stack: 2
top element of the stack: 30
counts of the stack: 0
push to the stack
0 1 2 3 4 5 6 7 8 9
pop from the stack
9 8 7 6 5 4 3 2 1 0
结论：
显然实现了stack的后进先出的性质。
栈可以应用到平衡符号，中缀到后缀的转换以及方法调用上。详情可参考Mark Allen Weisss的《数据结构与算法分析——java语言描述》。 本文部分内容页参考此书。