欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

队列实现栈和栈实现队列

程序员文章站 2022-07-10 23:34:15
...

1、如何仅用队列结构实现栈


import java.util.LinkedList;
import java.util.Queue;

//如何仅用队列结构实现栈
/*
①创建两个队列data和help;
②push操作,直接数字add进data队列;
③pop操作,将data中除了队列最后一个之外全部出队poll,
进到help队列中,然后将data中的最后一个元素出队;
然后交换help和data的引用,继续循环,可以将队列中的数一栈的
形式输出来。
④
 */
public class e3_StackQueue {
    private Queue<Integer> data;
    private Queue<Integer> help;
    public e3_StackQueue(){
        data=new LinkedList<Integer>();
        help=new LinkedList<Integer>();
    }
    public void push(Integer obj){
        data.add(obj);
    }
    public Integer pop(){
        if (data.isEmpty()){
            throw new ArrayIndexOutOfBoundsException("Queue is empty");
        }
        while (data.size()>1){
            help.add(data.poll());
        }
        Integer  tem = data.poll();
        swap();
        return  tem;
    }
    public Integer peek(){
        if (data.isEmpty()){
            throw new ArrayIndexOutOfBoundsException("Queue is empty");
        }
        while (data.size()>1){
            help.add(data.poll());
        }
        Integer  tem=data.peek();
        help.add(data.poll());
        swap();
        return  tem;

    }
    public void swap(){
        Queue<Integer> tem=data;
        data=help;
        help=tem;
    }

    public static void main(String[] args) {
        e3_StackQueue s=new e3_StackQueue();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        s.push(5);
        System.out.println(s.data);
        System.out.println("栈的peek操作:");
        System.out.println(s.peek());
        System.out.println("栈的pop操作,pop两次");
        System.out.println(s.pop());
        System.out.println(s.pop());
    }
}

2、如何仅用栈结构实现队列

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/*
①创建两个栈pushStack和popStack;
②进队操作,正常使用pushStack.push()的方法;
③出队操作,让pushStack栈的每个元素都弹出来,并依次压到popStack中。
(就像倒水一样,从pushStack到popStack)
出队操作就可以通过栈popStack.pop实现了
 */
public class e4_StackQueue {
    private Stack<Integer> pushStack;
    private Stack<Integer> popStack;
    public e4_StackQueue(){
        pushStack=new Stack<Integer>();
        popStack=new Stack<Integer>();
    }
    public void push(Integer obj){
        pushStack.push(obj);

    }
    public Integer pop(){
        if (popStack.isEmpty()&&pushStack.isEmpty()){
            throw new ArrayIndexOutOfBoundsException("Queue is empty1");
        }
        pouraway();
        return  popStack.pop();
    }
    public Integer peek(){
        if (!popStack.isEmpty()){
            throw new ArrayIndexOutOfBoundsException("Queue is empty2");
        }
        pouraway();
        return  popStack.peek();

    }
    public void pouraway(){
        //PopStack必须为空才能倒数据
        if (!popStack.isEmpty()){
            return;
        }//倒数据要一次倒完
        while (!pushStack.isEmpty()){
            popStack.push(pushStack.pop());
        }
    }

    public static void main(String[] args) {
        e4_StackQueue q=new e4_StackQueue();
        q.push(1);
        q.push(2);
        q.push(3);
        q.push(4);
        q.push(5);
        System.out.println(q.pushStack);
        System.out.println("队列的peek操作:");
        System.out.println(q.peek());
        System.out.println("队列的poll操作,poll两次");
        System.out.println(q.pop());
        System.out.println(q.pop());

    }
}