题目描述

如何用队列结构实现栈的push和pop操作。

队列和栈的概念

队列：先进先出，从头进，从尾出。

栈：先进后出，从头进，从头出。

解题思路

本题需要借助两个队列，通过让元素在两个队列中切换，来实现栈的功能。

假设分别有A、B两个队列，以及一个int类型的标识符F，当要添加元素时，如果F等于0，则添加到队列A中，否则添加到队列B中，

当要弹出元素时，如果F等于0，则先把队列A中的数据依次弹出并添加到队列B中，直到队列A中还剩最后一个元素时，则直接弹出，并设置F等于1，返回弹出元素。如果F等于1，则先把队列B中的数据依次弹出并添加到队列A中，直到队列B中还剩最后一个元素时，则直接弹出，并设置F等于0，返回弹出元素。

图解分析

1、假设现在要添加了3个元素，分别为：1，2，3

2、弹出一个元素

在这里插入图片描述

3、当又需要添加一个元素时。

在这里插入图片描述

4、当又要弹出一个元素时

在这里插入图片描述

5、如果继续需要弹出元素

在这里插入图片描述

代码实现

class MyStack {
       Queue
   
     queue_one = new LinkedList<>();    Queue
    
      queue_two = new LinkedList<>();    int flag = 0;    /**     * Initialize your data structure here.     */    public MyStack() {
       }    /**     * Push element x onto stack.     */    public void push(int x) {
           if (flag == 0) {
               queue_one.add(x);        } else {
               queue_two.add(x);        }    }    /**     * Removes the element on top of the stack and returns that element.     */    public int pop() {
           if (flag == 0) {
               int size = queue_one.size();            for (int i = 0; i < size - 1; i++) {
                   queue_two.add(queue_one.poll());            }            flag = 1;            return queue_one.poll();        } else {
               int size = queue_two.size();            for (int i = 0; i < size - 1; i++) {
                   queue_one.add(queue_two.poll());            }            flag = 0;            return queue_two.poll();        }    }    /**     * Get the top element.     */    public int top() {
           int i = 0;        if (flag == 0) {
               Iterator
     
       iterator = queue_one.iterator();            while (iterator.hasNext()) {
                   i = iterator.next();            }        } else {
               Iterator
      
        iterator = queue_two.iterator();            while (iterator.hasNext()) {
                   i = iterator.next();            }        }        return i;    }    /**     * Returns whether the stack is empty.     */    public boolean empty() {
           return queue_one.isEmpty() && queue_two.isEmpty();    }}

在当前方式下，如果要实现top方法，则需要遍历整个队列，并且直到遍历到最后一个元素时才能得到，在下一遍文章中，我们将通过另一种方式来优化它。

转载地址：http://fqlrb.baihongyu.com/

你可能感兴趣的文章