LeetCode算法题-Implement Stack Using Queues


这是悦乐书的第193次更新,第198篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第54题(顺位题号是225)。使用队列实现栈的以下操作:

push(x) - 将元素x推入栈。
pop() - 删除栈顶部的元素。
top() - 获取顶部元素。
empty() - 返回栈是否为空。

例如:

MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.top(); //返回2
stack.pop(); //返回2
stack.empty(); //返回false

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

借助ArrayList。进栈利用list的add方法。出栈时先获取list最后一位元素存起来,然后再删除最后一位元素,再返回先前存起来的最后一位元素。获取栈顶时,返回list最后一位元素即可。判空可以直接利用list的isEmpty方法。

class MyStack {
    List<Integer> list = null;
    /** Initialize your data structure here. */
    public MyStack() {
        list = new ArrayList<Integer>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        list.add(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        int top = list.get(list.size()-1);
        list.remove(list.size()-1);
        return top;
    }

    /** Get the top element. */
    public int top() {
        return list.get(list.size()-1);
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return list.isEmpty();
    }
}


03 第二种解法

利用队列。

进栈直接使用queue的add方法或者offer方法。

出栈时,因为队列是先进先出的特性,所以需要先把队列里的元素poll出来再add进去,但是此操作只能进行queue的size-1次,比如:进栈顺序是1->2->3,进行一次出队列再进队列操作后,2->3->1,再进行一次出队列再进队列的操作,3->1->2,如果你再操作一次就还原了,所以只能操作queue的size-1次。最后再使用队列的poll方法,实现出栈。

栈顶,和出栈的思路一样,不过在把队列里的元素poll出来再add进去size-1次后,先要将顶获取到,可以直接使用队列的peek方法,然后再来一次poll出来再add进去,就把队列元素的顺序还原了。方便下次操作。

判空可以直接使用队列自身的isEmpty方法。

class MyStack2 {

    Queue<Integer> queue = null;
    int size ;

    /** Initialize your data structure here. */
    public MyStack2() {
        queue = new LinkedList<Integer>();
        size = 0;
    }

    /** Push element x onto stack. */
    public void push(int x) {
        queue.add(x);
        size++;
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        for (int i=1; i<size; i++) {
            queue.add(queue.poll());
        }
        size--;
        return queue.poll();
    }

    /** Get the top element. */
    public int top() {
        for (int i=1; i<size; i++) {
            queue.add(queue.poll());
        }
        int res = queue.peek();
        queue.add(queue.poll());
        return res;
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}


04 第三种解法

还是使用队列。不过此解法除了入栈重新实现外,其他的出栈、栈顶、判空都是使用了队列的方法,所以重点讲下入栈即可。

入栈时,首先利用队列的add方法,然后利用循环,把队列里的元素poll出来再add进去,此循环只执行队列的size-1次,执行size次会还原。

class MyStack3 {

    Queue<Integer> queue = null;

    /** Initialize your data structure here. */
    public MyStack3() {
        queue = new LinkedList<Integer>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        queue.add(x);
        for (int i=0; i<queue.size()-1; i++) {
            queue.add(queue.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();
    }
}


05 小结

算法专题目前已连续日更超过一个月,算法题文章54+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!


作者:小川94,发布于:2018/12/06
原文:https://www.cnblogs.com/xiaochuan94/p/10079461.html