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.

Notes:

You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue -- which means only push to back, pop from front, size, and is empty operations are valid.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and all test cases.

用队列Queues的基本操作来实现栈Stack，队列和栈都是重要的数据结构，区别主要是，队列是先进先出，而栈是先进后出。

解法1: 在队列push进来新元素时，就把其它元素pop出来排到新元素的后面，新元素就在前面了，就可以后进先出。就好像大家都在排队，来了个重要客人，要让他第一，其他人从前面按顺序跑到他后面。

解法2: push的时候，其他元素不动只是用一个变量记住这个新元素。当top的时候直接给这个变量的值。当pop时，在调整顺序，把最后一个排到前面，弹出。变量记住目前在最尾部的值。

Java:

class MyStack {

    LinkedList<Integer> queue1 = new LinkedList<Integer>();

    LinkedList<Integer> queue2 = new LinkedList<Integer>();

    // Push element x onto stack.

    public void push(int x) {

        if(empty()){

            queue1.offer(x);

        }else{

            if(queue1.size()>0){

                queue2.offer(x);

                int size = queue1.size();

                while(size>0){

                    queue2.offer(queue1.poll());

                    size--;

                }

            }else if(queue2.size()>0){

                queue1.offer(x);

                int size = queue2.size();

                while(size>0){

                    queue1.offer(queue2.poll());

                    size--;

                }

            }

        }

    }

    // Removes the element on top of the stack.

    public void pop() {

        if(queue1.size()>0){

            queue1.poll();

        }else if(queue2.size()>0){

            queue2.poll();

        }

    }

    // Get the top element.

    public int top() {

       if(queue1.size()>0){

            return queue1.peek();

        }else if(queue2.size()>0){

            return queue2.peek();

        }

        return 0;

    }

    // Return whether the stack is empty.

    public boolean empty() {

        return queue1.isEmpty() & queue2.isEmpty();

    }

}

Python: Time: push: O(n), pop: O(1), top: O(1)， Space： O(n)

class Queue:

    def __init__(self):

        self.data = collections.deque()

    def push(self, x):

        self.data.append(x)

    def peek(self):

        return self.data[0]

    def pop(self):

        return self.data.popleft()

    def size(self):

        return len(self.data)

    def empty(self):

        return len(self.data) == 0

class Stack:

    # initialize your data structure here.

    def __init__(self):

        self.q_ = Queue()

    # @param x, an integer

    # @return nothing

    def push(self, x):

        self.q_.push(x)

        for _ in xrange(self.q_.size() - 1):

            self.q_.push(self.q_.pop())

    # @return nothing

    def pop(self):

        self.q_.pop()

    # @return an integer

    def top(self):

        return self.q_.peek()

    # @return an boolean

    def empty(self):

        return self.q_.empty()

Python: Time: push: O(1), pop: O(n), top: O(1)，Space: O(n)

class Stack:

    # initialize your data structure here.

    def __init__(self):

        self.q_ = Queue()

        self.top_ = None

    # @param x, an integer

    # @return nothing

    def push(self, x):

        self.q_.push(x)

        self.top_ = x

    # @return nothing

    def pop(self):

        for _ in xrange(self.q_.size() - 1):

            self.top_ = self.q_.pop()

            self.q_.push(self.top_)

        self.q_.pop()

    # @return an integer

    def top(self):

        return self.top_

    # @return an boolean

    def empty(self):

        return self.q_.empty()

类似题目：

[LeetCode] 232. Implement Queue using Stacks 用栈来实现队列

All LeetCode Questions List 题目汇总

巴特西

[LeetCode] 225. Implement Stack using Queues 用队列来实现栈

All LeetCode Questions List 题目汇总

最新文章

热门文章