leetcode栈和队列

数组实现栈

//使用index来代表栈顶位置，index=0，栈为空，index = size，栈满
public class ArrStack {
    private int[] arr;
    private int index;
    public ArrStack(int size){
        arr = new int[size];
    }
    public void push(int x){
        if(index==arr.length){
            throw new ArrayIndexOutOfBoundsException("full");
        }
        arr[index++] = x;
    }

    public int  pop(){
        if(index==0){
            throw new ArrayIndexOutOfBoundsException("empty");
        }
        return arr[--index];
    }
    public int  peek(){
        if(index==0){
            throw new ArrayIndexOutOfBoundsException("empty");
        }
        return arr[index-1];
    }
    public boolean isEmpty(){
        return index==0;
    }
}

622.循环队列

public class MyCircularQueue {
    /**
     * 记录队头的front，记录队尾的wear，size表示队列大小
     * front指向第一个元素 rear指向最后一个元素后一个位置
     * 入队：arr[rear]=value，rear后移，size++，注意，因为要完成一个循环队列rear+1需要取模运算
     * 出队：font后移取模运算，size--
     * */
    private int front = 0;
    private int rear = 0;
    private int size = 0;
    private int[] arr;
    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        arr = new int[size];
    }

    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if(size==arr.length){
            return false;
        }
        arr[rear] = value;
        rear = (rear +1)%arr.length;
        size++;
        return true;
    }

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if(size==0){
            return false;
        }
        front = (front++)%arr.length;
        size--;
        return true;
    }

    /** Get the front item from the queue. */
    public int Front() {
        if(size==0){
            throw new RuntimeException("empty");
        }
        return arr[front];
    }

    /** Get the last item from the queue. */
    public int Rear() {
        if(size==0){
            throw new RuntimeException("empty");
        }
        return arr[(rear-1)%arr.length];
    }

    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        return size==0;
    }

    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        return size==arr.length;
    }
}

155.最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) – 将元素 x 推入栈中。
pop() – 删除栈顶的元素。
top() – 获取栈顶元素。
getMin() – 检索栈中的最小元素。

Stack<Integer> data = new Stack<>();
Stack<Integer> min = new Stack<>();
public MinStack() {

}

/**入栈的时候除了data栈之外，还包括min栈，存储的每一个元素其相应的最小值
     *
     */

public void push(int x) {
    data.push(x);
    if(min.isEmpty()){
        min.push(x);
    }else{
        int minVal = min.peek();
        if(x<minVal){
            min.push(x);
        }else{
            min.push(minVal);
        }
    }

}

public void pop() {
    if(!data.isEmpty()) {
        data.pop();
        min.pop();
    }else{
        throw new ArrayIndexOutOfBoundsException("empty");
    }
}

public int top() {
    int res = 0;
    if(!data.isEmpty()) {
        res = data.peek();
    }else{
        throw new ArrayIndexOutOfBoundsException("empty");
    }
    return res;
}

public int getMin() {
    int res = 0;
    if(!min.isEmpty()) {
        res = min.peek();
    }else{
        throw new ArrayIndexOutOfBoundsException("empty");
    }
    return res;
}

255.用队列实现栈

队列是先进先出的，我们准备两个队列data，helper，data存放入队的数据，pop的时候将前n-1个元素从data出队到helper中，这样data中就只剩下一个最先进队的元素，即可以达到先进后出的目的。

private Queue<Integer> data = new LinkedList<>();
private Queue<Integer> helper = new LinkedList<>();
private int top;
public MyStack() {

}

/** 放入到data队列中 */
public void push(int x) {
    data.add(x);
}

/** pop元素的时候，将前n-1个元素放入helper中，只留下最后一个元素，这样，就可以达到栈的目的
     * */
public int pop() {
    while(data.size()>1){
        helper.add(data.remove());
    }
    int res = data.remove();
    swap();
    return res;
}
public void swap(){
    Queue<Integer> tmp = this.data;
    this.data = this.helper;
    this.helper = tmp;
}
/** Get the top element. */
public int top() {
    while(data.size()>1){
        helper.add(data.poll());
    }
    int res = data.poll();
    helper.add(res);
    swap();
    return res;
}

/** Returns whether the stack is empty. */
public boolean empty() {
    return data.size()==0;
}

232.用栈实现队列

因为栈是先进后出，因此元素先进去一个栈push，在从该栈push出栈到另一个栈pop，这样，我们从pop中取出元素就可以达到先进先出的目的。

需要注意的是，元素从push到pop，需要满足两个条件：需要一次性将push栈元素出栈完；当pop中有元素时，不可以入栈。

Stack<Integer> sta_pop = new Stack<>();
/** Initialize your data structure here. */
public MyQueue() {

}

/** Push element x to the back of queue. */
public void push(int x) {
    pushtoPop();
    sta_push.push(x);
}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
    pushtoPop();
    return sta_pop.pop();
}

/** Get the front element. */
public int peek() {
    pushtoPop();
    return sta_pop.peek();
}
//将元素从push推到pop
//1.一次性推完push中元素 2.pop中为空
public void pushtoPop(){
    if(sta_pop.isEmpty()) {
        while (!sta_push.isEmpty()) {
            sta_pop.push(sta_push.pop());
        }
    }
}

/** Returns whether the queue is empty. */
public boolean empty() {
    return sta_pop.isEmpty()&&sta_push.isEmpty();
}