[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());
        }
    }
}