如何用栈来实现队列,如何用队列来实现栈,如何用数组来实现栈和队列。

如何用栈实现队列

思路:用栈实现队列结构,准备两个栈,一个push栈,一个pop栈,加数据入push栈,取数据从pop栈中拿。总体思路是进push的数据倒入pop栈中,两次逆序等于顺序。倒的两个限制:(1) 如果push开始往pop中倒数据,一次要倒完 (2) pop栈为空才允许倒数据。只要满足以上两个限制,倒数据的行为可以发生在任何时刻

public static class twoStacksToQueue {
    private Stack<Integer> pushStack;
    private Stack<Integer> popStack;

    private void transfer() {
        if (!popStack.empty())
            return;
        while (!pushStack.empty()) {
            popStack.push(pushStack.pop());
        }
    }

    public twoStacksToQueue() {
        pushStack = new Stack<>();
        popStack = new Stack<>();
    }

    public boolean offer(int num) {
        pushStack.push(num);
        transfer();
        return true;
    }

    public int poll() {
        if (popStack.empty() && pushStack.empty()) {
            throw new RuntimeException("Queue is empty");
        }
        transfer();
        return popStack.pop();
    }

    public int peek() {
        if (popStack.empty() && pushStack.empty()) {
            throw new RuntimeException("Queue is empty");
        }
        transfer();
        return popStack.peek();
    }
}

如何用队列实现栈

思路:准备两个队列,一个data队列,一个help队列,压数的话压入data队列,弹出数将data队列中的数除了最后一个数之外其他的压入help队列,将最后一个数返回用户,再将data和help引用互换

public static class TwoQueuesToStack {
    private Queue<Integer> data;
    private Queue<Integer> help;

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

    public int push(int num) {
        data.add(num);
        return num;
    }

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

    public int peek() {
        if (data.isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        while (data.size() > 1) {
            help.add(data.poll());
        }
        int res = data.poll();
        // 注意:最后一个数要加回help中
        help.add(res);
        swap();
        return res;
    }

    private void swap() {
        Queue<Integer> tmp = data;
        data = help;
        help = tmp;
    }
}

如何用数组实现栈

思路:准备一个栈顶指针index,数组的大小设置为栈的大小为initSize。当要加一个数,index的含义为如果新来一个数,我把新来的数放在index位置。当用户让我弹出一个数,我弹出的数是index的前一个数(前一个数也就是位置处于index下面一个数,假设数组是竖直排列的,最底下是nums[0])。index == size时前一个数下标为size - 1,栈满,如还要压入则给用户报错。index == 0时前一个数下标为-1。栈空,如还要弹出给用户报错。

public static class ArrayStack {
    private int[] array;
    private int index;
    public int size; // 栈的大小,也是数组的大小

    public ArrayStack(int initSize) {
        if (initSize < 0) {
            throw new IllegalArgumentException("The init size is less than 0");
        }
        this.size = initSize;
        array = new int[initSize];
        index = 0;
    }

    public int push(int num) {
        if (index < size) {
            array[index ++] = num;
            return num;
        } else {
            throw new ArrayIndexOutOfBoundsException("The stack is full!");
        }
    }

    public int pop() {
        if (index > 0) {
            return array[-- index];
        } else {
            throw new ArrayIndexOutOfBoundsException("The stack is empty!");
        }
    }

    public int peek() {
        if (index > 0) {
            return array[index - 1];
        } else {
            throw new ArrayIndexOutOfBoundsException("The stack is empty!");
        }
    }
}

如何用数组实现队列

思路:准备一个start变量一个end变量,一开始都指向0位置,再准备一个curSize变量约束startend的行为,curSize表示队列已有元素的个数。startend无直接关系(解耦),start或者end都是每次和curSize比较是否越界。end代表当要加一个数,我把新来的数放在end位置,start代表当用户让我取出一个数,我把start位置的数取出给用户,类似于加数队尾排队打饭,取数队头打完饭走人。end一旦到底就返回开头,start一直在追end,curSize == array.length时队列为满,如还要加数给用户报错,curSize == 0队列为空,如还要取数给用户报错。

public static class ArrayQueue {
    private int[] array;
    private int curSize;
    private int start, end;
    public ArrayQueue(int initSize) {
        if (initSize < 0) {
            throw new IllegalArgumentException("The init size is less than 0");
        }
        array = new int[initSize];
        curSize = 0;
        start = 0;
        end = 0;
    }

    public boolean add(int num) {
        if (curSize == array.length) {
            throw new ArrayIndexOutOfBoundsException("The Queue is full");
        }
        curSize ++;
        array[end] = num;
        // end的下一个位置
        end = end == array.length - 1 ? 0 : end + 1;
        return true;
    }

    public int poll() {
        if (curSize == 0) {
            throw new ArrayIndexOutOfBoundsException("The Queue is empty");
        }
        curSize --;
        int tmp = start;
        // start的下一个位置
        start = start == array.length - 1 ? 0 : start + 1;
        return array[tmp];
    }

    public int peek() {
        if (curSize == 0) {
            throw new ArrayIndexOutOfBoundsException("The Queue is empty");
        }
        return array[start];
    }
}

results matching ""

    No results matching ""