如何使用Java的组合对(LinkedList)类进行封装,分别实现一个栈(Stack)和队列(Queue),并编写一个测试类来验证其功能是否正确。
时间: 2024-10-25 16:09:54 浏览: 27
Java模拟栈和队列数据结构的基本示例讲解共4页.pdf
在Java中,我们可以利用`LinkedList`类作为基础数据结构来实现栈(Stack)和队列(Queue)。这里我会提供一种简单的方式:
首先,我们创建一个名为`Node`的内部类,用于存储节点数据:
```java
import java.util.LinkedList;
class Node<T> {
T data;
LinkedList<Node<T>> next;
public Node(T data) {
this.data = data;
this.next = new LinkedList<>();
}
}
```
接下来,我们将实现栈和队列的接口:
```java
public class MyStack<T> {
private Node<T> top;
// 添加元素到顶部
public void push(T item) {
Node<T> newNode = new Node<>(item);
newNode.next.add(top);
top = newNode;
}
// 删除并返回顶部元素
public T pop() {
if (top == null) throw new IllegalStateException("Stack is empty");
T item = top.data;
top = top.next.head();
return item;
}
// 检查栈是否为空
public boolean isEmpty() {
return top == null;
}
}
public class MyQueue<T> {
private Node<T> front, rear;
// 添加元素到队尾
public void enqueue(T item) {
if (rear == null) {
rear = front = new Node<>(item);
} else {
rear.next = new Node<>(item);
rear = rear.next;
}
}
// 从队首删除并返回元素
public T dequeue() {
if (front == null) throw new IllegalStateException("Queue is empty");
T item = front.data;
Node<T> temp = front;
front = front.next;
if (front == null) rear = null;
return item;
}
// 检查队列是否为空
public boolean isEmpty() {
return front == null;
}
}
```
为了验证它们的功能,我们可以创建一个测试类`MyStackAndQueueTest`:
```java
import org.junit.Test;
import static org.junit.Assert.*;
public class MyStackAndQueueTest {
@Test
public void testStack() {
MyStack<Integer> stack = new MyStack<>();
stack.push(1);
stack.push(2);
assertEquals(1, stack.pop());
assertEquals(2, stack.pop());
assertTrue(stack.isEmpty());
}
@Test
public void testQueue() {
MyQueue<Integer> queue = new MyQueue<>();
queue.enqueue(1);
queue.enqueue(2);
assertEquals(1, queue.dequeue());
assertEquals(2, queue.dequeue());
assertTrue(queue.isEmpty());
}
}
```
这个测试类通过添加和删除元素来检查栈和队列的基本操作是否正确。
阅读全文