JAVA数据结构,栈和队列的算法设计,给予源代码并附上注释。
时间: 2024-09-11 08:13:08 浏览: 45
在Java中,栈(Stack)和队列(Queue)是两种基本的数据结构,它们在算法设计中扮演着重要角色。栈是一种后进先出(LIFO, Last In First Out)的数据结构,而队列是一种先进先出(FIFO, First In First Out)的数据结构。
以下是Java中栈和队列的基本实现示例代码:
```java
// 栈的实现,使用链表作为底层存储结构
class Stack<T> {
private Node<T> top;
// 内部节点类
private static class Node<T> {
T data;
Node<T> next;
Node(T data) {
this.data = data;
}
}
// 入栈操作
public void push(T item) {
Node<T> newNode = new Node<>(item);
newNode.next = top;
top = newNode;
}
// 出栈操作
public T pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
T item = top.data;
top = top.next;
return item;
}
// 查看栈顶元素
public T peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return top.data;
}
// 栈是否为空
public boolean isEmpty() {
return top == null;
}
}
// 队列的实现,使用链表作为底层存储结构
class Queue<T> {
private Node<T> head;
private Node<T> tail;
// 内部节点类与栈中相同,故省略
// 入队操作
public void enqueue(T item) {
Node<T> newNode = new Node<>(item);
if (tail != null) {
tail.next = newNode;
}
tail = newNode;
if (head == null) {
head = tail;
}
}
// 出队操作
public T dequeue() {
if (isEmpty()) {
throw new EmptyStackException();
}
T item = head.data;
head = head.next;
if (head == null) {
tail = null;
}
return item;
}
// 查看队首元素
public T peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return head.data;
}
// 队列是否为空
public boolean isEmpty() {
return head == null;
}
}
```
在上述代码中,`Stack` 和 `Queue` 类使用链表结构来存储数据,实现了基本的栈和队列操作。`Stack` 类提供了 `push`、`pop` 和 `peek` 方法来分别完成元素的入栈、出栈和查看栈顶元素。`Queue` 类则提供了 `enqueue`、`dequeue` 和 `peek` 方法来完成元素的入队、出队和查看队首元素。
请注意,这些代码仅用于演示基本的栈和队列操作,没有处理潜在的并发问题,也没有实现迭代器或其它高级功能。
阅读全文