暂无图片
暂无图片
暂无图片
暂无图片
暂无图片

Leetcode刷题之栈与队列(上篇)

码农的修炼之道 2020-02-03
110

     今天是新年初四,湖北的疫情牵动着大家的心,我们能做的就是支付宝里捐点爱心,在家不给国家惹麻烦。今天继续聊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道经典的栈和队列互相使用的情况,让我们对栈和队列的特性有了更深的理解。后续我们有空找几道经典的题目继续练练手。

文章转载自码农的修炼之道,如果涉嫌侵权,请发送邮件至:contact@modb.pro进行举报,并提供相关证据,一经查实,墨天轮将立刻删除相关内容。

评论