Implémentation de tableaux et de listes chaînées de la pile en Java

Introduction à la pile

La pile est une structure de données linéaire premier entré, dernier sorti (FILO). poussez et empilez.

Bas de la pile : l'emplacement où est stocké le premier élément entré.

Haut de la pile : Le dernier emplacement où l'élément est stocké (dans certaines piles, le haut de la pile est représenté comme la position suivante de l'élément supérieur).

Recommandation de vidéo d'apprentissage en ligne gratuite : Vidéo Java

Implémentation du tableau de pile

L'exemple est le suivant :

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

Implémentation de liste chaînée de la pile

Lorsque la pile est implémentée à l'aide d'une liste chaînée, la différence avec l'implémentation de tableau est que lors de l'éclatement de la pile, car nous n'en avons qu'une nœud supérieur pointant vers le haut de la pile, il doit donc être parcouru du début à la fin pour trouver la position précédente en haut de la pile.

L'implémentation spécifique est la suivante :

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

Scénario d'application de pile

(1) Jugement de correspondance de support, utilisé pour Judgement (), {}, etc. match;

(2) Lors de la conversion de base, le nombre converti est affiché à l'envers

(3) La logique pour implémenter la récursivité peut être implémentée en utilisant ; une pile ;

(4) La pile peut également être utilisée pour la navigation dans le fil d'Ariane, permettant aux utilisateurs de revenir facilement à la page précédente ou supérieure lors de la navigation sur la page.

Si vous souhaitez en savoir plus sur les connaissances connexes, veuillez visiter : Programme d'introduction à Java, tout le monde est invité à apprendre ensemble !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!