首頁 >Java >java教程 >Java中常見的線性資料結構及其實作方式:從堆疊到佇列的探索

Java中常見的線性資料結構及其實作方式:從堆疊到佇列的探索

WBOY
WBOY原創
2023-12-26 16:55:121140瀏覽

Java中常見的線性資料結構及其實作方式:從堆疊到佇列的探索

從堆疊到佇列:探索Java中常見的線性資料結構及其實作方式

引言:
在電腦科學中,資料結構是組織和儲存資料的一種方式。線性資料結構是其中之一,它的特徵是資料元素之間存在明確的前後關係。在Java開發中,常見的線性資料結構包括堆疊和佇列,它們的使用頻率非常高。本文將深入探索堆疊和佇列在Java中的實作方式,並提供具體的程式碼範例。

一、堆疊的概念及實作方式:
堆疊是一種後進先出(Last In First Out, LIFO)的資料結構。它的特點是只能在堆疊頂部進行插入和刪除操作。在Java中,堆疊的常見實作方式有兩種:基於陣列的實作和基於鍊錶的實作。

  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];
    }
}
  1. 基於鍊錶的堆疊實作:
    鍊錶是一種非連續儲存的資料結構,同樣適合用來實現棧。以下是一個基於鍊錶的堆疊類別的範例程式碼:
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;
        }
    }
}

二、佇列的概念及實作方式:
佇列是一種先進先出(First In First Out, FIFO)的資料結構。它的特點是只能在隊尾插入元素,在隊頭刪除元素。在Java中,佇列的常見實作方式有兩種:基於陣列的實作和基於鍊錶的實作。

  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];
    }
}
  1. 基於鍊錶的佇列實作:
    與基於鍊錶的堆疊實作類似,下面是一個基於鍊錶的佇列類別的範例程式碼:
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中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn