從堆疊到佇列:探索Java中常見的線性資料結構及其實作方式
引言:
在電腦科學中,資料結構是組織和儲存資料的一種方式。線性資料結構是其中之一,它的特徵是資料元素之間存在明確的前後關係。在Java開發中,常見的線性資料結構包括堆疊和佇列,它們的使用頻率非常高。本文將深入探索堆疊和佇列在Java中的實作方式,並提供具體的程式碼範例。
一、堆疊的概念及實作方式:
堆疊是一種後進先出(Last In First Out, LIFO)的資料結構。它的特點是只能在堆疊頂部進行插入和刪除操作。在Java中,堆疊的常見實作方式有兩種:基於陣列的實作和基於鍊錶的實作。
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; } } }
二、佇列的概念及實作方式:
佇列是一種先進先出(First In First Out, FIFO)的資料結構。它的特點是只能在隊尾插入元素,在隊頭刪除元素。在Java中,佇列的常見實作方式有兩種:基於陣列的實作和基於鍊錶的實作。
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中文網其他相關文章!