Java数据结构：栈的实现

上一篇 / 下一篇  2012-05-18 08:58:42 / 个人分类：Java

查看( 442 ) / 评论( 0 ) / 评分( 0 / 0 )
栈是Java语言中最重要的数据结构之一，它的实现，至少应该包括以下几个方法：

3rrq(Z@0　　1、pop() 出栈操作，弹出栈顶元素。

G'i|D6xzWpaW0

F&F_)nq~w0　　2、push(E e) 入栈操作51Testing软件测试网"bP7C0z+u9b+s6e i)]

LF E'Hi2w0　　3、peek() 查看栈顶元素

Jr[#MEy5b[%sl0

(oH9za G0　　4、isEmpty() 栈是否为空

YT,]"XyE+BqqD0

*t;GC,FA:|@0　　另外，实现一个栈，还应该考虑到几个问题：

*c1|wG2YQ]b9a051Testing软件测试网O Sw `R(}g6g

　　1、栈的初始大小以及栈满以后如何新增栈空间

$bP:h8i:t(N S6Iq0]wp051Testing软件测试网v}N `9lL;Z)_ K

　　2、对栈进行更新时需要进行同步

KH*x7~1?%x;b8M6\6c0

q t])]FA!] }+j7w0　　简单示例，使用数组实现栈，代码如下：

/l$E p C6\(jZP+n0
  1. <pre name="code" class="java">public class Stack<E> {  
  2. 51Testing软件测试网.nO |G}b,F:\
  3.     // Java 不支持泛型数组，如需使用，请使用Java提供的容器 
  4.     private Object[] stack;  

  5. 8@1k${m[/JD0
  6.     // 栈的默认初始大小 
  7.     private static final int INIT_SIZE = 2;  
  8. 51Testing软件测试网5@M*]%Y6q7L%o
  9.     // 栈顶索引 
  10.     private int index;  

  11. .G#Tj7L*y8]e2CF0m8R0
  12.     public Stack() {  
  13.         stack = new Object[INIT_SIZE];  
  14.         index = -1;  
  15.     }  
  16. 51Testing软件测试网EUN gAR:K {3V
  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. 3i}!| d.x^&j _0
  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. 51Testing软件测试网 P j}1H'v h/o!H
  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. 4u |)l2F w/kK ?/g'O{0
  61.     /** 
  62.      * 查看栈顶对象 
  63.      *  
  64.      * @return 栈顶对象 
  65.      */ 
  66.     public E peek() {  
  67.         if (!isEmpty()) {  
  68.             return (E) stack[index];  
  69.         }  
  70.         return null;  
  71.     }  

  72. x \dAhaJS#b0
  73.     /** 
  74.      * 查看栈是否为空 
  75.      *  
  76.      * @return 如果栈为空返回true，否则返回false 
  77.      */ 
  78.     public boolean isEmpty() {  
  79.         return index == -1;  
  80.     }  
  81. 51Testing软件测试网c#um9Yc lg
  82.     /** 
  83.      * 查看栈是否满 
  84.      *  
  85.      * @return 如果栈满返回true,否则返回false 
  86.      */ 
  87.     public boolean isFull() {  
  88.         return index >= stack.length - 1;  
  89.     }  
  90. }

HW W9d1K0　　最后说明，Java中实现了栈（java.util.Stack）的数据结构，它是通过继承Vector类实现的，一般情况下我们直接拿来用就行了。51Testing软件测试网 PE!L+z)q;J#~8s7a;I~.U


收藏 举报

TAG:

 

评分：0

我来说两句

Open Toolbar