用棧實現(xiàn)隊列和用隊列實現(xiàn)棧

liang1234_ 2019-01-26

展開全文

首先需要使用上篇文章（用數(shù)組實現(xiàn)棧和隊列）中的棧和隊列兩個類

1.棧實現(xiàn)隊列：思路是有兩個棧，一個用來放數(shù)據(jù)（數(shù)據(jù)棧），一個用來輔助（輔助棧）。數(shù)據(jù)添加時，會依次壓人棧，取數(shù)據(jù)時肯定會取棧頂元素，但我們想模擬隊列的先進先出，所以就得取棧底元素，那么輔助棧就派上用場了，把數(shù)據(jù)棧的元素依次彈出到輔助棧，但保留最后一個元素，最后數(shù)據(jù)棧就剩下了最后一個元素，直接把元素返回，這時數(shù)據(jù)棧已經沒有了數(shù)據(jù)。最后呢，把輔助棧的元素依次壓人數(shù)據(jù)棧，這樣，我們成功取到了棧底元素。

代碼如下：

package com.sxt.test.java;

public class Stack2Queue {
    /**
     * 用棧的入棧和出棧
     * 來實現(xiàn)隊列的入隊和出隊
     *  stack1是入棧的，stack2是出棧的。
        入隊列：直接壓入stack1即可
        出隊列：如果stack2不為空，把stack2中的棧頂元素直接彈出；
            否則，把stack1的所有元素全部彈出壓入stack2中，再彈出stack2的棧頂元素
     * */
    Stack stack1 = new Stack();
    Stack stack2 = new Stack();
    public void add(Object o) {
        stack1.push(o);
    }
    
    public Object poll() {
        Object o = null;
        
        if(stack2.length()==0) {
            //把stack1的數(shù)據(jù)放入stack2，留下最后一個數(shù)據(jù)
            while(stack1.length()>1) {
                stack2.push(stack1.pop());
            }
            if(stack1.length()==1) {
                //把stack1的留下的那個數(shù)據(jù)返回出去
                o = stack1.pop();
            }
        }else {
            o = stack2.pop();
        }
        
        return o;
    }
    public int length() {
        return stack1.length()+stack2.length();
    }

}

2.隊列實現(xiàn)棧

思路同上：有數(shù)據(jù)隊列和輔助隊列，模擬棧的先進后出，隊列是隊尾進隊頭出，也就是說每次取值要取隊列的隊尾元素，數(shù)據(jù)隊列出隊到輔助隊列，留下最后一個元素返回，輔助隊列再把元素出隊到數(shù)據(jù)隊列

代碼如下：

package com.sxt.test.java;

public class Queue2Stack {
    /**
     * 用隊列的入隊和出隊
     * 來實現(xiàn)棧的入棧和出棧
     * */
    
    Queue queue1 = new Queue();//主要存放數(shù)據(jù)
    Queue queue2 = new Queue();//輔助
    
    public void push(Object o) {
        queue1.add(o);
    }
    
    public Object pop() {
        Object o = null;
        while(queue1.length()>1) {
            queue2.add(queue1.poll());
        }
        if(queue1.length()==1) {
            o = queue1.poll();
            while(queue2.length()>0) {
                queue1.add(queue2.poll());
            }
        }
        
        return o;
    }
    
    public int length() {
        return queue1.length();
    }
    

}

3.測試類

/**
         * 用兩個棧實現(xiàn)隊列
         * */
        Stack2Queue stack2Queue = new Stack2Queue();
        stack2Queue.add("a");
        stack2Queue.add("b");
        stack2Queue.add("c");
        stack2Queue.add("d");
        stack2Queue.add("e");
        while(stack2Queue.length()>0) {
            System.out.println(stack2Queue.poll());
        }
        
        /**
         * 用兩個隊列實現(xiàn)棧
         * */
        Queue2Stack queue2Stack = new Queue2Stack();
        queue2Stack.push("a");
        queue2Stack.push("c");
        queue2Stack.pop();
        queue2Stack.push("d");
        queue2Stack.push("e");
        queue2Stack.push("f");
        queue2Stack.push("g");
        queue2Stack.push("h");
        
        while(queue2Stack.length()>0) {
            System.out.println(queue2Stack.pop());
        }