数组实现队列和栈
一句话总结
用数组作为底层数据结构实现栈和队列：栈用动态数组尾部作为栈顶（O(1)），队列用环形数组实现 FIFO 操作（O(1)）。
关键要点
1. 用数组实现栈
- 方法：把动态数组的尾部作为栈顶
- 时间复杂度：
push()- O(1)：arr.add(e)pop()- O(1)：arr.remove(arr.size() - 1)peek()- O(1)：arr.get(arr.size() - 1)
- 为什么不选头部作为栈顶：数组头部增删是 O(n)，不符合栈的效率要求
2. 用环形数组实现栈
- 方法：使用
CycleArray类，以头部作为栈顶 - 时间复杂度：O(1)（环形数组头部增删是 O(1)）
- API 映射：
push()→addFirst()pop()→removeFirst()
3. 用环形数组实现队列
- 方法：复用
CycleArray类实现标准队列 - 时间复杂度：O(1)
- API 映射：
push()→addLast()（入队）pop()→removeFirst()（出队）peek()→getFirst()
代码示例
数组实现栈
public class MyArrayStack<E> {
private ArrayList<E> arr = new ArrayList<>();
// 向栈顶加入元素，时间复杂度 O(1)
public void push(E e) {
arr.add(e);
}
// 从栈顶弹出元素，时间复杂度 O(1)
public E pop() {
return arr.remove(arr.size() - 1);
}
// 查看栈顶元素，时间复杂度 O(1)
public E peek() {
return arr.get(arr.size() - 1);
}
// 返回栈中的元素个数，时间复杂度 O(1)
public int size() {
return arr.size();
}
}
环形数组实现队列
public class MyArrayQueue<E> {
private CycleArray<E> arr;
public MyArrayQueue() {
arr = new CycleArray<>();
}
public void push(E t) {
arr.addLast(t);
}
public E pop() {
return arr.removeFirst();
}
public E peek() {
return arr.getFirst();
}
public int size() {
return arr.size();
}
}