Struktur data linear biasa dalam Java dan pelaksanaannya: Penerokaan dari tindanan ke baris gilir

Dari Timbunan ke Baris Gilir: Teroka struktur data linear biasa di Java dan cara ia dilaksanakan

Pengenalan:
Dalam sains komputer, struktur data ialah cara mengatur dan menyimpan data. Salah satunya ialah struktur data linear, yang dicirikan oleh hubungan kontekstual yang jelas antara elemen data. Dalam pembangunan Java, struktur data linear biasa termasuk tindanan dan baris gilir, yang digunakan dengan sangat kerap. Artikel ini akan meneroka secara mendalam cara tindanan dan baris gilir dilaksanakan dalam Java dan memberikan contoh kod khusus.

1. Konsep dan pelaksanaan tindanan:
Timbunan ialah struktur data Masuk Dahulu Terakhir (LIFO). Cirinya ialah operasi pemasukan dan pemadaman hanya boleh dilakukan pada bahagian atas timbunan. Di Java, terdapat dua pelaksanaan biasa tindanan: pelaksanaan berasaskan tatasusunan dan pelaksanaan berasaskan senarai terpaut.

1. Pelaksanaan tindanan berasaskan array:
   Array ialah struktur data yang disimpan secara berterusan, yang sangat sesuai untuk melaksanakan tindanan. Berikut ialah kod sampel kelas tindanan berasaskan tatasusunan:

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. Pelaksanaan tindanan berdasarkan senarai terpaut:
   Senarai terpaut ialah struktur data storan tidak berterusan, yang juga sesuai untuk melaksanakan tindanan. Berikut ialah kod sampel kelas tindanan berdasarkan senarai terpaut:

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. Konsep dan pelaksanaan baris gilir:
Baris gilir ialah struktur data masuk dahulu keluar dahulu (FIFO). Cirinya ialah ia hanya boleh memasukkan elemen pada penghujung baris gilir dan memadamkan elemen di kepala baris gilir. Di Java, terdapat dua pelaksanaan biasa baris gilir: pelaksanaan berasaskan tatasusunan dan pelaksanaan berasaskan senarai terpaut.

1. Pelaksanaan baris gilir berasaskan tatasusunan:
   Sama seperti pelaksanaan tindanan berasaskan tatasusunan, berikut ialah kod sampel kelas gilir berasaskan tatasusunan:

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. Pelaksanaan baris gilir berasaskan senarai terpaut:
   Serupa dengan senarai terpaut- pelaksanaan tindanan berasaskan, Berikut ialah contoh kod untuk kelas gilir berasaskan senarai terpaut:

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

Kesimpulan:
Tindanan dan baris gilir adalah struktur data linear yang biasa digunakan di Java, dan terdapat banyak cara untuk melaksanakannya. Artikel ini memperkenalkan pelaksanaan tindanan dan baris gilir berasaskan tatasusunan dan senarai terpaut serta menyediakan contoh kod khusus. Pembangun boleh memilih kaedah pelaksanaan yang sesuai mengikut keperluan sebenar untuk meningkatkan kecekapan dan kebolehselenggaraan program.

Atas ialah kandungan terperinci Struktur data linear biasa dalam Java dan pelaksanaannya: Penerokaan dari tindanan ke baris gilir. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!