Java實作棧（連結清單和線性表兩種方法實作）

Java實作棧（連結清單和線性表兩種方法實作）

一、棧的介紹

任何資料結構都是一種規則

棧就是在最基礎的結構——線性結構和鍊式結構上面定義規則形成的

如果對基本資料結構（線性表和連結清單）有疑問的同學可以看我之前的部落格：

https://www.cnblogs.com/yxm2020/p/12762888.html

規則如下：

限制連結清單或者線性表元素的插入和取出，隻能在同一端進行操作，運作插入的一段稱為棧頂（top),另一端為固定的一端，成為棧底。

圖解：（入棧和出棧）

特點：

先入後出FILO(First in last out),最先放入棧的資料，隻能最後才能出來，和隊列完全相反

棧的應用場景：

儲存運作過程中程式中的代碼或者值，比如：

子程式的調用

處理遞歸的調用

表達式的轉換（中綴轉字尾）

二叉樹的周遊

圖形的深度優先周遊

二、代碼的實作思路

1、思路

确定一個結構存儲資料，線性表或者連結清單

既然隻能在棧頂操作，那麼定義一棧頂标志（top)

最基本的兩個方法，入棧和出棧

入棧後，在棧頂加入一個元素，top上移一個單元

出棧後，在棧頂删除一個元素，top下移一個單元

2、Java實作

用Java數組模拟棧

java連結清單實作棧

三、Java數組模拟棧

public class ArrayStack {

//棧頂标志
private int top;
//java數組
private T[] stack;
//最大長度
private int maxsize;
public ArrayStack(int maxsize,Class<T> type){
    this.maxsize = maxsize;
    this.top = -1;
    stack = (T[]) Array.newInstance(type,maxsize);
}
//長度
public int size(){
    return top+1;
}
//棧滿
public boolean isFull(){
    return top == maxsize-1;
}
//棧空
public boolean isEnpty(){
    return top == -1;
}
//入棧
public void push(T t){
    if(isFull()){
        throw new RuntimeException("棧滿");
    }
    top++;
    stack[top] = t;
}
//出棧
public T pop(){
    if(isEnpty()){
        throw new RuntimeException("棧空");
    }
    T value = stack[top];
    top--;
    return value;
}
//周遊
public void show(){
    if(isEnpty()){
        System.out.println("棧空");
    }
    int temp = top;
    while (temp != -1){
        System.out.println(stack[temp]);
        temp--;
    }
}           

}

四、Java連結清單實作棧

public class LinkedStack {

//定義一個棧頂标志，帶了個
private Node top;
private class Node{
    private Node next;
    private T t;
    public Node(T t){
        this.t = t;
    }
}
//建立
public LinkedStack(){
    top = new Node(null);
}
//棧空
public boolean isEnpty(){
    if(top.next == null){
        return true;
    }
    return false;
}
//入棧
public void push(T t){
    Node newNode = new Node(t);
    //從棧頂入
    newNode.next = top.next;
    top.next = newNode;
}
//出棧
public T pop(){
    if(isEnpty()){
        System.out.println("棧空");
        return null;
    }
    T value = top.next.t;
    top.next = top.next.next;
    return value;
}
//show
public void show(){
    Node temp = top;
    if(temp.next == null){
        System.out.println("棧空");
    }
    while (temp.next!=null){
        temp = temp.next;
        System.out.println(temp.t);
    }
}           

原文位址

https://www.cnblogs.com/yxm2020/p/12859000.html