用JAVA实现堆栈（数组篇）

 2011移动开发者大会亮点之一：六大精彩主题论坛抢鲜看                 2012年1月微软MVP申请开始了！
CSDN博客“准专家勋章”“微软MVP勋章”上线公告                                  “IT适合你吗？”智力挑战

用JAVA实现堆栈（数组篇）

分类： Java 2010-05-26 17:14 444人阅读 评论(0) 收藏 举报

什么是堆栈，关于这个名词，我在百度，google搜索了半天，也没有发现一个比较权威的解释，还有许多资料语焉不详，就以维基百科的解释为准吧，和我记忆中的一致。

堆栈（英文：stack），中国大陆作堆栈，台湾作堆叠，在计算机科學中，是一種特殊的串列形式的資料結構，它的特殊之處在於只能允許在鏈結串列或陣列的一端（稱為堆疊頂端指標，英文為top）進行加入資料（push）和輸出資料（pop）的運算。另外堆疊也可以用一維陣列或連結串列的形式來完成。堆疊的另外一個相對的操作方式稱為佇列。
由於堆疊資料結構只允許在一端進行操作，因而按照後進先出（LIFO, Last In First Out）的原理運作。

堆疊資料結構使用兩種基本操作：推入（push）和彈出（pop）：
推入（push） ：將數據放入堆疊的頂端（陣列形式或串列形式），堆疊頂端top指標加一。
彈出（pop）  ：將頂端數據資料輸出（回傳），堆疊頂端資料減一。

 

下面是用java数组实现堆栈

view plaincopy to clipboardprint?

/**
 * 使用数组实现堆栈，包括入栈、出栈、获取堆栈长度、
 * @author Adair
 */
public class Stack {

  Object[] data;

  int maxSize;
  //栈顶位置
  int top;

  public Stack(int maxSize) {
      this.maxSize = maxSize;
      data = new Object[maxSize];
      top = -1;
  }

  /**
   * 获取堆栈长度
   * @return 堆栈长度
   */
  public int getSize()
  {
    return maxSize;
  }

  /**
   * 返回栈中元素的个数
   * @return 栈中元素的个数
   */
  public int getElementCount()
  {
    return top;
  }

  /**
   * 判断栈空
   * @return 栈空
   */
  public boolean isEmpty()
  {
    return top == -1;
  }

  /**
   * 判断栈满
   * @return 栈满
   */
  public boolean isFull()
  {
    return top+1 == maxSize;
  }

  /**
   * 依次加入数据
   * @param data 要加入的数据通信
   * @return 添加是否成功
   */
  public boolean push(Object data) {
    if(isFull())
    {
        System.out.println("栈已满!");
        return false;
    }
    this.data[++top] = data;
    return true;
  }

  /**
   * 从栈中取出数据
   * @return 取出的数据
   */
  public Object pop() throws Exception{
    if(isEmpty())
    {
        throw new Exception("栈已空!");
    }
    return this.data[top--];
  }

  /**
   * 返回栈顶元素
   * @return
   */
  public Object peek()
  {
    return this.data[getElementCount()];
  }


  public static void main(String[] args) throws Exception {
      Stack stack=new Stack(1000);
      stack.push(new String("1"));
      stack.push(new String("2"));
      stack.push(new String("3"));
      stack.push(new String("4"));
      stack.push(new String("5"));
      System.out.println(stack.peek());

      while(stack.top>=0)
      {
          System.out.println(stack.pop());
      }
  }
}