[剑之offer] 08 用两个栈实现队列

一、问题描述

1、用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead操作返回 -1 )

二、解决方法

1、一个栈用来存放入栈

2、一个栈用来存放出栈

3、具体操作

A: 构造方法 初始化 stackIn 和 stackOut 为空

B:插入元素

插入元素对应方法 appendTail stackIn 直接插入元素

C: 删除元素

删除元素对应方法 deleteHead

如果 stackOut 为空，则将 stackIn 里的所有元素弹出插入到 stackOut 里 如果 stackOut 仍为空，则返回 -1，否则从 stackOut 弹出一个元素并返回

三、代码

package com.haoxiansheng.demo01.SwordfingerOffer; import lombok.extern.slf4j.Slf4j; import java.util.Stack; /** * @author flame * @data 2020/10/21 */ @Slf4j public class CQueue { private Stack<Integer> stackIn; private Stack<Integer> stackOut; public CQueue() { stackIn = new Stack<>(); stackOut = new Stack<>(); } public static void main(String[] args) { CQueue queue = new CQueue(); queue.appendTail(8); queue.appendTail(9); queue.appendTail(10); log.info("pop=>{}", queue.deleteHead()); log.info("pop=>{}", queue.deleteHead()); log.info("pop=>{}", queue.deleteHead()); log.info("pop=>{}", queue.deleteHead()); } /** * 入队 * @param value */ public void appendTail(int value) { stackIn.push(value); } /** * 出队 * @return */ public int deleteHead() { if (!stackOut.isEmpty()) { return stackOut.pop(); } else { while (!stackIn.isEmpty()) { stackOut.push(stackIn.pop()); } } return stackOut.isEmpty() ? -1 : stackOut.pop(); } }