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

スタックのリンク リスト実装

スタックがリンク リストを使用して実装される場合、配列実装との違いは、スタックをポップするときにスタックが 1 つしかないことです。最上位ノードはスタックの最上位を指すため、スタックの最上位の前の位置を見つけるには、最初から最後までトラバースする必要があります。

具体的な実装は以下のとおりです。

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) 16 進変換の際、変換された数値を逆に出力;

(3) 再帰を実装するロジックは次のように実装できます。スタック;

(4) スタックはパンくずリストのナビゲーションにも使用できるため、ユーザーはページを閲覧するときに簡単に前のページ以上に戻ることができます。

さらに関連する知識を学びたい場合は、java 入門プログラム をご覧ください。皆さんも一緒に学びましょう。

以上がJava でのスタックの配列およびリンク リストの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。