Java深入了解数据结构之栈与队列的详解
1. 栈的概念
栈(Stack)是一种先进后出的数据结构，类似于一个箱子，新的物品只能放到箱子的顶部，旧的物品只能从箱子的顶部取出。栈通常有下面几个基本操作：
- push：将元素压入栈中，放在栈顶。
- pop：将栈顶元素弹出，如果栈为空，则抛出异常。
- peek：返回栈顶元素，但不将其弹出，如果栈为空，则抛出异常。
- isEmpty：判断栈是否为空。
- size：返回栈的元素数量。
2. 栈的实现
数组实现
数组实现栈非常简单，使用一个数组和一个指针top来实现，top表示栈顶元素的位置。具体实现代码如下：
public class ArrayStack<E> {
private static final int DEFAULT_CAPACITY = 10;
private Object[] data; // 栈数组
private int top; // 栈顶指针
private int size; // 栈内元素数量
// 构造函数，可以指定初始容量
public ArrayStack(int initialCapacity) {
if (initialCapacity <= 0) {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
data = new Object[initialCapacity];
top = -1;
}
// 默认构造函数，容量为10
public ArrayStack() {
this(DEFAULT_CAPACITY);
}
public void push(E item) {
if (size == data.length) {
resize(data.length * 2);
}
data[++top] = item;
size++;
}
public E pop() {
if (isEmpty()) {
throw new NoSuchElementException("Stack is empty");
}
E item = (E) data[top];
data[top--] = null; // help gc
size--;
if (size > 0 && size == data.length / 4) {
resize(data.length / 2);
}
return item;
}
public E peek() {
if (isEmpty()) {
throw new NoSuchElementException("Stack is empty");
}
return (E) data[top];
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
private void resize(int capacity) {
Object[] newData = new Object[capacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
}
链表实现
链表实现栈同样非常简单，使用一个链表和一个指针top来实现，top表示栈顶元素的位置。
public class LinkedListStack<E> {
private Node top; // 栈顶指针
private int size; // 栈内元素数量
public void push(E item) {
top = new Node(item, top);
size++;
}
public E pop() {
if (isEmpty()) {
throw new NoSuchElementException("Stack is empty");
}
E item = top.item;
top = top.next;
size--;
return item;
}
public E peek() {
if (isEmpty()) {
throw new NoSuchElementException("Stack is empty");
}
return top.item;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
private class Node {
E item;
Node next;
Node(E item, Node next) {
this.item = item;
this.next = next;
}
}
}
3. 队列的概念
队列(Queue)是一种先进先出的数据结构，类似于排队。新来的人只能排在队尾，离开的人只能从队首离开。队列通常有下面几个基本操作：
- add：将元素插入队尾。
- remove：删除并返回队首元素，如果队列为空，则抛出异常。
- element：返回队首元素，但不将其移除，如果队列为空，则抛出异常。
- offer：将元素插入队尾，与add方法类似，但是如果队列已满，则返回false。
- poll：删除并返回队首元素，与remove方法类似，但是如果队列为空，则返回null。
- peek：返回队首元素，但不将其移除，与element方法类似，但是如果队列为空，则返回null。
4. 队列的实现
数组实现
数组实现队列同样非常简单，使用一个数组和两个指针front和rear来实现，front表示队首元素的位置，rear表示队尾元素的位置。具体实现代码如下：
public class ArrayQueue<E> {
private static final int DEFAULT_CAPACITY = 10;
private Object[] data; // 队列数组
private int front; // 队首指针
private int rear; // 队尾指针
private int size; // 队列元素数量
public ArrayQueue(int initialCapacity) {
if (initialCapacity <= 0) {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
data = new Object[initialCapacity];
front = 0;
rear = -1;
}
public ArrayQueue() {
this(DEFAULT_CAPACITY);
}
public void add(E item) {
if (size == data.length) {
resize(data.length * 2);
}
data[++rear % data.length] = item;
size++;
}
public E remove() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
}
E item = (E) data[front];
data[front++] = null; // help gc
size--;
if (size > 0 && size == data.length / 4) {
resize(data.length / 2);
}
return item;
}
public E element() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
}
return (E) data[front];
}
public boolean offer(E item) {
if (size == data.length) {
return false;
}
data[++rear % data.length] = item;
size++;
return true;
}
public E poll() {
if (isEmpty()) {
return null;
}
return remove();
}
public E peek() {
if (isEmpty()) {
return null;
}
return (E) data[front];
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
private void resize(int capacity) {
Object[] newData = new Object[capacity];
for (int i = 0, j = front; i < size; i++, j++) {
newData[i] = data[j % data.length];
}
data = newData;
front = 0;
rear = size - 1;
}
}
链表实现
链表实现队列也非常简单，使用一个链表和两个指针front和rear来实现，front表示队首元素的位置，rear表示队尾元素的位置。
public class LinkedListQueue<E> {
private Node front; // 队首指针
private Node rear; // 队尾指针
private int size; // 队列元素数量
public void add(E item) {
Node node = new Node(item, null);
if (rear == null) {
front = node;
rear = node;
} else {
rear.next = node;
rear = node;
}
size++;
}
public E remove() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
}
E item = front.item;
front = front.next;
if (front == null) {
rear = null;
}
size--;
return item;
}
public E element() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
}
return front.item;
}
public boolean offer(E item) {
Node node = new Node(item, null);
if (rear == null) {
front = node;
rear = node;
} else {
rear.next = node;
rear = node;
}
size++;
return true;
}
public E poll() {
if (isEmpty()) {
return null;
}
return remove();
}
public E peek() {
if (isEmpty()) {
return null;
}
return front.item;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
private class Node {
E item;
Node next;
Node(E item, Node next) {
this.item = item;
this.next = next;
}
}
}
5. 示例说明
示例1: 使用栈实现括号匹配
我们可以使用栈来实现括号匹配，思路如下：
- 从左到右扫描字符串中的每个括号。
- 如果是左括号，则将其压入栈中。
- 如果是右括号，则从栈中弹出一个元素。
- 如果弹出的元素不是相应的左括号，则说明括号不匹配，返回false。
- 如果扫描完整个字符串后栈为空，则说明括号匹配，返回true。
代码实现如下：
public class BracketMatch {
public static boolean isMatch(String s) {
if (s == null || s.isEmpty()) {
return true;
}
ArrayStack<Character> stack = new ArrayStack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();
if ((c == ')' && top != '(')
|| (c == ']' && top != '[')
|| (c == '}' && top != '{')) {
return false;
}
}
}
return stack.isEmpty();
}
}
示例2: 使用队列实现击鼓传花
我们可以使用队列来实现击鼓传花，思路如下：
- 从1号到n号给每个人标上编号，形成一个环状队列。
- 从第一个人开始报数（1，则出队列），将花传给下一个人，再重新进入队列。
- 不断进行此操作，直到最后只剩下一个人。
代码实现如下：
public class PassGame {
public static int play(int n, int m) {
ArrayQueue<Integer> queue = new ArrayQueue<>();
for (int i = 1; i <= n; i++) {
queue.add(i);
}
while (queue.size() > 1) {
for (int i = 1; i < m; i++) {
queue.add(queue.remove());
}
queue.remove();
}
return queue.remove();
}
}
6. 总结
本文详细讲解了栈和队列的概念和实现方式，通过两个示例说明了如何使用栈和队列解决实际问题。栈和队列是基本的数据结构之一，本文的内容适合初学者学习。
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：Java深入了解数据结构之栈与队列的详解 - Python技术站
微信扫一扫 
支付宝扫一扫 