QQ扫一扫联系
Java栈与队列怎么实现
在Java编程中，栈（Stack）和队列（Queue）是两种常见的数据结构，它们分别具有后进先出（Last In First Out，LIFO）和先进先出（First In First Out，FIFO）的特性。栈和队列在实际应用中有着广泛的用途，比如在算法、数据处理和多线程等场景下都能发挥重要作用。本文将介绍Java中栈和队列的实现方式，帮助您理解这两种数据结构的基本原理及应用。
栈是一种线性数据结构，它按照后进先出的原则管理数据。在Java中，可以使用数组或链表来实现栈。
使用数组实现栈是最简单直观的方式之一。我们可以创建一个固定大小的数组，同时维护一个栈顶指针（top）来表示当前栈顶的位置。
public class ArrayStack {
private int[] array;
private int top;
private int capacity;
public ArrayStack(int capacity) {
this.array = new int[capacity];
this.top = -1;
this.capacity = capacity;
}
public void push(int item) {
if (top == capacity - 1) {
throw new RuntimeException("Stack is full.");
}
array[++top] = item;
}
public int pop() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty.");
}
return array[top--];
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty.");
}
return array[top];
}
public boolean isEmpty() {
return top == -1;
}
public int size() {
return top + 1;
}
}
使用链表实现栈也是一种常见的方式，相比数组实现更具灵活性。我们可以定义一个链表节点类，并维护一个指向栈顶的指针。
public class LinkedListStack {
private static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
private Node top;
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 data = top.data;
top = top.next;
return data;
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty.");
}
return top.data;
}
public boolean isEmpty() {
return top == null;
}
public int size() {
int size = 0;
Node current = top;
while (current != null) {
size++;
current = current.next;
}
return size;
}
}
队列是一种线性数据结构，它按照先进先出的原则管理数据。在Java中，可以使用数组或链表来实现队列。
使用数组实现队列时，需要维护一个前端指针（front）和一个后端指针（rear）。
public class ArrayQueue {
private int[] array;
private int front;
private int rear;
private int capacity;
public ArrayQueue(int capacity) {
this.array = new int[capacity];
this.front = 0;
this.rear = -1;
this.capacity = capacity;
}
public void enqueue(int item) {
if (rear == capacity - 1) {
throw new RuntimeException("Queue is full.");
}
array[++rear] = item;
}
public int dequeue() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty.");
}
return array[front++];
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty.");
}
return array[front];
}
public boolean isEmpty() {
return front > rear;
}
public int size() {
return rear - front + 1;
}
}
使用链表实现队列时，只需维护一个前端指针（front）和一个后端指针（rear）即可。
public class LinkedListQueue {
private static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
private Node front;
private Node rear;
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 data = front.data;
front = front.next;
return data;
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty.");
}
return front.data;
}
public boolean isEmpty() {
return front == null;
}
public int size() {
int size = 0;
Node current = front;
while (current != null) {
size++;
current = current.next;
}
return size;
}
}
栈和队列在编程中有着广泛的应用。栈常用于实现递归算法、表达式求值、括号匹配和浏览器历史记录等场景。队列常用于实现广度优先搜索（BFS）、任务调度、消息队列和缓冲区管理等场景。
栈和队列是两种常见的数据结构，在Java中可以用数组或链表来实现。栈的后进先出特性使其适用于某些算法和数据处理场景，而队列的先进先出特性则使其在其他场景下发挥重要作用。了解栈和队列的实现方式和应用场景，可以帮助我们在编程中更加灵活地运用这两种数据结构，提高程序的效率和可维护性。
