两个栈实现队列以及两个队列实现栈

用户5513909

发布于 2023-04-25 11:29:56

2070

发布于 2023-04-25 11:29:56

两个队列实现栈 思路：队列queue是专职进出栈的，队列help只是个中转站，起辅助作用。入栈：直接入队列queue即可出栈：把queue的除最后一个元素外全部转移到队help中,然后把刚才剩下queue中的那个元素出队列。之后把q2中的全部元素转移回q1中(或者两个队列互换) 入栈：

出栈：

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

public class QueuesStack {
    private Queue<Integer> queue;
    private Queue<Integer> help;

    public QueuesStack() {
        queue = new LinkedList<Integer>();
        help = new LinkedList<Integer>();
    }

    private void push(int pushInt) {
        queue.add(pushInt);
    }

    public int peek() {
        if(queue.isEmpty()) {
            throw new RuntimeException("Stack is empty!");
        }
        while(queue.size() !=1 ) {
            help.add(queue.poll());
        }
        int res = queue.poll();
        help.add(res);
        swap();
        return res;
    }

    public void swap(){
        Queue<Integer> tmp;
        tmp = queue;
        queue = help;
        help = tmp;
    }

    public int pop() {
        if(queue.isEmpty()) {
            throw new RuntimeException("Stack is empty!");
        }
        while(queue.size() > 1 ) {
            help.add(queue.poll());
        }
        int res = queue.poll();
        swap();
        return res;
    }
}

*两个栈实现队列 思路：

使用两个栈stackPush,stackPop，其中假定stackPush负责push操作，stackPop负责pop操作。使用一个变量res来存储最后添加的元素。
实现队列的push操作。每次进行添加操作，都会直接对栈stackPush进行添加元素
实现队列的pop操作首先判断栈stackPush,stackPop是否都为空 a.如果都为空，抛出异常 b.如果stackPush不为空，则将stackPush中的数据pop到stackPop中去，然后pop出stackPush的元素,这个元素即为队列头部元素 c.如果stackPush为空，直接pop出stackPop中的数据

import java.util.Stack;

public class StacksQueue {
    private Stack<Integer> stackPop;
    private Stack<Integer> stackPush;

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

    public void push(int pushInt) {
        stackPush.push(pushInt);
    }

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

    public int poll() {
        if(stackPush.empty() && stackPop.empty()) {
            throw new RuntimeException("Queue is empty");
        } else if (stackPop.empty()) {
            while (!stackPush.empty()) {
                stackPop.push(stackPush.pop());
            }
        }
        return stackPop.pop();
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-09-29，如有侵权请联系 cloudcommunity@tencent.com 删除

integer