当前位置：首页 > news >正文

代码随想录刷题day28|（栈与队列篇:栈）232.用栈实现队列

news 2025/2/23 13:06:51

一、栈的基本知识

二、栈在Java中的实现

太长不看简易总结版

1.使用组合模式

2.通过Deque接口

3.基于底层数据结构的实现

使用数组：

使用链表：

4.使用Java的Stack类

三、相关算法题目

四、其他细节

1.组合模式如何通过封装隐藏其他方法？

2.为什么 Stack 类不能隐藏这些破坏栈特性的方法？

3.组合模式中创建对象的具体实现：

4.接口作为类的成员变量

一、栈的基本知识

栈是一种特殊的数据结构，所有的数据操作只能在一端（栈顶）进行操作，特点是先进后出，栈中除了栈顶元素其他都是未知的，栈无法随机访问；比如桶装羽毛球；

入栈：往栈中添加元素的操作，一般叫做push；

出栈：从栈中移除元素的操作，并返回栈顶元素，一般叫做pop，出栈（弹出栈顶元素）；

peek：获取栈顶元素，并不出栈；

注意：这里说的"栈"与内存中的"栈空间"是两个不同的概念，具体不同见⬇️

Java 【数据结构】栈(Stack)和队列(Queue)【神装】_java stack queue-CSDN博客

二、栈在Java中的实现

四种实现方法：

太长不看简易总结版

实现方式	优点	缺点
使用Stack类	简单易用，线程安全	性能较差、设计缺陷
使用Deque接口的实现类	性能高、代码简洁	需自觉遵守栈的规则
组合模式实现栈	隐藏底层实现、灵活性高	需要手动实现栈的逻辑
直接通过数组、链表实现栈	性能高、实现方式更底层	灵活性较低、需要手动实现

1.使用组合模式

组合模式（Composition）是一种设计模式，它通过在一个类中持有另一个类的实例来实现功能，而不是通过继承。组合模式的核心思想是 “优先使用组合，而不是继承” 即：持有实例而不是通过继承。

组合模式的体现：

在栈的实现中，MyStack类持有一个List接口的实例（如 ArrayList），并通过实例来实现栈的功能，而不是继承 List；
这样，MyStack 类可以通过封装隐藏 List 的其他方法（防止破坏栈的特性），只暴露栈的标准接口；
需要手动编写代码实现栈的操作逻辑（如push、pop、peek等）；可以 完全控制栈的行为，隐藏底层数据结构的方法，确保栈的特性不被破坏。

示例代码：

public class MyStack<E> {private List<E> list; // 组合 List 的实例public MyStack() {this.list = new ArrayList<>(); //使用ArrayList实现//将list成员变量初始化为一个 ArrayList对象//创建了一个 ArrayList 的实例，并将其赋值给 list}// 栈的标准方法public void push(E element) {list.add(element);}public E pop() {if (isEmpty()) {throw new RuntimeException("Stack is empty");}return list.remove(list.size() - 1);}public E peek() {if (isEmpty()) {throw new RuntimeException("Stack is empty");}return list.get(list.size() - 1);}public boolean isEmpty() {return list.isEmpty();}
}

2.通过Deque接口

Deque接口（双端队列），支持在队列的两端进行插入和删除操作，继承了对队列Queue接口；

Deque有两个主要的实现类：ArrayDeque（底层使用数组），LinkedList（底层使用双向链表）；

具体实现：

Deque接口的实现类（如 ArrayDeque）提供了栈的标准方法（如 push、pop、peek），直接调用即可；
同时也提供了其他方法（如 addFirst、addLast、removeFirst、removeLast 等），误用可能会破坏栈的特性；
deque的设计目标是灵活，如果像组合模式一样封装，会影响其灵活性，增加代码复杂性，一般不进行封装；

示例代码：

Deque<Integer> stack = new ArrayDeque<>();//创建一个ArrayDeque类的对象stack
stack.push(1);//入栈
stack.push(2);
stack.push(3);System.out.println(stack.pop()); // 输出 3
System.out.println(stack.peek()); // 输出 2

3.基于底层数据结构的实现

直接通过数组或者链表实现栈，不涉及另一个类；

使用数组：

