Array- und verknüpfte Listenimplementierung des Stapels in Java

Einführung in den Stapel

Der Stapel ist eine lineare First-In-Last-Out-Datenstruktur (FILO). Die Hauptoperationen sind Push-and-Pop-Stapel.

Unten im Stapel: Der Ort, an dem das früheste eingegebene Element gespeichert wird.

Oberseite des Stapels: Der letzte Ort, an dem das Element gespeichert ist (in einigen Stapeln wird die Oberseite des Stapels als nächste Position des obersten Elements dargestellt).

Kostenlose Online-Lernvideoempfehlung: Java-Video

Implementierung des Stack-Arrays

Das Beispiel lautet wie folgt:

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();
    }
}

Verknüpfte Listenimplementierung des Stapels

Wenn der Stapel mithilfe einer verknüpften Liste implementiert wird, besteht der Unterschied zur Array-Implementierung darin, dass der Stapel geöffnet wird, da wir nur einen haben Der oberste Knoten zeigt auf die Oberseite des Stapels und muss daher von Anfang bis Ende durchlaufen werden, um die vorherige Position oben auf dem Stapel zu finden.

Die spezifische Implementierung lautet wie folgt:

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();
    }
}

Stack-Anwendungsszenario

(1) Klammerübereinstimmungsbeurteilung, verwendet für Urteil (), {} usw. übereinstimmen;

(2) Während der Basiskonvertierung wird die konvertierte Zahl in umgekehrter Reihenfolge ausgegeben

(3) Die Logik zur Implementierung der Rekursion kann mit implementiert werden ein Stapel;

(4) Der Stapel kann auch für die Breadcrumb-Navigation verwendet werden, sodass Benutzer beim Durchsuchen der Seite problemlos zur vorherigen Seite oder höher zurückkehren können.

Wenn Sie weitere verwandte Kenntnisse erlernen möchten, besuchen Sie bitte: Java-Einführungsprogramm, alle sind herzlich willkommen, gemeinsam zu lernen!

Das obige ist der detaillierte Inhalt vonArray- und verknüpfte Listenimplementierung des Stapels in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!