MENU

栈和队列的相关问题

August 7, 2018 • Read: 163 • 算法

用数组实现栈

实现栈太简单了,直接上代码

代码
public class Stack {
    private Integer[] arr;
    private Integer idx;
    public Stack(int size) {
        if(size < 0) 
            throw new StackOverflowError("please input again and input numer must more than 0");
        arr = new Integer[size];
        idx = 0;
    }
    public Integer peek() {
        if(idx == 0)
            return null;
        return arr[idx - 1];
    }
    public void push(int obj) {
        if(idx == arr.length)
            throw new StackOverflowError("The Stack is full");
        arr[idx++] = obj;
    }
    public Integer pop() {
        if(idx == 0)
            throw new StackOverflowError("The Stack is null");
        return arr[--idx];
    }
    public static void main(String[] args) {
        Stack stack = new Stack(5);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }
}

用数组实现队列

题解

队列可能稍微有点复杂,定义队列的时候需要定义三个变量,分别是end,start,size,先说说他们分别的作用,每次用户拿队中的元素,都从start下标位置取,每次进队都从s=end位置进,每次出队或者进队size都要++或--

假设数组长度是3,如果size没有到3,进队时就把元素放到end的位置上,这是end和size之间的约束关系;如果size不等于0,出队时就总出start位置,这是start和size之间的约束关系。end本身还有一个约束关系,end是控制进队的,所以每次进一个元素end就++,如果end==数组长度,那么end就回到开头也就是0位置

代码
public class Queue {
    private int start = 0,end = 0,size = 0;
    private int[] arr;
    Queue(int size) {
        arr = new int[size];
    }
    public void push(int obj){
        if(size == arr.length) 
            throw new ArrayIndexOutOfBoundsException("The Queue is full");
        size++;
        arr[end] = obj;
        end = end == arr.length - 1 ? 0 : end + 1;
    }
    public int pop(){
        if(size == 0) 
            throw new ArrayIndexOutOfBoundsException("The Queue is full");
        size--;
        int tmp = start;
        start = start == arr.length - 1 ? 0 : start + 1;
        return arr[tmp];
    }
    public Integer peek() {
        if(size == 0)
            return null;
        return arr[start];
    }
    public static void main(String[] args) {
        Queue queue = new Queue(3);
        queue.push(3);
        queue.push(2);
        queue.push(1);
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
    }
}

题目链接:LeetCode155

题解

如何在常数时间内检索到最小元素这是关键,可以开辟一个新的min栈,当min为空或者push的值比min的栈顶元素小时,就将该值push到min中去,否则就再次min栈的栈顶元素

代码
class MinStack {
    int[] data = new int[10000];
    int[] min = new int[10000];
    int idx_data,idx_min;  
    public MinStack() { 
        idx_data = 0;
        idx_min = 0;
    }
    
    public void push(int x) {
        data[idx_data++] = x;
        if(idx_min == 0 || x < min[idx_min - 1])
            min[idx_min++] = x;
        else 
            min[idx_min++] = min[idx_min - 2];
    }
    
    public void pop() {
        idx_min--;
        idx_data--;
    }
    
    public int top() {
        return data[idx_data - 1];
    }
    
    public int getMin() {
        return min[idx_min - 1];
    }
}

题目链接:LeeCode225

题解

这个题不要觉得很简单就不想写,很多地方有可能会用到,比方说图的深度优先遍历,别人不让你用栈去实现深度优先遍历,怎么办,其实就和这个道题的思路一样,用两个队列合成一个栈,然后再去遍历

那么说一下这道题的思路。假设现在有元素12345入队,要按照栈的方式弹出,应该怎么做,很简单,再设一个辅助队列help,将1234全部弹出到help中,然后弹出5返回给用户即可

代码
class MyStack {
    Queue<Integer> myQueue;
    public MyStack() {
        myQueue = new LinkedList();
    }
    /** Push element x onto stack. */
    public void push(int x) {
        int n= myQueue.size();
        Queue<Integer> tempQueue= new LinkedList(); 
        for(int i= 0; i<n; i++){
            tempQueue.add(myQueue.poll());
        }
        myQueue.add(x);
        for(int i= 0; i<n; i++){
            myQueue.add(tempQueue.poll());
        }
    }
    
    /** Removes and returns the element on top of the stack. */
    public int pop() {
        return (int)myQueue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return (int)myQueue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return myQueue.isEmpty();
    }
}

题目链接:LeetCode232

题解

用两个栈实现一个队列更简单,假设先在有两个栈data和help,12345首先进data栈,然后将data栈中的元素全部倒到help栈里,然后依次从help栈弹出即可,所以进元素全从data栈进,出元素全从help栈出,但是这两个栈交互的时候有两个条件:

  1. data栈每次倒元素必须倒完
  2. 如果help栈里有东西,绝对不能将data栈的元素倒入help栈
代码
class MyQueue {

    private Stack<Integer> data = new Stack<Integer>();
    private Stack<Integer> help = new Stack<Integer>();
    public MyQueue() {
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        data.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(help.isEmpty())
            data_to_help();
        return help.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if(help.isEmpty())
            data_to_help();
        return help.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return data.isEmpty() && help.isEmpty();
    }
    public void data_to_help() {
        while(!data.isEmpty()) {
            help.push(data.pop());
        }
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */
最后编辑于: November 22, 2018
Archives Tip
QR Code for this page
Tipping QR Code