使用队列实现栈的下列操作： push(x) -- 元素 x 入栈 pop() -- 移除栈顶元素 top() -- 获取栈顶元素 empty() -- 返回栈是否为空

柔光的暖阳◎ 2023-01-09 15:31 105阅读 0赞

## 思路 ##

创建两个队列A和B，先将元素入A队列，元素入队列后，再依次出队列到B中，直到A中的元素剩下最后一个的时候，再将这个元素出队列，就可以完成栈中的后进先出的过程

## 代码 ##

public class TestDemo21_2 {
        
        private Queue<Integer> A = new LinkedList<>();
        private Queue<Integer> B = new LinkedList<>();
    
        /** Push element x onto stack. */
        public void push(int x) {
        
            //x往A中入队列即可
            A.offer(x);
        }
    
        /** Removes the element on top of the stack and returns that element. */
        public Integer pop() {
        
            if (empty()){
        
                return null;
            }
            //把A中的元素放入B中
            while (A.size() > 1){
        
                Integer fong = A.poll();
                if (fong == null){
        
                    //A是空的队列
                    break;
                }
                B.offer(fong);
            }
            //当循环结束之后，A中只有一个元素
            int ret = A.poll();
            //交换A和B的身份
            swapAB();
            return ret;
        }
    
        private void  swapAB(){
        
            Queue<Integer> tmp = A;
            A = B;
            B = tmp;
        }
    
        /** Get the top element. */
        public Integer top() {
        
            if (empty()){
        
                return null;
            }
            //把A中的元素放入B中
            while (A.size() > 1){
        
                Integer fong = A.poll();
                if (fong == null){
        
                    //A是空的队列
                    break;
                }
                B.offer(fong);
            }
            //当循环结束之后，A中只有一个元素
            int ret = A.poll();
            B.offer(ret);
            //交换A和B的身份
            swapAB();
            return ret;
        }
    
        /** Returns whether the stack is empty. */
        public boolean empty() {
        
            return A.isEmpty() && B.isEmpty();
        }
    }