栈的实际应用以及队列的初理解

栈的实际应用以及队列的初理解

对于前面栈的学习，我便萌发了自己创建一个栈的想法。那么，想要自己实现一个栈，要从何入手呢？

根据栈的源码我们可以得知，栈的底层实际上是一个数组，所以我们可以利用数组的思想来自己创建一个栈。

下面便是自己创建的栈

import java.util.Arrays;
public class MyStack {
    public int[] elem;
    public int usedSide;//记录有效数据

    public MyStack(){
        this.elem = new int[5];//对数组初始化，如果不够可以扩容
    }

    public void push(int val){
        //这里要考虑栈是否满
        if(isFull()){
            //扩容
           this.elem =  Arrays.copyOf(this.elem, 2*this.elem.length);
        }
        this.elem[this.usedSide] = val;
        usedSide++;
    }

    public boolean isFull(){
        return this.usedSide == this.elem.length;
    }

    public int pop(){
        //这里要考虑栈是否为空
        if(isEmpty()){
            throw new RuntimeException("栈为空");
        }
        int oldVal = this.elem[this.usedSide-1];
        this.usedSide--;
        return oldVal;
    }
    public boolean isEmpty(){
        return this.usedSide == 0;
    }
    public int peek(){
        if(isEmpty()){
            throw new RuntimeException("栈为空");
        }
        return this.elem[this.usedSide-1];
    }

}

代码解读： 

1.push

对于数据的push，我们 可以根据usedSize（记录有效数据）来放入，这时候要考虑一个问题，对于放入的数据如果栈满了怎么办？非常好办，我们已经知道栈的底层是一个数组，我们只需要将数组扩容便可以达到预想的结果，根据源码也可知是二倍扩容，通过

 Arrays.copyOf 二倍扩容

2.pop 

这里的pop我们须要注意两个问题：1.存储的数据是引用类型 2.栈为空时

1.当存储的数据为引用类型时，只需将栈顶元素置为null就可以了，再将usedSize--就能够得到我们想要的pop；而当数据为整数类型是，不需要将栈顶元素置为null，直接将usedSize--就可以得到我们想要的。

2.当usedSize==0时候栈就为空

3.peek

peek的情况和pop比较类似，只是省略了数据的“删除”，详情可以根据代码的对比

MyStack的测试 

 

可以看出MyStack也是成功的跑起来了

---

对于栈的面试题也是非常重要，这道OJ 对于面试来说也是常考的题型

题目：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

 代码如下

class Solution {
    public boolean isValid(String s) {
        Stack stack = new Stack<>();//创建栈
        for(int i = 0;i < s.length();i++){
            char ch = s.charAt(i);
            if(ch == '(' || ch == '{' || ch == '['){
                stack.push(ch);
            }else{
                //遇到右括号
                if(stack.empty()){
                    //说明右括号多
                    System.out.println("右括号多");
                    return false;
                }
                char top = stack.peek();//获取栈顶元素后与右括号进行匹配
                if(top == '(' && ch == ')' || top == '{' && ch == '}' || top == '[' && ch == ']' ){
                    stack.pop();
                }else{
                    //左右括号不匹配
                    System.out.println("左右括号不匹配");
                    return false;
                }
            }
        }
        if(!stack.empty()){
            //说明左括号多
            System.out.println("左括号多");
            return false;
        }
        return true;
    }
}

对于这道题，我们可以从括号不匹配来分析切入，可以得出一共有三种情况

1.左括号多

（（（））

当左括号出栈与右括号进行匹配时，如果当i遍历完之后，栈并不为空，此时就说明左括号多 

 

2.右括号多

（（）））

当i没有遍历完，但是栈为空了，就说明右括号多。

对于左右括号多这个点也是比较难想出来，这便是积累题的好处 

3.左右括号不匹配

（ [ ) ] 

第三种情况就是当i遍历完之后，栈不为空，并且也没有右括号与左括号相匹配，这便是左右括号不匹配问题

---

最小栈OJ1 

题目：

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

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

class MinStack {
    private Stack stack;
    private Stack minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(!minStack.empty()){
            int top = minStack.peek();
            if(val <= top){
                minStack.push(val);//
            }
        }else{
            minStack.push(val);
        }
    }
    public void pop() {
        int popVal = stack.pop();
        if(!minStack.empty()){
            int top = minStack.peek();
            if(top == popVal){
                minStack.pop();
            }
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

 代码分析见下一章！！！

未完待续。。。