Java中的棧和隊(duì)列是兩種非常重要的數(shù)據(jù)結(jié)構(gòu),它們在編程中扮演著重要的角色,尤其是在數(shù)據(jù)處理和算法設(shè)計(jì)中。下面我們來分別介紹棧和隊(duì)列。
棧是一種后進(jìn)先出(LIFO)的數(shù)據(jù)結(jié)構(gòu),它具有入棧(PUSH)和出棧(POP)兩個(gè)基本操作。入棧操作向棧中添加一個(gè)元素;出棧操作則刪去棧頂元素。棧可以用數(shù)組或鏈表實(shí)現(xiàn),下面是使用鏈表實(shí)現(xiàn)的Java棧代碼:
public class Stack {
private Node top;
private class Node {
int data;
Node next;
}
public boolean isEmpty() {
return top == null;
}
public void push(int data) {
Node oldTop = top;
top = new Node();
top.data = data;
top.next = oldTop;
}
public int pop() {
int data = top.data;
top = top.next;
return data;
}
}
隊(duì)列是一種先進(jìn)先出(FIFO)的數(shù)據(jù)結(jié)構(gòu),它具有入隊(duì)(ENQUEUE)和出隊(duì)(DEQUEUE)兩個(gè)基本操作。入隊(duì)操作向隊(duì)列末尾添加一個(gè)元素;出隊(duì)操作則刪除隊(duì)頭元素。隊(duì)列同樣可以用數(shù)組或鏈表實(shí)現(xiàn),下面是使用數(shù)組實(shí)現(xiàn)的Java隊(duì)列代碼:
public class Queue {
private int head, tail;
private int[] data;
public Queue(int size) {
data = new int[size];
head = tail = 0;
}
public boolean isEmpty() {
return head == tail;
}
public boolean isFull() {
return tail - head == data.length;
}
public void enqueue(int x) {
if (isFull()) {
throw new RuntimeException("Queue is full.");
}
data[tail % data.length] = x;
tail++;
}
public int dequeue() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty.");
}
int x = data[head % data.length];
head++;
return x;
}
}