Java数据结构：栈的实现

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

查看( 439 ) / 评论( 0 ) / 评分( 0 / 0 )
栈是Java语言中最重要的数据结构之一，它的实现，至少应该包括以下几个方法：51Testing软件测试网 a1`O8O3l[:B,N d?:[

　　1、pop() 出栈操作，弹出栈顶元素。

9z:C)B SU^(S)c051Testing软件测试网y+j+E?)q

　　2、push(E e) 入栈操作

jb-NWo N9h#q$|0

n.D&g2M%^M'D_X4Q0　　3、peek() 查看栈顶元素

u\(?Kn,oTFG0

`!M7vX!O bB0　　4、isEmpty() 栈是否为空51Testing软件测试网7rRM?5tXgm gmY

51Testing软件测试网(SRJ f V&H"fw?

　　另外，实现一个栈，还应该考虑到几个问题：51Testing软件测试网 R Py'd{8H@Z%]

51Testing软件测试网 PU7vjm2v

　　1、栈的初始大小以及栈满以后如何新增栈空间51Testing软件测试网G)?4PTyD Ux

U Z&made0　　2、对栈进行更新时需要进行同步

1|k yS8yj-f051Testing软件测试网u0s'VO+{}

　　简单示例，使用数组实现栈，代码如下：51Testing软件测试网0["K1Lp9r1l |-X

  1. <pre name="code" class="java">public class Stack<E> {  

  2. 8s EuH T0F'?Z0
  3.     // Java 不支持泛型数组，如需使用，请使用Java提供的容器 
  4.     private Object[] stack;  
  5. 51Testing软件测试网'\6tAYM
  6.     // 栈的默认初始大小 
  7.     private static final int INIT_SIZE = 2;  

  8. n t&X(L"CQ-P0
  9.     // 栈顶索引 
  10.     private int index;  

  11. 3E.d.u u3Uoc0
  12.     public Stack() {  
  13.         stack = new Object[INIT_SIZE];  
  14.         index = -1;  
  15.     }  

  16. *v ^ce&P%k-w1eY8l7b@0
  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. 51Testing软件测试网v ?,w%G']GTJca
  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. +CKJS5X F0
  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. -sa];qE#oj7Zo-QR0
  61.     /** 
  62.      * 查看栈顶对象 
  63.      *  
  64.      * @return 栈顶对象 
  65.      */ 
  66.     public E peek() {  
  67.         if (!isEmpty()) {  
  68.             return (E) stack[index];  
  69.         }  
  70.         return null;  
  71.     }  

  72. S ]I;Pf r0
  73.     /** 
  74.      * 查看栈是否为空 
  75.      *  
  76.      * @return 如果栈为空返回true，否则返回false 
  77.      */ 
  78.     public boolean isEmpty() {  
  79.         return index == -1;  
  80.     }  

  81. %gor$M [*ad!_0
  82.     /** 
  83.      * 查看栈是否满 
  84.      *  
  85.      * @return 如果栈满返回true,否则返回false 
  86.      */ 
  87.     public boolean isFull() {  
  88.         return index >= stack.length - 1;  
  89.     }  
  90. }

Im6w!P#xW1ZDl0　　最后说明，Java中实现了栈（java.util.Stack）的数据结构，它是通过继承Vector类实现的，一般情况下我们直接拿来用就行了。51Testing软件测试网,uqgnW g iE


收藏 举报

TAG:

 

评分：0

我来说两句

Open Toolbar