首頁 >Java >java教程 >java中堆疊的數組和鍊錶實現

java中堆疊的數組和鍊錶實現

王林
王林轉載
2019-11-28 13:14:462743瀏覽

java中堆疊的數組和鍊錶實現

堆疊的介紹

棧,是一種先進後出(FILO)的線性資料結構,主要操作為入棧和出棧。

堆疊底部:最早進入的元素存放的位置。

堆疊頂:最後進入元素存放的位置(有些堆疊中將堆疊頂表示為堆疊頂部元素的下一位置)。

免費線上學習影片推薦:java影片

堆疊的陣列的實作

範例如下:

public class MyStack {
    private int[] array;
    private int top = -1;//用top来表示栈顶,指向栈顶元素
 
    public MyStack(int capacity){
        array = new int[capacity];
    }
 
    public void push(int data) throws Exception{
        if(top >= array.length-1)
            throw new IndexOutOfBoundsException("边界超过范围!");
        else
            array[++top] = data;//先将指针上移,后赋值
    }
 
    public int pop() throws Exception{
        int temp;
        if(top < 0)
            throw new IndexOutOfBoundsException("栈为空,不能再删除元素!");
        else{
            temp = array[top];
            array[top--] = 0;
        }
        return temp;
    }
 
    public void output(){
        for(int i = 0; i <= top; i++){
            System.out.println(array[i]);
        }
    }
 
    public static void main(String[] args) throws Exception{
        MyStack myStack = new MyStack(5);
        myStack.push(1);
        myStack.push(3);
        myStack.push(2);
        myStack.pop();
        myStack.push(4);
        myStack.pop();
        myStack.output();
    }
}

棧的鍊錶實作

棧用鍊錶來實作時,和陣列實作不同的是,在出棧時,因為我們只有一個top節點來指向棧頂,因此需要從頭到尾遍歷一遍,才能找到棧頂的前一個位置。

具體的實作如下:

public class MyStack_LinkList {
    private static class Node{
        int data;
        Node next;
        Node(int data){
            this.data = data;
        }
    }
    private Node head;//定义链表的头结点
    private Node top;
    private int size;//定义栈中的元素个数
    private int maxSize;
 
    private MyStack_LinkList(int capacity){
        maxSize = capacity;
    }
 
    public void push(int data) throws Exception{
        if(size >= maxSize){
            throw new IndexOutOfBoundsException("栈已满,不能再入栈!");
        }
        Node pushedNode = new Node(data);
        if(size == 0){
            head = pushedNode;
            top = pushedNode;
            pushedNode.next = null;
        }
        else{
            top.next = pushedNode;
            pushedNode.next = null;
            top = pushedNode;
        }
        size++;
    }
 
    public int pop() throws Exception{
        int temp = 0;
        if(size <= 0)
            throw new IndexOutOfBoundsException("栈为空,不能再出栈!");
        else if(size == 1){//当栈中元素个数为1时,单独讨论,需将头节点置为空
            temp = top.data;
            top = null;
        }
        else{
            temp = top.data;
            top = get(size - 1);//此时需遍历一遍链表,用top指向需出栈的上一个节点
            top.next = null;
        }
        size--;
        return temp;
 
    }
 
    /*
    从头到尾查找元素
     */
    public Node get(int index){
        Node temp = head;
        for(int i = 1; i < index; i++){
            temp = temp.next;
        }
        return temp;
    }
 
    public void output(){
        Node temp = head;
        for(int i = 0; i < size; i++){
            System.out.println(temp.data);
            temp = temp.next;
        }
    }
 
    public static void main(String[] args) throws Exception{
        MyStack_LinkList myStack_linkList = new MyStack_LinkList(5);
        myStack_linkList.push(1);
        myStack_linkList.push(2);
        myStack_linkList.pop();
        myStack_linkList.push(3);
        myStack_linkList.push(5);
        myStack_linkList.output();
    }
}

堆疊的應用場景

(1)括號匹配判斷,用於判斷()、{}等是否匹配;

(2)進位轉換時,逆向輸出轉換後的數;

(3)實作遞歸的邏輯可以用堆疊來實現;

(4)堆疊也可以用於麵包屑導航,使用戶在瀏覽頁面時可以輕鬆地回溯到上一級或更上一級頁面。

想學習更多相關知識請造訪:java入門程式,歡迎大家一起來共同學習!

以上是java中堆疊的數組和鍊錶實現的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:csdn.net。如有侵權,請聯絡admin@php.cn刪除