数据结构Java版构建顺序栈和链栈,实现栈判空、出栈、入栈、取栈顶元素、遍历栈元素,统计栈元素个数等操作。
时间: 2024-12-12 12:18:42 浏览: 13
在Java中,我们可以用数组(顺序栈)和链表(链栈)来实现基本的栈数据结构。这里分别解释一下:
1. **顺序栈(Array Stack)**,通常基于数组实现:
```java
public class ArrayStack {
private int[] stack;
private int top;
// 构造函数,初始化栈容量
public ArrayStack(int capacity) {
stack = new int[capacity];
top = -1;
}
// 判空
public boolean isEmpty() {
return top == -1;
}
// 入栈(push)
public void push(int value) {
if (top < stack.length - 1) {
top++;
stack[top] = value;
} else {
throw new StackOverflowError();
}
}
// 出栈(pop)
public int pop() {
if (!isEmpty()) {
int value = stack[top];
top--;
return value;
} else {
throw new EmptyStackException();
}
}
// 取栈顶元素(peek)
public int peek() {
if (!isEmpty()) {
return stack[top];
} else {
throw new EmptyStackException();
}
}
// 遍历栈元素
// 注意:由于数组的固定位置,无法直接遍历,一般通过栈迭代器或临时数组存储再遍历
// 这里简化示例只提供部分功能,完整遍历需要额外处理
public void printAll() {
if (!isEmpty()) {
System.out.print(stack[top]);
while (top > 0) {
System.out.print(" -> " + stack[top - 1]);
top--;
}
}
}
// 统计栈元素个数
public int size() {
return top + 1;
}
}
```
2. **链栈(Linked Stack)**,基于链表实现:
```java
public class LinkedStack {
private Node top;
// 简化节点类
static class Node {
int value;
Node next;
Node(int value) {
this.value = value;
}
}
// 初始化
public LinkedStack() {
top = null;
}
// ... (同上其他方法,如isEmpty(), push(), pop(), peek(), printAll(), size())
}
```
阅读全文