今天是新年初四,湖北的疫情牵动着大家的心,我们能做的就是支付宝里捐点爱心,在家不给国家惹麻烦。今天继续聊3道栈和队列应用的经典题目。
所谓栈和队列,其实现方式可以基于数组也可以基于链表去实现。都是线性结构。对于栈来说,FILO。对于队列来说FIFO。比如在高并发场景下使用的阻塞队列,线程池中都会涉及到这种数据结构。
155. Min Stack
题目:支持最小值的栈,分别实现下面4个方法。
push(x) -- 压入元素x到栈
pop() -- 从栈顶移除元素
top() -- 获取栈顶元素
getMin() -- 获取栈内的最小值
思路:我们创建两个栈分别为stack和minStack,其中stack用于保存原始值。minStack用于保存目前stack栈内的最小值。主要在push方法中需要处理,当压入第一个元素,此时最小值也是这个元素。因此stack和minStack都要压入。当压入第二个及以上元素时,依然压入stack。但是此时需要看看minStack的栈顶元素是否比当前元素小,如果当前元素较小,则压入当前元素到minStack。否则还是压入minStack的栈顶元素。
参考代码:
class MinStack {
public LinkedList<Integer> stack=new LinkedList<Integer>();
public LinkedList<Integer> minstack=new LinkedList<Integer>();
public void push(int x){
if(stack.size()==0){
stack.push(x);
minstack.push(x);
}else{
stack.push(x);
int min=minstack.peek();
minstack.push(Math.min(x, min));
}
}
public void pop(){
stack.pop();
minstack.pop();
}
public int top(){
return stack.peek();
}
public int getMin(){
return minstack.peek();
}
}
复制
232. Implement Queue using Stacks
题目:使用栈去模拟一个队列的功能。分别实现以下4个方法:
push(x) -- 压入x元素到队列
pop() -- 从队列弹出一个元素
peek() -- 获取队列头部元素
empty() -- 返回队列是否为空
思路:我们可以使用两个栈stack1和stack2,当压入元素时,将元素压入stack1中。如果需要取队列首部元素,此时需要将stack1中元素全部放入stack2中,然后返回stack2中的栈顶元素即可。取队列首部元素也是如此,如果stack2不为空,则直接返回栈顶元素。如果stack2为空,则将stack1元素全部弹出并放入stack2中。总体思路是栈内元素导入另一个栈,就符合队列的FIFO特性了。
参考代码:
class MyQueue {
public Stack<Integer> stack1=new Stack<Integer>();
public Stack<Integer> stack2=new Stack<Integer>();
public int size;
public void push(int x){
stack1.push(x);
size++;
}
public void pop(){
if(!stack2.isEmpty()){
stack2.pop();
}else{
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
stack2.pop();
}
size--;
}
public int peek(){
if(!stack2.isEmpty()){
return stack2.peek();
}else{
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.peek();
}
}
public boolean empty(){
return size==0?true:false;
}
}
复制
225. Implement Stack using Queues
题目:使用队列去模拟一个栈的功能,分别实现以下四个功能。
push(x) --将元素x压入栈
pop() -- 从栈中移除一个元素
top() -- 查看栈顶的元素
empty() -- 判断栈是否为空
思路:和上面的思路类似,使用两个栈queue1和queue2去模拟一个队列的功能。压入元素的时候,queue1不为空则放入queue1,否则放入queue2中。弹出元素的时候,比如queue1不为空,则弹出其他元素放入queue2中,只保留一个元素最后弹出即可。查看栈顶元素也是类似,总之,一个队列只是作为辅助队列使用。
参考代码:
class MyStack {
public Queue<Integer> queue1=new LinkedList<Integer>();
public Queue<Integer> queue2=new LinkedList<Integer>();
private int size;
public void push(int x) {
if(empty()||!queue1.isEmpty())
queue1.offer(x);//压入元素
else
queue2.offer(x);
size++;
}
public void pop() {
if(!queue1.isEmpty()){
while(queue1.size()>1)
queue2.offer(queue1.poll());
queue1.poll();
}else{
while(queue2.size()>1)
queue1.offer(queue2.poll());
queue2.poll();
}
size--;
}
public int top() {
if(!queue1.isEmpty()){
while(queue1.size()>1)
queue2.offer(queue1.poll());
int k=queue1.poll();
queue2.offer(k);
return k;
}else{
while(queue2.size()>1)
queue1.offer(queue2.poll());
int k=queue2.poll();
queue1.offer(k);
return k;
}
}
public boolean empty() {
return size==0?true:false;
}
}
复制
总结:今天一起刷了3道经典的栈和队列互相使用的情况,让我们对栈和队列的特性有了更深的理解。后续我们有空找几道经典的题目继续练练手。