1.用栈结构实现队列结构

1.用栈结构实现队列结构

package cn.test;

import java.util.Stack;

/**
 * @Author smallmartial
 * @Date 2020/3/2
 * @Email [email protected]
 *
 * 示例：放入栈的顺序为：1,2,3,4,5 保证拿出顺序为：1,2,3,4,5；
 * 首先将数据放入 push 栈中，形成：5,4,3,2,1，然后将其全部拿出 push 到 pop 栈中，变成了 1,2,3,4，5；
 * 然后在 pop 栈中依次从栈顶取出所有元素即可；
 * **要求**：如果 push 栈中决定往 pop 栈中倒数据，则一次必须倒完；
 * 如果 pop 栈中仍有数据，则 push 栈不能往 pop 栈中倒数据；
 */
public class StackConvertToQueue {
    private Stack<Integer> stackPush;
    private Stack<Integer> stackPop;

    public StackConvertToQueue() {
        stackPush = new Stack<Integer>();
        stackPop = new Stack<Integer>();
    }

    public void push(Integer num){
        stackPush.push(num);
    }
    // 将 push 栈中数据全部倒入 pop 栈中，然后返回 Pop 栈顶元素
    public Integer poll(){
        if(stackPush.isEmpty() && stackPop.isEmpty()){
            throw new RuntimeException("Queue is empty");
        }else if(stackPop.isEmpty()){
            while (!stackPush.isEmpty()){
                stackPop.push(stackPush.pop());
            }
        }
        return stackPop.pop();
    }

    public Integer peek(){
        if(stackPush.isEmpty() && stackPop.isEmpty()){
            throw new RuntimeException("Queue is Empty");
        }else if(stackPop.isEmpty()){
            while (!stackPush.isEmpty()){
                stackPop.push(stackPush.pop());
            }
        }
        return stackPop.peek();
    }

    public static void main(String[] args) {
        StackConvertToQueue stackConvertToQueue = new StackConvertToQueue();
        stackConvertToQueue.push(1);
        stackConvertToQueue.push(2);
        stackConvertToQueue.push(3);
        System.out.println("======poll测试=========");
        System.out.println(stackConvertToQueue.poll());
        System.out.println(stackConvertToQueue.poll());
        System.out.println("=======peek测试=========");
        System.out.println(stackConvertToQueue.peek());
    }
}

2.用队列实现栈

package cn.test;

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

/**
 * @Author smallmartial
 * @Date 2020/3/2
 * @Email [email protected]
 *
 * 用队列实现栈
 */
public class QueueConvertToStack {
    private Queue<Integer> data;
    private Queue<Integer> help;

    public QueueConvertToStack() {
        data = new LinkedList<Integer>();
        help = new LinkedList<Integer>();
    }

    public void push(Integer num){
        data.add(num);
    }

    public Integer pop(){
        if(data.isEmpty()){
            throw new RuntimeException("stack is empty");
        }
        while (data.size() > 1){
            help.add(data.poll());
        }
        Integer res = data.poll();
        swap();
        return res;
    }

    public Integer peek(){
        if(data.isEmpty()){
            throw new RuntimeException("stack is empty");
        }
        while (data.size() != 1) {
            help.add(data.poll());
        }
        Integer res = data.poll();
        help.add(res);
        // 改变两个引用，就是 Help 栈变 data 栈， data 栈变 help 栈；
        swap();
        return res;
    }
    /**
     * 交换引用
     */
    private void swap() {
        Queue<Integer> temp = data;
        data = help;
        help = temp;
    }

    public static void main(String[] args) {
        QueueConvertToStack stack = new QueueConvertToStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("=====poll测试====");
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println("=====peek测试====");
        System.out.println(stack.peek());
        System.out.println(stack.peek());
    }
}