很有想法的一个问题---用栈实现队列和用队列实现栈

蔚落 2021-11-11 20:04 266阅读 0赞

1.栈实现队列：

思路是有两个栈，一个用来放数据（数据栈），一个用来辅助（辅助栈）。数据添加时，会依次压人栈，取数据时肯定会取栈顶元素，但我们想模拟队列的先进先出，所以就得取栈底元素，那么辅助栈就派上用场了，把数据栈的元素依次弹出到辅助栈，但保留最后一个元素，最后数据栈就剩下了最后一个元素，直接把元素返回，这时数据栈已经没有了数据。最后呢，把辅助栈的元素依次压人数据栈，这样，我们成功取到了栈底元素。

代码如下：

package com.sxt.test.java;  
   
public class Stack2Queue \{  
    /\*\*  
     \* 用栈的入栈和出栈  
     \* 来实现队列的入队和出队  
     \*  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的数据放入stack2，留下最后一个数据  
            while(stack1.length()>1) \{  
                stack2.push(stack1.pop());  
            \}  
            if(stack1.length()==1) \{  
                //把stack1的留下的那个数据返回出去  
                o = stack1.pop();  
            \}  
        \}else \{  
            o = stack2.pop();  
        \}  
          
        return o;  
    \}  
    public int length() \{  
        return stack1.length()+stack2.length();  
    \}  
   
\}

2.队列实现栈  
思路同上：有数据队列和辅助队列，模拟栈的先进后出，队列是队尾进队头出，也就是说每次取值要取队列的队尾元素，数据队列出队到辅助队列，留下最后一个元素返回，辅助队列再把元素出队到数据队列

代码如下：

package com.sxt.test.java;  
   
public class Queue2Stack \{  
    /\*\*  
     \* 用队列的入队和出队  
     \* 来实现栈的入栈和出栈  
     \* \*/  
      
    Queue queue1 = new Queue();//主要存放数据  
    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();  
    \}  
      
   
\}