题目详细思路来自于:代码随想录 (programmercarl.com)
栈和队列都是大家不陌生的数据结构,我们之前的栈和队列一般是用数组或链表来实现的 ,
这里我们给出实现方式,用于帮助更好的理解.
1.用链表实现栈
/* 基于链表实现的栈 */ class LinkedListStack { private ListNode stackPeek; // 将头节点作为栈顶 private int stkSize = 0; // 栈的长度 public LinkedListStack() { stackPeek = null; } /* 获取栈的长度 */ public int size() { return stkSize; } /* 判断栈是否为空 */ public boolean isEmpty() { return size() == 0; } /* 入栈 */ public void push(int num) { ListNode node = new ListNode(num); node.next = stackPeek; stackPeek = node; stkSize++; } /* 出栈 */ public int pop() { int num = peek(); stackPeek = stackPeek.next; stkSize--; return num; } /* 访问栈顶元素 */ public int peek() { if (size() == 0) throw new IndexOutOfBoundsException(); return stackPeek.val; } /* 将 List 转化为 Array 并返回 */ public int[] toArray() { ListNode node = stackPeek; int[] res = new int[size()]; for (int i = res.length - 1; i >= 0; i--) { res[i] = node.val; node = node.next; } return res; } }
2.用数组实现栈
class ArrayStack { private ArrayList<Integer> stack; public ArrayStack() { // 初始化列表（动态数组） stack = new ArrayList<>(); } /* 获取栈的长度 */ public int size() { return stack.size(); } /* 判断栈是否为空 */ public boolean isEmpty() { return size() == 0; } /* 入栈 */ public void push(int num) { stack.add(num); } /* 出栈 */ public int pop() { if (isEmpty()) throw new IndexOutOfBoundsException(); return stack.remove(size() - 1); } /* 访问栈顶元素 */ public int peek() { if (isEmpty()) throw new IndexOutOfBoundsException(); return stack.get(size() - 1); } /* 将 List 转化为 Array 并返回 */ public Object[] toArray() { return stack.toArray(); } }
3.两种实现的优缺点
3.1 用数组实现栈的优缺点
在基于数组的实现中，入栈和出栈操作都是在预先分配好的连续内存中进行，具有很好的缓存本地性，因此效率较高。然而，如果入栈时超出数组容量，会触发扩容机制，导致该次入栈操作的时间复杂度变为 𝑂(𝑛).
3.2 用链表实现栈的优缺点
在链表实现中，链表的扩容非常灵活，不存在上述数组扩容时效率降低的问题。但是，入栈操作需要初始化节点对象并修改指针，因此效率相对较低。不过，如果入栈元素本身就是节点对象，那么可以省去初始化步骤，从而提高效率。
4. 用链表实现队列
class LinkedListQueue { private ListNode front, rear; // 头节点 front ，尾节点 rear private int queSize = 0; public LinkedListQueue() { front = null; rear = null; } /* 获取队列的长度 */ public int size() { return queSize; } /* 判断队列是否为空 */ public boolean isEmpty() { return size() == 0; } /* 入队 */ public void push(int num) { // 尾节点后添加 num ListNode node = new ListNode(num); // 如果队列为空，则令头、尾节点都指向该节点 if (front == null) { front = node; rear = node; // 如果队列不为空，则将该节点添加到尾节点后 } else { rear.next = node; rear = node; } queSize++; } /* 出队 */ public int pop() { int num = peek(); // 删除头节点 front = front.next; queSize--; return num; } /* 访问队首元素 */ public int peek() { if (size() == 0) throw new IndexOutOfBoundsException(); return front.val; } /* 将链表转化为 Array 并返回 */ public int[] toArray() { ListNode node = front; int[] res = new int[size()]; for (int i = 0; i < res.length; i++) { res[i] = node.val; node = node.next; } return res; } }
5.用数组实现队列
你可能会发现一个问题：在不断进行入队和出队的过程中， front 和 rear 都在向右移动， 当它们到达数组尾部时就无法继续移动了。为解决此问题，我们可以将数组视为首尾相接的“环形数组”。对于环形数组，我们需要让 front 或 rear 在越过数组尾部时，直接回到数组头部继续遍历。这种周期性规律可以通过“取余操作”来实现
/* 基于环形数组实现的队列 */ class ArrayQueue { private int[] nums; // 用于存储队列元素的数组 private int front; // 队首指针，指向队首元素 private int queSize; // 队列长度 public ArrayQueue(int capacity) { nums = new int[capacity]; front = queSize = 0; } /* 获取队列的容量 */ public int capacity() { return nums.length; } /* 获取队列的长度 */ public int size() { return queSize; } /* 判断队列是否为空 */ public boolean isEmpty() { return queSize == 0; } /* 入队 */ public void push(int num) { if (queSize == capacity()) { System.out.println(" 队列已满"); return; } // 计算尾指针，指向队尾索引 + 1 // 通过取余操作，实现 rear 越过数组尾部后回到头部 int rear = (front + queSize) % capacity(); // 将 num 添加至队尾 nums[rear] = num; queSize++; } /* 出队 */ public int pop() { int num = peek(); // 队首指针向后移动一位，若越过尾部则返回到数组头部 front = (front + 1) % capacity(); queSize--; return num; } /* 访问队首元素 */ public int peek() { if (isEmpty()) throw new IndexOutOfBoundsException(); return nums[front]; } /* 返回数组 */ public int[] toArray() { // 仅转换有效长度范围内的列表元素 int[] res = new int[queSize]; for (int i = 0, j = front; i < queSize; i++, j++) { res[i] = nums[j % capacity()]; } return res; } }
LeetCode T232 用栈实现队列
题目链接:
题目思路:
我们这里就要用两个栈来实现队列,一个是stackOut,一个是stackIn,in栈负责将要入队的添加进来,但是这时候我们发现出栈的话会和队列的出队顺序相反,所以我们再入栈一次,这样出栈的顺序就颠倒过来啦,也完美的实现队列的基本功能.
注:一定要将In栈的全部元素一起push进Out栈,否则顺序可能会发生变化,这样就影响了正常的出栈功能.
题目代码:
class MyQueue { Stack<Integer> stackIn; Stack<Integer> stackOut; public MyQueue() { stackIn = new Stack<>(); stackOut = new Stack<>(); } public void push(int x) { stackIn.push(x); } public int pop() { downStackIn(); return stackOut.pop(); } public int peek() { downStackIn(); return stackOut.peek(); } public boolean empty() { downStackIn(); return stackOut.isEmpty(); } public void downStackIn() { while(!stackOut.isEmpty()) { return; } while(!stackIn.isEmpty()) { stackOut.push(stackIn.pop()); } } } /** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */
LeetCode T225 用队列实现栈
题目链接:225. 用队列实现栈 - 力扣（LeetCode）
题目思路:
这里我们同样可以用和上一题同样的思路实现,但是为了更有挑战性,我们决定用一个队列来实现栈,假设我们入队元素是123,此时我们需要的出队元素应该是3,那么我们该如何操作呢,其实,我们只需要让前两个元素重新入队,这样第一个出队的元素就是3了,其实就是前size()-1个元素重新入队,就实现了出栈的操作
这里我使用的是deque,这个类可以实现两头的操作,就是比queue多了两头操作的一些方法.
题目代码:
class MyStack { Deque<Integer> que1; public MyStack() { que1 = new ArrayDeque<>(); } public void push(int x) { que1.addLast(x); } public int pop() { int tmp = que1.size()-1; while(tmp>0) { que1.addLast(que1.peekFirst()); que1.pollFirst(); tmp--; } return que1.pollFirst(); } public int top() { return que1.peekLast(); } public boolean empty() { return que1.isEmpty(); } } /** * Your MyStack object will be instantiated and called as such: * MyStack obj = new MyStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * boolean param_4 = obj.empty(); */
