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

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

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

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

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

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];
    }
}

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

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 つがあります。

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

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];
    }
}

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

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 サイトの他の関連記事を参照してください。