利用队列和栈的算法题

栈 先进后出

队列

队列是一种常用的数据结构，可以将队列看做是一种特殊的线性表，遵循先进先出原则。分分为队列queue和双向队列deque。

队列queue

在java中，使用LinkedList实现queue。操作的方法如下：

 抛出异常返回值插入add(e)offer(e)移除remove()poll()检查element()peek()

boolean add(E e);将指定的元素插入此队列（如果立即可行且不会违反容量限制），在成功时返回 true，如果当前没有可用的空间，则抛出 IllegalStateException。

boolean offer(E e);将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，此方法通常要优于 add(E)，后者可能无法插入元素，而只是抛出一个异常。

E remove();获取并移除此队列的头。

E poll();获取并移除此队列的头，如果此队列为空，则返回 null。

E element();获取，但是不移除此队列的头。

E peek();获取但不移除此队列的头；如果此队列为空，则返回 null。

双向队列deque

双向队列(Deque),是Queue的一个子接口，双向队列是指该队列两端的元素既能入队(offer)也能出队(poll),如果将Deque限制为只能从一端入队和出队，则可实现栈的数据结构。对于栈而言，有入栈(push)和出栈(pop)，遵循先进后出原则。(下面几张图参考了https://www.cnblogs.com/shamo89/p/6774080.html这篇文章)

此接口扩展了 Queue 接口。在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，如下表所示

双端队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：

注意，在将双端队列用作队列或堆栈时，peek 方法同样正常工作；无论哪种情况下，都从双端队列的开头抽取元素。

力扣习题

225. 用队列实现栈

使用队列实现栈的下列操作：

push(x) -- 元素 x 入栈 pop() -- 移除栈顶元素 top() -- 获取栈顶元素 empty() -- 返回栈是否为空

用队列实现栈主要是实现push方法

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

232. 用栈实现队列

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。

用栈实现队列主要是实现pop()和peek()方法

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

155. 最小栈

这个题目可以投机取巧一下，使用两个栈来实现最小栈，一个用来正常实现栈的方法，一个用来维护存储最小值

代码如下

class MinStack { private Stack<Integer> stack; private Stack<Integer> min_stack; /** initialize your data structure here. */ public MinStack() { stack=new Stack<>(); min_stack=new Stack<>(); } public void push(int x) { stack.push(x); if(min_stack.isEmpty() || x<=min_stack.peek()){ min_stack.push(x); } } public void pop() { Integer temp=stack.pop(); if(temp.equals(min_stack.peek())){ min_stack.pop(); } } public int top() { return stack.peek(); } public int getMin() { return min_stack.peek(); } }

这里可以小小的优化一下，存储最小值用一个变量来实现，具体代码如下

class MinStack { private int min = Integer.MAX_VALUE; private Stack<Integer> stack; /** initialize your data structure here. */ public MinStack() { stack = new Stack<>(); } public void push(int x) { if(min >= x){ stack.push(min); min = x; } stack.push(x); } public void pop() { if(stack.pop() == min){ min = stack.pop(); } } public int top() { return stack.peek(); } public int getMin() { return min; }}

也可以使用一个栈来实现，一次压入两个值，一个是要压入的值，一个是当前的最小值

class MinStack { private Stack<Integer> stack; /** initialize your data structure here. */ public MinStack() { stack=new Stack<>(); } public void push(int x) { if(stack.isEmpty()){ stack.push(x); stack.push(x); }else{ int temp=stack.peek(); stack.push(x); if(temp<x){ stack.push(temp); }else{ stack.push(x); } } } public void pop() { stack.pop(); stack.pop(); } public int top() { return stack.get(stack.size()-2); } public int getMin() { return stack.peek(); } }

用链表来实现最小栈

class MinStack { public MinStack(){ } public void push(int x){ if(head==null){ head=new Node(x,x); }else{ head=new Node(x,Math.min(x,head.min),head); } } public void pop(){ head=head.next; } public int top(){ return head.val; } public int getMin(){ return head.min; } private class Node{ int val; int min; Node next; private Node(int val,int min){ this(val,min,null); } private Node(int val,int min,Node next){ this.val=val; this.min=min; this.next=next; } } }

剑指 Offer 59 - II. 队列的最大值

这种题就是实现API,根据题目要设计好每个方法就好，首先为了可以以o1的时间拿出最大值，那么我们就要维护一个数据结构来保存每一次的最大值。我们采用两个队列来实现，其中一个是双向队列，用于维护最大值。

首先在调用max_value方法的时候，我们使用b.peek()直接获取队列的头部，因此在设计push方法时，维护的队列应该是单调的，并且队首应是最大值。

在push方法中，每次push一个数x的时候，对于双向列表，先从尾部开始判断，如果当前尾部值小于x,则删除，直到尾部值大于x，此时将x加入尾部。

在pop方法中，在删除a头部的元素时，要判断此时是否和当前的b头部最大值相等，如果相等则都要删除。

代码如下

class MaxQueue { Queue<Integer> a; Queue<Integer> b; public MaxQueue() { a=new LinkedList<>(); b=new LinkedList<>(); //用于维护最大值队列 } public int max_value() { return a.isEmpty()?-1:b.peek(); //返回最大值队列的头部 } public void push_back(int value) { a.offer(value); while(!b.isEmpty() && value>b.peekLast()){ b.pollLast(); } b.offer(value); } public int pop_front() { if(a.isEmpty()){ return -1; } int temp=a.poll(); if(temp==b.peek()){ b.poll(); } return temp; } }

239. 滑动窗口最大值

剑指 Offer 59 - I. 滑动窗口的最大值

这两个是一道题，和上一题有所关联，放在一起做，本质就是维护一个滑动窗口。判断里面的最大值。

最开始使用的是暴力法，对每一个长度为k的滑动窗口进行遍历，保存最大值

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int len=nums.length; if(nums==null || len<1) return new int[0]; int[] res=new int[len-k+1]; for(int i=0;i<=len-k;i++){ res[i]=max_value(nums,i,i+k); //传入所有的窗口 } return res; } private int max_value(int[] nums,int left,int right){ //遍历传递的窗口范围，返回最大值 int max=nums[left]; for(int i=left+1;i<right;i++){ if(nums[i]>max){ max=nums[i]; } } return max; } }

可以对上面的暴力法进行优化，通过分析我们可以知道，每一次都要遍历是有点重复的，那么我们可以想想办法减少遍历的次数。通过使用窗口。比如说窗口的长度为3，假如说最大值是第二个，那么，这个时候，滑动窗口向右滑动一格，其实没有必要全部判断一次，因为前两个在上一轮中已经判断过了，所以只需要判断新加入的就好了。如果说最大值是第一个，滑动窗口向右滑动一个之后，最大值就不再这个窗口里了，那么只能全部遍历了。

代码如下：

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int len=nums.length; int count=0; if(nums==null || len==0) return new int[0]; int max=0,left=0,right=k-1,index=-1,count=0; int[] res=new int[len-k+1]; while(right<len){ if(index>=left){ //说明最大值的索引还在滑动窗口里，只需要比较最右边的数值 if(nums[right]>=max){ index=right; max=nums[right]; } }else{ //说明此时最大值的索引已经不在滑动窗口里了，需要遍历整个窗口长度 max=nums[left]; //很重要 index=left; for(int i=left+1;i<=right;i++){ if(nums[i]>=max){ index=i; max=nums[i]; } } } left++; //滑动窗口移动 right++; res[count++]=max; //保存结果 } return res; } }

也可以维护一个单调栈，新来的数和队尾的数比较，如果队尾的数小于新来的数则不断移除，直至不小于或者队列为空。这样移动窗口之后，只需要取队头的数即为最大值。当滑动窗口的长度大于k时，对不要的进行移除

代码如下

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int len=nums.length; int count=0; if(nums==null || len==0) return new int[0]; int[] res=new int[len-k+1]; Deque<Integer> deque=new ArrayDeque<>(); for(int i=0;i<len;i++){ if(i>=k && deque.peekFirst()==nums[i-k]) deque.removeFirst(); //移除已经不在窗口里的数 while(!deque.isEmpty() && deque.peekLast()<nums[i]){ deque.pollLast(); } deque.offer(nums[i]); if(i>=k-1) res[count++]=deque.peekFirst(); //当i达到k的长度之后，每次循环要记录此时窗口的最大值 } return res; } }