转载

Java数据结构:栈的实现

栈是Java语言中最重要的数据结构之一,它的实现,至少应该包括以下几个方法:

  1. pop() 出栈操作,弹出栈顶元素。
  2. push(E e) 入栈操作
  3. peek() 查看栈顶元素
  4. isEmpty() 栈是否为空

另外,实现一个栈,还应该考虑到几个问题:

  1. 栈的初始大小以及栈满以后如何新增栈空间
  2. 对栈进行更新时需要进行同步

简单示例,使用数组实现栈,代码如下:

  1. <pre name="code" class="java">public class Stack<E> {  
  2.  
  3.     // Java 不支持泛型数组,如需使用,请使用Java提供的容器  
  4.     private Object[] stack;  
  5.  
  6.     // 栈的默认初始大小  
  7.     private static final int INIT_SIZE = 2;  
  8.  
  9.     // 栈顶索引  
  10.     private int index;  
  11.  
  12.     public Stack() {  
  13.         stack = new Object[INIT_SIZE];  
  14.         index = -1;  
  15.     }  
  16.  
  17.     /**  
  18.      * 构造方法  
  19.      *   
  20.      * @param initSize  
  21.      *            栈的初始大小  
  22.      */ 
  23.     public Stack(int initSize) {  
  24.         if (initSize < 0) {  
  25.             throw new IllegalArgumentException();  
  26.         }  
  27.         stack = new Object[initSize];  
  28.         index = -1;  
  29.     }  
  30.  
  31.     /**  
  32.      * 出栈操作  
  33.      *   
  34.      * @return 栈顶对象  
  35.      */ 
  36.     public synchronized E pop() {  
  37.         if (!isEmpty()) {  
  38.             E temp = peek();  
  39.             stack[index--] = null;  
  40.             return temp;  
  41.         }  
  42.         return null;  
  43.     }  
  44.  
  45.     /**  
  46.      * 入栈操作  
  47.      *   
  48.      * @param obj  
  49.      *            等待入栈的对象  
  50.      */ 
  51.     public synchronized void push(E obj) {  
  52.         if (isFull()) {  
  53.             Object[] temp = stack;  
  54.             // 如果栈满,则创建空间为当前栈空间两倍的栈  
  55.             stack = new Object[2 * stack.length];  
  56.             System.arraycopy(temp, 0, stack, 0, temp.length);  
  57.         }  
  58.         stack[++index] = obj;  
  59.     }  
  60.  
  61.     /**  
  62.      * 查看栈顶对象  
  63.      *   
  64.      * @return 栈顶对象  
  65.      */ 
  66.     public E peek() {  
  67.         if (!isEmpty()) {  
  68.             return (E) stack[index];  
  69.         }  
  70.         return null;  
  71.     }  
  72.  
  73.     /**  
  74.      * 查看栈是否为空  
  75.      *   
  76.      * @return 如果栈为空返回true,否则返回false  
  77.      */ 
  78.     public boolean isEmpty() {  
  79.         return index == -1;  
  80.     }  
  81.  
  82.     /**  
  83.      * 查看栈是否满  
  84.      *   
  85.      * @return 如果栈满返回true,否则返回false  
  86.      */ 
  87.     public boolean isFull() {  
  88.         return index >= stack.length - 1;  
  89.     }  
  90. }  

最后说明,Java中实现了栈(java.util.Stack)的数据结构,它是通过继承Vector类实现的,一般情况下我们直接拿来用就行了。

正文到此结束
Loading...