用两个栈实现队列

发表于
本文字数： 1k 阅读时长 ≈ 1 分钟

LeetCode每日一题，剑指offer 09.用两个栈实现队列

先看题目描述

算法和思路

在类中维护两个栈，一个栈用于负责插入元素功能，第二个栈用于负责删除功能。当要插入整数时，就直接往第一个栈中添加元素；当要删除整数时，若两个栈均为空，则直接返回 -1，否则的话就看第二个栈是否为空，为空的话就将第一个栈的元素一个个弹出并插入到第二个栈中，再将第二个栈的栈顶元素弹出并返回，不空的话就直接弹出第二个栈的栈顶元素并返回

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;

class CQueue {
    private Deque<Integer> addStack = new LinkedList<>();
    private Deque<Integer> deleteStack = new LinkedList<>();
    int size;

    public CQueue() {

    }

    public void appendTail(int value) {
        addStack.push(value);
        size++;
    }

    public int deleteHead() {
        if (size == 0) return -1;
        if (deleteStack.isEmpty()) {
            while (!addStack.isEmpty()) {
                deleteStack.push(addStack.pop());
            }
        }
        size--;
        return deleteStack.pop();
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */