使用两个栈实现一个队列

时间:2022-02-06 17:39:22

  使用两个栈Stack1和Stack2来实现一个队列。其中一个栈作为主存放数据的,另外一个栈作为临时存放数据的栈。具体操作如下:

enqueue: 栈Stack1的入栈操作。

dequeue:将Stack1中的元素一个一个地全部依次出栈,并且在Stack1出栈的同时把出栈的元素作为参数对Stack2进行入栈操作。这步完成之后,执行Stack2出栈操作,这时就将原先在Stack1中最先入栈的元素弹出。最后再将Stack2中的元素一个一个地全部依次出栈,填到Stack1中。

实现代码如下:

/**
 * 用两个栈实现一个队列
 * @author LBX
 *
 */
public class Exam10_1_6 {

    private Stack stack1;
    private Stack stack2;
    
    public Exam10_1_6() {
    }
    
    public Exam10_1_6(int n) {
        stack1 = new Stack(n);
        stack2 = new Stack(n);
    }
    
    public boolean enqueue(Object obj) {

        return stack1.push(obj);

    }
    
    public Object dequeue() {
        Object obj;
        Object result;
        while((obj=stack1.pop()) != null ){
            stack2.push(obj);
        }
        result = stack2.pop();
        while((obj=stack2.pop()) != null ){
            stack1.push(obj);
        }
        return result;
        

    }
    
    public static void main(String[] args) {
        Exam10_1_6 exam = new Exam10_1_6(10);
        for (int i = 0; i < 10; i++) {
            if(exam.enqueue(i)){
                System.out.println(i);
            }
        }
        System.out.println();
        for(int i=0;i<10;i++){
            System.out.println(exam.dequeue());
        }
    }
}

 改进后代码:

import java.util.Stack;

public class QueueByTwoStack {

    /*
     * 两个栈实现一个队列
     * enqueue完成入队操作,dequeue完成出队操作
     */
    private Stack<String> stack1 = new Stack<String>();
    private Stack<String> stack2 = new Stack<String>();
    
    public void enqueue(String obj) {
        stack1.push(obj);
    }
    
    public String dequeue() throws Exception {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty())
                stack2.push(stack1.pop());
        }
        if(stack2.isEmpty()){
            throw new Exception("no element");
        }
        return stack2.pop();
    }
    
    public static void main(String[] args) throws Exception {
        QueueByTwoStack queue = new QueueByTwoStack();
        for(int i=0;i<10;i++){
            queue.enqueue(i+"");
        }
        for(int i=0;i<20;i++){
            queue.enqueue(i+"");
            System.out.println(queue.dequeue());
        }
    }
    
}