用Java代碼實現(xiàn)棧數(shù)據結構的基本方法歸納

更新時間：2015年08月06日 11:09:57 作者：zinss26914

這篇文章主要介紹了用Java代碼實現(xiàn)棧數(shù)據結構的基本方法歸納,各種算法的實現(xiàn)也是ACM上經常出現(xiàn)的題目,是計算機學習的基本功,需要的朋友可以參考下

鏈式實現(xiàn)：

在棧的一段添加和刪除元素，在棧中維護一個指向棧頂?shù)慕Y點和一個count變量指示棧的大?。?br /> private LinearNode top; //指向棧頂
private int count;//標記棧的大小
每次出棧和壓棧在鏈表的表頭：（也可以再表尾，實現(xiàn)方式不一樣而已）
top--->元素1--->元素2--->元素3.........
實現(xiàn)（附帶測試main）：
LinkedStack

package Stack;
import Bag.LinearNode;
//為了重點來實現(xiàn)算法，將異常情況直接打印出然后退出程序，不再聲明異常類
public class LinkedStack implements StackADT {
  private LinearNode top; //指向棧頂
  private int count;//標記棧的大小
  public static void main(String[] args){
    LinkedStack stack = new LinkedStack();
    System.out.println("將0到10依次壓棧");
    for(int i = 0;i < 10;i++)
      stack.push(i);
    System.out.println("連續(xù)執(zhí)行5次出棧操作");
    for(int i = 0;i < 5;i++)
      stack.pop();
    System.out.println("棧為空嗎？： " + stack.isEmpty());
    System.out.println("棧的大小為： " + stack.size());
    System.out.println("棧頂元素為： " + stack.top.getElement());
    System.out.println("棧頂元素為： " + stack.peek());  
  }
  public LinkedStack()
  {
    top = null;
    count = 0;
  }
  public int size() {
    return count;
  }
  public boolean isEmpty() {
    return (size() == 0);
  }
  public void push(Object element) {
    LinearNode node = new LinearNode(element);
    node.setNext(top);
    top = node;
    count++;
  }
  public Object pop() {
    if(isEmpty())
    {
      System.out.println("stack is empty!");
      System.exit(1);
    }
    Object result = top.getElement();
    top = top.getNext();
    count--;
    return result;
  }
  public Object peek() {
    Object result = top.getElement();
    return result;
  }
}

運行結果：
將0到10依次壓棧
連續(xù)執(zhí)行5次出棧操作
棧為空嗎？： false
棧的大小為： 5
棧頂元素為： 4
棧頂元素為： 4

數(shù)組實現(xiàn)：

棧底總是數(shù)組下標為0的位置，入棧出棧從數(shù)組下標的最后一個元素開始：

private Object[] contents;
private int top;//top標記下一個入棧的位置，同時也表示棧的容量大小，跟鏈式實現(xiàn)的count比較一下?。?！

實現(xiàn)（附帶測試main）：
ArrayStack

package Stack;
public class ArrayStack implements StackADT {
  private Object[] contents;
  private int top;//top標記下一個入棧的位置，同時也表示棧的容量大小，跟鏈式實現(xiàn)的count比較一下?。。?
  private static int SIZE = 10;
  public ArrayStack()
  {
    contents = new Object[SIZE];
    top = 0;
  }
  public void expand(){//借助于申請一個輔助空間,每次擴展容量一倍
    Object[] larger = new Object[size()*2];
    for(int index = 0;index < top;index++)
      larger[index] = contents[index];
    contents = larger;
  }
  public int size() {
    return top;
  }
  public boolean isEmpty() {
    return (size() == 0);
  }
  public void push(Object element) {
    //if(isEmpty())
      //expand();
    if(top == contents.length)
      expand();
    contents[top] = element;
    top++;
  }
  public Object pop() {
    if(isEmpty())
    {
      System.out.println("stack is empty!");
      System.exit(1);
    }
    Object result = contents[top-1];
    contents[top-1] = null;//出棧
    top--;
    return result;  
    /*書上這樣寫簡便一點：：：
     * top--;
     * Object result = contents[top];
     * contents[top] = null;*/    
  }
  public Object peek() {
    Object result;
    if(isEmpty())
      result = null;
    else
      result = contents[top-1];
    return result;
  }
  public static void main(String[] args) {
    ArrayStack stack = new ArrayStack();
    System.out.println("將0到24依次壓棧，然后連續(xù)10次出棧");
    for(int i = 0;i < 25;i++)
      stack.push(i);
    for(int i = 0;i < 10;i++)
      stack.pop();
    System.out.println("棧的大小為： " + stack.size());
    System.out.println("棧為空嗎？： " + stack.isEmpty());
    System.out.println("棧頂元素為： " + stack.peek());
  }
}

