從堆疊到佇列：探索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中文網其他相關文章！
