栈/队列互相模拟实现

谁借莪１个温暖的怀抱￠ 2022-05-12 11:06 139阅读 0赞

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

思路：大概这么想：用一个辅助栈把进第一个栈的元素倒一下就好了。

比如进栈1，2，3，4，5

第一个栈：

然后倒到第二个栈里

再倒出来，顺序为1，2，3，4，5

实现队列

然后要注意的事情：

1）栈2非空不能往里面倒数，顺序就错了。栈2没数再从栈1倒。

2）栈1要倒就一次倒完，不倒完的话，进新数也会循序不对。

import java.util.Stack;
     
    public class Solution {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
         
        public void push(int node) {
            stack1.push(node);
        }
         
        public int pop() {
            if(stack1.empty()&&stack2.empty()){
                throw new RuntimeException("Queue is empty!");
            }
            if(stack2.empty()){
                while(!stack1.empty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }

用两个队列实现栈，要求同上：

这其实意义不是很大，有些数据结构书上甚至说两个队列不能实现栈。

其实是可以的，只是时间复杂度较高，一个弹出操作时间为O(N)。

思路：两个队列，编号为1和2.

进栈操作：进1号队列

出栈操作：把1号队列全弄到2号队列里，剩最后一个别压入，而是返回。

最后还得把1和2号换一下，因为现在是2号有数，1号空。

仅仅有思考价值，不实用。

比如压入1，2，3

队列1：1，2，3

队列2：空

依次弹出1，2，3：

队列1里的23进入2号，3弹出

队列1：空

队列2：2，3

队列2中3压入1号，2弹出

队列1：3

队列2：空

队列1中只有一个元素，弹出。

上代码：

public class TwoQueueImplStack {
    	Queue<Integer> queue1 = new ArrayDeque<Integer>();
    	Queue<Integer> queue2 = new ArrayDeque<Integer>();
    //压入
    	public void push(Integer element){
    		//都为空，优先1
    		if(queue1.isEmpty() && queue2.isEmpty()){
    			queue1.add(element);
    			return;
    		}
    		//1为空，2有数据，放入2
    		if(queue1.isEmpty()){
    			queue2.add(element);
    			return;
    		}
    		//2为空，1有数据，放入1
    		if(queue2.isEmpty()){
    			queue1.add(element);
    			return;
    		}
    	}
    //弹出
    	public Integer pop(){
    		//两个都空，异常
    		if(queue1.isEmpty() && queue2.isEmpty()){
    			try{
    				throw new Exception("satck is empty!");
    			}catch(Exception e){
    				e.printStackTrace();
    			}
    		}	
    		//1空，2有数据，将2中的数据依次放入1，最后一个元素弹出
    		if(queue1.isEmpty()){
    			while(queue2.size() > 1){
    				queue1.add(queue2.poll());
    			}
    			return queue2.poll();
    		}
    		
    		//2空，1有数据，将1中的数据依次放入2，最后一个元素弹出
    		if(queue2.isEmpty()){
    			while(queue1.size() > 1){
    				queue2.add(queue1.poll());
    			}
    			return queue1.poll();
    		}
    		
    		return (Integer)null;
    	}
    //测试
    	public static void main(String[] args) {
    		TwoQueueImplStack qs = new TwoQueueImplStack();
    		qs.push(2);
    		qs.push(4);
    		qs.push(7);
    		qs.push(5);
    		System.out.println(qs.pop());
    		System.out.println(qs.pop());
    		
    		qs.push(1);
    		System.out.println(qs.pop());
    	}
    }