数据结构与算法-栈和队列

LeetCode_20 判断括号是否合法

Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid. Input: “()[]{}” Output: true Input: “{[]}” Output: true

新建一个栈，然后遍历字符串，如果遇到左括号，直接压入栈中；如果遇到右括号，则弹出一个栈顶元素，将二者进行匹配，如果二者不匹配，直接返回false；如果匹配，则继续遍历。遍历结束之后，判断栈内元素是否为空，如果为空，则说明括号是合法的。

代码：

class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); Map<Character,Character> map = new HashMap<>(); map.put(')','('); map.put(']','['); map.put('}','{'); for (Character c :s.toCharArray()){ if (!map.containsKey(c)){ stack.push(c); }else { if (stack.isEmpty() || map.get(c) != stack.pop()){ return false; } } } return stack.isEmpty(); } }

LeetCode_225 使用队列实现栈结构

Implement the following operations of a stack using queues. push(x) – Push element x onto stack. pop() – Removes the element on top of the stack. top() – Get the top element. empty() – Return whether the stack is empty.

使用两个队列，一个队列queue用于存放元素和取元素，另一个队列tmp用于临时存放元素。当执行push方法时，需要把queue中的元素取出临时放在tmp队列中，然后把需要push的元素放入queue中，再将tmp队列中的元素放回queue中。

执行pop方法时，只需调用queue队列的poll方法取出队列头的元素。执行top方法时，调用queue队列的peek方法返回队列头元素。执行empty方法需判断queue是否为空。

代码：

class MyStack { LinkedList<Integer> queue; LinkedList<Integer> tmp; /** Initialize your data structure here. */ public MyStack() { queue = new LinkedList<Integer>(); tmp = new LinkedList<Integer>(); } /** Push element x onto stack. */ public void push(int x) { while (!queue.isEmpty()){ tmp.offer(queue.poll()); } queue.offer(x); while (!tmp.isEmpty()){ queue.offer(tmp.poll()); } } /** Removes the element on top of the stack and returns that element. */ public int pop() { return queue.poll(); } /** Get the top element. */ public int top() { return queue.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return queue.isEmpty() && tmp.isEmpty(); } }

LeetCode_232 使用栈实现队列

Implement the following operations of a queue using stacks. push(x) – Push element x to the back of queue. pop() – Removes the element from in front of queue. peek() – Get the front element. empty() – Return whether the queue is empty.

使用两个栈pushStack和popStack，执行push方法时，直接把元素push到pushStack；执行pop和peek方法时，如果popStack中有元素，直接执行popStack的pop或peek；如果popStack中没有元素，把pushStack中的元素一次性全倒入popStack，然后再执行popStack的pop或peek。

代码：

class MyQueue { Stack<Integer> stack1 = new Stack<>(); Stack<Integer> stack2 = new Stack<>(); /** Initialize your data structure here. */ public MyQueue() { } /** Push element x to the back of queue. */ public void push(int x) { stack1.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { if (stack2.isEmpty()){ while (!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.pop(); } /** Get the front element. */ public int peek() { if (stack2.isEmpty()){ while (!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return stack1.isEmpty()&&stack2.isEmpty(); } }

LeetCode_239 滑动窗口的最大值

给定一个数组，有一个k大小的窗口从数组最左滑动到最右，窗口每向右滑动一个位置，返回窗口中k个元素的最大值。

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. Example: Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3 Output: [3,3,5,5,6,7]

代码：

class Solution { public static int[] maxSlidingWindow(int[] nums, int k) { if (nums.length == 0){ return nums; } //用于保存结果的数组，长度为nums.length - k + 1 int[] res = new int[nums.length - k + 1]; //双端队列，里面存放数组下标，队头元素对应的数组值是窗口滑动中的最大值 LinkedList<Integer> queue = new LinkedList<>(); //res结果数组下标 int count = 0; //遍历数组 for (int i=0; i<nums.length; i++){ //如果队尾元素对应的数组值小于数组当前值，则取出队尾元素 while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){ queue.pollLast(); } //把当前数组下标加入队尾 queue.addLast(i); //数组当前下标与队头元素的差值等于k时，说明队头元素已过期，需要移除 if (i >= queue.peekFirst() + k){ queue.pollFirst(); } //当前数组下标遍历到k-1时，开始保存结果，结果值是队头元素对应的数组值 if (i >= k-1){ res[count++] = nums[queue.peekFirst()]; } } return res; } }

LeetCode_703 返回数据流中第K大的元素

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element. Example: int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5 kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8

建立一个由k个元素组成的小根堆，堆顶的元素就是k个元素中的最小值，也就是第k大的元素，当往小根堆中添加元素时，如果需要添加的元素大于堆顶元素，则移除堆顶元素，然后加入新元素，并调整堆结构，再返回堆顶值。可以使用默认的PriorityQueue作为小根堆。如果需要大根堆，则使用PriorityQueue带有Comparator的构造方法即可。

代码：

class KthLargest { private int k; private PriorityQueue<Integer> queue; public KthLargest(int k, int[] nums) { this.k = k; queue = new PriorityQueue<>(k); for (int n : nums){ add(n); } } public int add(int val) { if (queue.size() < k){ queue.offer(val); }else if (queue.peek() <val){ queue.poll(); queue.offer(val); } return queue.peek(); } }