java：用栈实现队列+用队列实现栈

Love The Way You Lie 2022-08-04 05:26 351阅读 0赞

package com.stackqueue;
    
    import java.util.Stack;
    
    /*
     * 用两个栈模拟一个队列
     * A为插入栈--模拟入队列，B为弹出栈--模拟出队列
     * (1)入队列，即入栈A
     * (2)出队列，B栈为空，则A栈元素全部出栈并入栈B，再从B出栈
     *            B栈不为空，从B出栈
     * */
    
    //自定义队列
    class StackToQueue
    {
    	private Stack A = new Stack();
    	private Stack B = new Stack();
    	
    	//元素入队列--压入A栈
    	public void push(int val)
    	{
    		A.push(val);
    	}
    	
    	//元素出队列--从B栈弹出
    	public int pop()
    	{
    		//如果弹出栈B为空，则把A栈中的元素全部压入B栈
    		if(B.empty())
    		{
    			while(!A.empty())
    			{
    				B.push(A.pop());
    			}
    		}
    		
    		//B栈中元素出栈
    		return (Integer)B.pop();
    	}
    	
    	//判断队列是否为空
    	public boolean isEmpty()
    	{
    		if(A.empty() && B.empty())
    			return true;
    		else
    			return false;
    	}
    	
    }
    
    public class TestStackToQueue 
    {
    	public static void main(String[] args)
    	{
    		StackToQueue Q = new StackToQueue();
    		
    		//元素入队列
    		System.out.print("元素入队列：");
    		for(int i = 0; i < 3; i++)
    		{
    			Q.push(i);
    			System.out.print(i +" ");
    		}
    		System.out.println();
    	
    		//元素出队列
    		System.out.print("元素出队列：");
    		for(int i = 0; i < 1; i++)
    		{
    			int val = Q.pop();
    			System.out.print(val +" ");
    		}
    		System.out.println();
    		
    		//元素入队列
    		System.out.print("元素入队列：");
    		for(int i = 4; i < 6; i++)
    		{
    			Q.push(i);
    			System.out.print(i +" ");
    		}
    		System.out.println();
    		
    		//元素出队列
    		System.out.print("元素出队列：");
    		for(int i = 0; i < 3; i++)
    		{
    			int val = Q.pop();
    			System.out.print(val +" ");
    		}
    		System.out.println();
    	}
    }

![Image 1][]

package com.stackqueue;
    
    import java.util.LinkedList;
    
    /*两个队列模拟栈的操作
     * 队列Q1--入队列，模拟入栈、出栈
     * 队列Q2--出队列，作为存贮中间数据的队列
     * 入栈：入队列Q1
     * 出栈：如果队列Q1只有一个元素，则出队列Q1
     *      如果队列Q1有（1+k，k>0）个元素，
     *         Q1中的k个元素出队列再入队列Q2,把Q1中的一个元素出队列，再把Q2中的元素出队列、入队列Q1中
     * */
    
    class QueueToStack
    {
    	LinkedList Q1 = new LinkedList();
    	LinkedList Q2 = new LinkedList();
    	
    	//元素入栈--入队列Q1
    	public void push(int val)
    	{
    		Q1.add(val);  //在列表的尾部添加元素
    	}
    	
    	//元素出栈--出队列Q1
    	public void pop()
    	{	
    		int val, tmp;
    		
    		int len1 = Q1.size();  //队列Q1的长度
    		
    		//如果队列Q1只有一个元素，直接出队列
    		if(len1 == 1)
    			val = (Integer)Q1.removeFirst();
    		
    		//如果队列Q1中有多于一个元素，
    		else
    		{
    			//把Q1中的多于一个的所有元素入队列Q2  *****注意：应该用变量len,而不是Q1.size()
    			for(int i = 0; i < len1 - 1; i++)
    			{ 
    				tmp = (Integer)Q1.removeFirst();
    				Q2.add(tmp);
    			}
    
    			//把Q1中唯一元素出队列
    			val = (Integer)Q1.removeFirst();
    			
    			//在把Q2中的所有元素入队列Q1
    			int len2 = Q2.size();
    			for(int i = 0; i < len2; i++)
    			{
    				tmp = (Integer)Q2.removeFirst();
    				Q1.add(tmp);
    			}
    		}
    		
    		System.out.print(val +" ");
    	}
    	
    }
    
    
    public class TestQueueToStack 
    {
    	public static void main(String[] args)
    	{
    		QueueToStack s = new QueueToStack();
    		
    		//元素入栈
    		System.out.print("元素入栈：");
    		for(int i = 0; i < 3; i++)
    		{
    			s.push(i);
    			System.out.print(i +" ");
    		}
    		System.out.println();
    	
    		//元素出栈
    		System.out.print("元素出栈：");
    		for(int i = 0; i < 1; i++)
    		{
    			s.pop();
    		}
    		System.out.println();
    		
    		//元素入栈
    		System.out.print("元素入栈：");
    		for(int i = 4; i < 6; i++)
    		{
    			s.push(i);
    			System.out.print(i +" ");
    		}
    		System.out.println();
    		
    		//元素出栈
    		System.out.print("元素出栈：");
    		for(int i = 0; i < 3; i++)
    		{
    			s.pop();
    		}
    		System.out.println();
    	}
    
    }

![Image 1][]  
![Image 1][]

[Image 1]: