[Java每日一练] 两个栈实现一个队列 || 两个队列实现一个栈

问题一：两个栈，实现一个队列。

思路：

  用两个栈，分为添加元素栈、移除元素栈。

• 添加元素栈：一直向该栈添加元素

• 移除元素栈：

    如果该栈为空，将添加元素栈的元素都移到移除元素栈，再将栈顶元素移除。

    如果该栈不为空，直接移除栈顶元素。

public class StackQueueDemo {
    Stack<Object> stackPush = new Stack<>();
    Stack<Object> stackPop = new Stack<>();
    int count = 0;

    public void push(Object obj){
        stackPush.push(obj);
        count++;
    }

    public Object pop(){
        if(stackPop.isEmpty()){
            if(stackPush.isEmpty()){
                throw new RuntimeException("队列中元素为空，无法出队列。");
            }else{
                while(!stackPush.isEmpty()) {
                    stackPop.push(stackPush.pop());
                }
            }
        }
        Object pop = stackPop.pop();
        count--;
        return pop;
    }

    public int size(){
        return count;
    }

    @Override
    public String toString() {
        return "StackQueueDemo{" +
                "stackPush=" + stackPush +
                ", stackPop=" + stackPop +
                ", count=" + count +
                '}';
    }
    
    public static void main(String[] args){
        StackQueueDemo sqd = new StackQueueDemo();
        try {
            sqd.push("北京");
            sqd.push("上海");
            sqd.push("杭州");
            sqd.pop();
            sqd.pop();
            sqd.push("深圳");
            sqd.push("四川");
            System.out.println(sqd);

            int count = sqd.size();
            for (int i = 0; i < count; i++) {
                System.out.println(sqd.pop());
            }
        }catch (Exception e){
            System.out.println(e.getMessage());
        }
    }
}
           

问题二：两个队列，实现一个栈。

思路：

  除了第一次没有add元素外，两个队列始终都是只有一个为空。

• 添加元素：向非空队列添加元素，
• 移除元素：向空队列添加元素直到非空剩余最后一个元素。

public class QueueStackDemo {
    Queue queue1 = new LinkedList();
    Queue queue2 = new LinkedList();
    int count = 0;

    public void add(Object obj){
        if(!queue1.isEmpty())
            queue1.add(obj);
        else
            queue2.add(obj);
        count++;
    }

    public Object remove(){
        if(queue1.isEmpty() && queue2.isEmpty()){
            throw new RuntimeException("栈为空，出栈异常。");
        }else{
            Object obj = null;
            if(!queue1.isEmpty()){
                while(queue1.size()>1){
                    queue2.offer(queue1.poll());
                }
                obj = queue1.poll();
            }else{
                while(queue2.size()>1){
                    queue1.offer(queue2.poll());
                }
                obj = queue2.poll();
            }
            count--;
            return obj;
        }
    }

    public int size(){
        return count;
    }

    @Override
    public String toString() {
        return "QueueStackDemo{" +
                "queue1=" + queue1 +
                ", queue2=" + queue2 +
                ", count=" + count +
                '}';
    }

    public static void main(String[] args){
        QueueStackDemo qsd = new QueueStackDemo();
        try {
            qsd.add("北京");
            qsd.add("深圳");
            qsd.remove();
            qsd.add("上海");
            qsd.remove();
            qsd.add("杭州");
            qsd.add("苏州");

            int count = qsd.size();
            for (int i = 0; i < count; i++) {
                System.out.println(qsd.remove());
            }
        }catch (Exception e){
            System.out.println(e.getMessage());
        }
    }
}