java栈的实现,并给出栈的逆序方法
时间: 2024-10-15 19:14:20 浏览: 5
在 Java 中,栈(Stack)通常通过数组或链表(LinkedList)等数据结构来实现。最基础的实现是使用数组,称为固定大小的 Stack。例如:
```java
public class ArrayStack<T> {
private T[] elements;
private int top;
// 构造函数、push、pop 等基本操作...
public void push(T item) {
if (top == elements.length) {
resize(2 * elements.length); // 当栈满时扩大容量
}
elements[top++] = item;
}
public T pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
return elements[--top];
}
// 其他辅助方法...
}
```
对于链表实现的动态大小 Stack,比如 LinkedList,可以更方便地实现:
```java
import java.util.LinkedList;
public class LinkedStack<T> {
private LinkedList<T> list;
public void push(T item) {
list.addFirst(item);
}
public T pop() {
return list.removeFirst();
}
// ...其他方法...
}
```
至于栈的逆序(Reverse Stack),一种常见的方法是使用另一个栈(辅助栈)。首先将原栈的所有元素依次压入辅助栈,然后将辅助栈的元素逐个弹出并压回原栈,从而达到逆序的效果。
以下是逆序栈的简单步骤:
1. 初始化两个空栈辅助栈 `aux` 和目标栈 `target`
2. 循环遍历原栈 `source` 直到它为空:
- 将 `source` 的顶部元素压入 `aux` 栈
3. 再次循环遍历 `aux` 栈并将元素压回 `target`,此时 `target` 的顺序就是原栈的逆序
```java
void reverseStack(Stack source, Stack target) {
while (!source.isEmpty()) {
target.push(source.pop());
}
}
```
阅读全文