運行結果：
將0到24依次壓棧，然后連續(xù)10次出棧
棧的大小為： 15
棧為空嗎？： false
棧頂元素為： 14

使用集合LinkedList來模擬棧
方法
java的泛型可以讓LinkedList模擬存儲各種數(shù)據類型的棧，包括int，double，String，Object等等，介紹一下幾種用到的API接口：

入棧

  void addFirst(E e); // 將指定元素插入此列表的開頭

獲取棧頂元素

  E getFirst(); // 返回此列表的第一個元素

出棧

  E removeFirst(); // 移除并返回此列表第一個元素

判?？?/p>

  boolean isEmpty(); // 判斷?？?

示例代碼

 import java.util.LinkedList; 
  import java.util.NoSuchElementException; 
   
   
  public class SimulateStack { 
    private LinkedList<Integer> stack = new LinkedList<Integer>(); 
     
    public boolean isEmpty() { 
      return this.stack.isEmpty(); 
    } 
     
    public void push(int data) { 
      this.stack.addFirst(data); 
    } 
     
    public int pop() throws NoSuchElementException{ 
      return this.stack.removeFirst(); 
    } 
     
    public int getTop() throws NoSuchElementException{ 
      return this.stack.getFirst(); 
    } 
     
    public static void main(String args[]) { 
      SimulateStack s = new SimulateStack(); 
       
      s.push(1); 
      s.push(2); 
      s.push(3); 
       
      while (! s.isEmpty()) { 
        int data = s.getTop(); 
        System.out.println(data); 
        s.pop(); 
      } 
    } 
  }

您可能感興趣的文章:

Java
棧

JVM垃圾回收原理解析
這篇文章主要介紹了JVM垃圾回收原理解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2019-08-08
mybatis 多表關聯(lián)mapper文件寫法操作
這篇文章主要介紹了mybatis 多表關聯(lián)mapper文件寫法操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2020-12-12
Java面向對象編程（封裝/繼承/多態(tài)）實例解析
這篇文章主要介紹了Java面向對象編程（封裝/繼承/多態(tài)）實例解析的相關內容，具有一定參考價值，需要的朋友可以了解下。
2017-10-10
Java數(shù)據結構之圖的領接矩陣詳解
圖的領接矩陣存儲方式是用兩個數(shù)組來表示圖。一個一位數(shù)組存儲圖中頂點信息，一個二維數(shù)組存儲圖中的邊或弧的信息。本文將為大家重點介紹一下數(shù)據結構中的圖的鄰接矩陣，快來跟隨小編一起學習吧
2021-11-11
JavaFx 中創(chuàng)建計時器的步驟詳解
本文介紹了如何在JavaFx中創(chuàng)建計時器,通過創(chuàng)建計時器界面、編寫計時器邏輯以及關聯(lián)計時器按鈕,我們可以快速實現(xiàn)一個靈活可靠的計時器組件,本文能夠幫助讀者在 JavaFx 中成功實現(xiàn)自己的計時器功能,感興趣的朋友一起看看吧
2023-11-11
Fluent Mybatis,原生Mybatis,Mybatis Plus三者功能對比
本文主要介紹了Fluent Mybatis,原生Mybatis,Mybatis Plus三者功能對比，分享給大家，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2021-08-08
SpringBoot?分模塊開發(fā)的操作方法
這篇文章主要介紹了SpringBoot?分模塊開發(fā)的操作方法，通過在原項目新增一個maven模塊，本文通過示例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
2022-04-04
在Java中為日期增加一天的多種方法
這篇文章主要給大家介紹了關于如何在Java中為日期增加一天的多種方法,在JAVA業(yè)務代碼中,經常會遇到通過指定時間,增加指定天數(shù)的業(yè)務需求,需要的朋友可以參考下
2023-07-07
AntDesign多環(huán)境配置啟動過程詳解
這篇文章主要為大家介紹了AntDesign多環(huán)境配置啟動過程詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
2023-11-11
java的Jackson將json字符串轉換成泛型List
這篇文章主要介紹了java的Jackson將json字符串轉換成泛型List ，這里整理了詳細的代碼,有需要的小伙伴可以參考下。
2017-02-02