Java の一般的な線形データ構造とその実装: スタックからキューまでの探索-＆＃＆チュートリアル-php.cn

Java の一般的な線形データ構造とその実装: スタックからキューまでの探索

WBOY

リリース： 2023-12-26 16:55:12

オリジナル

1132 人が閲覧しました

Java の一般的な線形データ構造とその実装: スタックからキューまでの探索

スタックからキューへ: Java の一般的な線形データ構造とその実装方法を探る

はじめに:
コンピュータサイエンスでは、データ構造は組織化されており、データを保存する方法の実装。その 1 つは線形データ構造であり、データ要素間の明確なコンテキスト関係によって特徴付けられます。 Java 開発では、一般的な線形データ構造にはスタックとキューが含まれており、これらは非常に頻繁に使用されます。この記事では、Java でスタックとキューがどのように実装されるかを詳しく説明し、具体的なコード例を示します。

1. スタックの概念と実装:
スタックは後入れ先出し (LIFO) データ構造です。その特徴は、挿入および削除操作がスタックの最上位でのみ実行できることです。 Java では、スタックの一般的な実装として、配列ベースの実装とリンクリストベースの実装の 2 つがあります。

配列ベースのスタック実装:
配列は継続的に格納されるデータ構造であり、スタックの実装に非常に適しています。以下は、配列ベースのスタッククラスのサンプルコードです。

public class ArrayStack {
    private int[] stack;
    private int top;  // 栈顶指针

    public ArrayStack(int capacity) {
        stack = new int[capacity];
        top = -1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == stack.length - 1;
    }

    public void push(int item) {
        if (isFull()) {
            throw new RuntimeException("Stack is full");
        }
        stack[++top] = item;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top];
    }
}

ログイン後にコピー

リンクリストベースのスタック実装:
リンクリストは、非連続ストレージデータ構造です。実装スタックにも適しています。以下は、リンクリストに基づくスタッククラスのサンプルコードです:

public class LinkedStack {
    private Node top;

    public LinkedStack() {
        top = null;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public void push(int item) {
        Node newNode = new Node(item);
        newNode.next = top;
        top = newNode;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        int item = top.data;
        top = top.next;
        return item;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return top.data;
    }

    private class Node {
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
}

ログイン後にコピー

2. キューの概念と実装:
キューは先入れ先出し (FIFO) データです。構造。その特徴は、キューの最後尾の要素のみを挿入し、キューの先頭の要素を削除できることです。 Java では、キューの一般的な実装として、配列ベースの実装とリンクリストベースの実装の 2 つがあります。

配列ベースのキュー実装:
配列ベースのスタック実装と同様に、以下は配列ベースのキュークラスのサンプルコードです:

public class ArrayQueue {
    private int[] queue;
    private int front;  // 队头指针
    private int rear;  // 队尾指针

    public ArrayQueue(int capacity) {
        queue = new int[capacity + 1];  // 额外预留一个空位
        front = rear = 0;
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return (rear + 1) % queue.length == front;
    }

    public void enqueue(int item) {
        if (isFull()) {
            throw new RuntimeException("Queue is full");
        }
        queue[rear] = item;
        rear = (rear + 1) % queue.length;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int item = queue[front];
        front = (front + 1) % queue.length;
        return item;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return queue[front];
    }
}

ログイン後にコピー

リンクリストに基づくキューの実装:
リンクリストに基づくスタックの実装と同様に、以下はリンクリストに基づくキュークラスのサンプルコードです:

public class LinkedQueue {
    private Node front;  // 队头指针
    private Node rear;  // 队尾指针

    public LinkedQueue() {
        front = null;
        rear = null;
    }

    public boolean isEmpty() {
        return front == null;
    }

    public void enqueue(int item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int item = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return item;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return front.data;
    }

    private class Node {
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
}

ログイン後にコピー

結論:
スタックとキューは Java で一般的に使用される線形データ構造を実装する方法はたくさんあります。この記事では、配列ベースおよびリンクリストベースのスタックとキューの実装を紹介し、具体的なコード例を示します。開発者は実際のニーズに応じて適切な実装方法を選択し、プログラムの効率と保守性を向上させることができます。

以上がJava の一般的な線形データ構造とその実装: スタックからキューまでの探索の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。