数据结构与算法-栈和队列
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();
}
}