public class ArrayStack<E> {private Object[] elements; // 用数组存储栈元素private int size; // 栈的大小
使用数组来实现栈public ArrayStack() {elements = new Object[10]; // 初始容量size = 0;}// 入栈public void push(E element) {if (size == elements.length) {resize(); // 扩容}elements[size++] = element; // 将元素添加到数组末尾}// 出栈public E pop() {if (isEmpty()) {throw new RuntimeException("Stack is empty");}E element = (E) elements[--size]; // 返回数组的最后一个元素elements[size] = null; // 帮助垃圾回收return element;}// 查看栈顶元素public E peek() {if (isEmpty()) {throw new RuntimeException("Stack is empty");}return (E) elements[size - 1]; // 返回数组的最后一个元素}// 判断栈是否为空public boolean isEmpty() {return size == 0;}// 扩容private void resize() {Object[] newElements = new Object[elements.length * 2];System.arraycopy(elements, 0, newElements, 0, size);elements = newElements;}
}

使用链表：

public class LinkedStack<E> {private static class Node<E> {E element;Node<E> next;Node(E element, Node<E> next) {this.element = element;this.next = next;}}private Node<E> top;private int size;public LinkedStack() {top = null;size = 0;}// 入栈public void push(E element) {top = new Node<>(element, top);size++;}// 出栈public E pop() {if (isEmpty()) {throw new RuntimeException("Stack is empty");}E element = top.element;top = top.next;size--;return element;}// 查看栈顶元素public E peek() {if (isEmpty()) {throw new RuntimeException("Stack is empty");}return top.element;}// 判断栈是否为空public boolean isEmpty() {return size == 0;}
}

4.使用Java的Stack类

Java 的Stack类是基于 Vector 实现的，而 Vector 是一个过时的类，存在以下问题：

Stack继承自 Vector ，而Vector 是一个动态数组，提供了许多栈不需要的方法（如随机访问、插入、删除等），破坏了栈先进后出的特性；
Vector 的所有方法都加了 synchronized关键字，虽保证了线程安全，但在单线程下导致性能下降；

三、相关算法题目

232.用栈实现队列（使用Deque接口的ArrayDeque实现类）

232. 用栈实现队列 - 力扣（LeetCode）

class MyQueue {//成员变量 接口也可以作为成员变量private Deque<Integer> stack1;//用于入栈private Deque<Integer> stack2;//用于出栈public MyQueue() {//构造函数this.stack1 = new ArrayDeque<>(); //初始化stack1this.stack2 = new ArrayDeque<>();//初始化stack2}//成员方法public void push(int x) {stack1.push(x);}public int pop() {//先判断stack2是否为空if(stack2.isEmpty()){//为空 将stack1中的元素全部压入stack2while(!stack1.isEmpty()){stack2.push(stack1.pop());}//全部压入以后 再弹出stack2的栈顶元素}//不为空 直接弹出stack2中的元素if(stack2.isEmpty()){return -1;}return stack2.pop();}       public int peek() {if(stack2.isEmpty()){while(!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.peek();        }    public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}

四、其他细节

1.组合模式如何通过封装隐藏其他方法？

封装将类的内部状态（成员变量）和方法实现隐藏起来，只通过公共方法（如 push、pop、peek）来操作类的内部状态，而不是直接访问成员变量。
list是 MyStack 类的私有成员变量，外部无法直接访问。
MyStack 类只暴露了 push、pop、peek 等栈的标准方法，而没有暴露 list 的其他方法（如 add(int index, E element)、remove(int index) 等）。
这样，外部调用者只能通过栈的标准接口来操作栈，而无法直接操作底层 List，从而确保栈的特性不被破坏。

2.为什么`Stack`类不能隐藏这些破坏栈特性的方法？

Stack 类继承自 Vector，而 Vector 提供了许多不适合栈操作的方法（如 add(int index, E element)、remove(int index) 等）。由于继承关系，Stack 类会继承这些方法，导致栈的特性被破坏。

3.组合模式中创建对象的具体实现：

创建 MyStack 对象：当调用 MyStack<Integer> stack = new MyStack<>(); 时，会执行 MyStack 类的构造函数，创建一个MyStack 类的对象stack；
初始化list：在构造函数中，this.list = new ArrayList<>(); 将 list 初始化为一个 ArrayList 对象，new ArrayList<>() 创建了一个 ArrayList的实例，并将其赋值给list；
结果：stack 对象的 list 成员变量指向一个 ArrayList对象，可以通过list调用 ArrayList 的方法（如 add、remove 等）；
stack.push(1) 实际执行的是list.add(1);