专栏简介 :java语法及数据结构

题目来源:leetcode,牛客,剑指offer

创作目标:从java语法角度实现底层相关数据结构,达到手撕各类题目的水平.

希望在提升自己的同时,帮助他人,与大家一起共同进步,互相成长.

学历代表过去,能力代表现在,学习能力代表未来!

目录

前言

一.栈的定义与实现

1)栈的定义:

 2)栈常见操作方法:

 3)栈的实现:

二.栈相关题目

1)逆波兰数

2)不可能的入栈方式

3)有效括号

4)最小栈

三.队列的实现

1)单链表实现队列

2)循环队列

四.队列相关题目

1)用栈实现队列 

2)用队列实现栈

总结

---

前言

        Hello!大家好!我是Node_Hao,今天给大家带来的是栈和队列的底层实现及其构造方法,旨在熟练掌握栈和队列的使用以后,可以手撕各类栈相关的题目.希望我的文章能对你有所帮助与启发!

一.栈的定义与实现

1)栈的定义:

      栈是一种数据结构特点是"先进后出",基于这一特点栈不管是push()(压入元素)还是pop()(弹出栈顶元素),时间复杂度都是O(1).而java虚拟机栈只是JVM中的一块内存,用来存放局部变量..... 调用函数时我们会在java虚拟机栈中开辟一块内存叫栈帧.

 2)栈常见操作方法:

1.stack.empty().判断栈是否为空,为空就返回false,否则返回true.

2.stack.push().将元素压入栈底.

3.stack.pop().将栈顶元素弹出栈.

4.satck.peek().peek有窥视的意思,顾名思义作用就是查看栈顶元素,但不弹出.

 3)栈的实现:

        栈的底层实现既可以用顺序表也可以使用双向链表,二者实现方式大同小异,而我们使用的是顺序表.基本配置只需要一个数组来存放元素和一个usedSize记录顺序表元素的个数.构造方法初始化时我们可以将栈的大小初始化为5,后续不够再扩容.扩容使用Arrays.copyof()方法.

class My_stack{
    int[] elem;
    int usedSize;

    public My_stack(int[] elem, int usedSize) {
        this.elem = new int[5];
        this.usedSize = usedSize;
    }
    public void push(int val){
        if (usedSize==elem.length){//如果满了就扩容
            Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize] = val;
        usedSize++;
    }
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("栈为空");
        }
        return elem[usedSize--];
    }
    public int peek(){
        if (isEmpty()){
            throw new RuntimeException("栈为空");
        }
        return elem[usedSize-1];
    }
    public boolean isEmpty(){
        return usedSize==0;
    }
}

二.栈相关题目

1)逆波兰数

        逆波兰数也叫后缀表达式,早年计算机并没有用括号来规定四则运算的计算顺序,那么如果计算9+(3-1)x3+10/2总不能直接输9+3-1x3+10/2吧,于是睿智的科学家通过栈解决了这个难题,栈中存放的只能是数字,所以只要遇到数字就压栈,遇到运算符号就从栈顶弹出两个数字,最顶部的在操作符右边,下一个在操作符左边,运算完后将结果压栈,继续重复上述操作.

        在此题的基础上我们拓展中缀表达式转后缀表达式,首先按四则运算的优先级给表达式加上相应的括号((9+((3-1)x3))+(10/2))然后将每个括号中对应的操作符移到该括号之外:

(((9((31)-3)x)+)10 2)/)+去掉括号后得:931-3x+102/+.

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> str = new Stack<>();
        for(int i = 0;i<tokens.length;i++){
            String s = tokens[i];
            if(!isoperation(s)){
                str.push(Integer.parseInt(s));//将数字压栈
            }else{
                int num2 = str.pop();
                int num1 = str.pop();
                switch(s){
                    case "+":
                        str.push(num1+num2);
                        break;
                     case "-":
                        str.push(num1-num2);
                        break;
                     case "*":
                        str.push(num1*num2);
                        break;
                    case "/":
                        str.push(num1/num2);
                        break;
                }
            }
        }
        return str.pop();
    }
    public boolean isoperation(String s){
        if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
            return true;
        }
        return false;
    }
}

2)不可能的入栈方式

         根据栈"先进后出"的原理我们可以将pushed数组,每压入一个元素就与popped数组的栈顶元素相比较,如果相同就弹出压入数组的元素,然后访问popped数组的下一个元素继续比较.如果不相同,pushed数组继续压栈,重复上述操作.当pushed数组全部压入后,如果此时栈为空,那么符合出栈方式,如果不为空则不符合.

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<Integer>();
         int j = 0;
        for(int i = 0;i<pushed.length;i++){
            stack.push(pushed[i]);
            while(!stack.empty()&&i<pushed.length&&stack.peek()==popped[j]){
                stack.pop();
                j++;
            }
        }
        if(!stack.empty()){
            return false;
        }
        return true;
    }
}

3)有效括号

         通过了解题目大致有四种情况,1.左边括号多( ( ( ) 2.右边括号多( ( ) ) ) ) 3.左右括号不匹配{ ) [ } 4.左右括号匹配( ) { } .那么根据栈的特点,我们可以遇到左边的括号就压入栈中,遇到右边的括号便和栈顶的元素比较是否匹配,如果不匹配返回false.但要注意两点:1. 如果我们在比较的过程中发现栈为空,那么就是右边括号多,返回fasle.2.如果我们比较完毕,栈不为空,说明左边括号多,返回false.如果没有以上情形我们就可以返回true.

class Solution {
    public boolean isValid(String s) {
        Stack<Character> 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()){//右边括号多
                    return false;
                }
                char top = stack.peek();
                if((top=='('&&ch==')')||(top=='['&&ch==']')||(top=='{'&&ch=='}')){
                    stack.pop();
                }else{
                    return false;//左右括号不匹配
                }
            }
        }
        if(!stack.empty()){//左面括号多
            return false;
        }
    return true;
    }
}

4)最小栈

        要想实现在常数时间内检索到最小元素的栈,那么一定不可能一个栈,因为根据栈的特点检索元素的时间复杂度必然是O(N),所以如果我们可以把栈的最小元素单独保存起来,那么当我们需要时查找最小元素时间复杂度必然是O(1).按照上述思路,首先我们创建两个栈,第一个栈中存放元素,第二个栈中存放最小值.其次压入元素时,如果是第一次压入,两个栈都压.否则判断要压入的元素是否小于第二个栈栈顶的元素,如果小于就压入第二个栈,否则就不压入.重复上述操作,无论任何时候我们都能按O(1)的时间复杂度取出第二个栈栈顶的元素,也就是最小的元素.

class MinStack {
    public Stack<Integer> stack1;
    public Stack<Integer> stack2;
    public MinStack() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }

    public void push(int val) {
        stack1.push(val);
        if (stack2.empty()){
            stack2.push(val);
        }else {
            if(val<=stack2.peek()){
                stack2.push(val);
            }
        }
    }

    public void pop() {
        int popVal = stack1.pop();
       if(!stack2.empty()){
           int top = stack2.peek();
           if(top==popVal){
               stack2.pop();
           }
       }
    }

    public int top() {
        return stack1.peek();
    }

    public int getMin() {
        return stack2.peek();
    }
}

三.队列的实现

        队列是只允许在一端进行插入另一端进行删除的线性表,与栈正好相反.简要概括为:"尾进头出",同样队列的实现底层既可以用顺序表也可以用链表.首先我们用单链表来实现,为了使入队和出队的时间复杂度都为O(1),我们需要记录单链表的头结点和尾结点,入队时尾插,出队时删除头结点即可.

1)单链表实现队列

class Node1{
    public Node1 next;
    public int val;

    public Node1(int val) {
        this.val = val;
    }
}
class My_queue{
    public Node1 head;
    public Node1 last;

    public void offer(int val){//入队
        Node1 node1 = new Node1(val);
        if (head==null){
            head = node1;
            last = node1;
        }else {
            last.next = node1;
            last = last.next;
        }
    }
    public int poll(){//出队
        if (isEmpty()){
            throw new RuntimeException("队列为空");
        }
        int pollVal = head.val;
        head = head.next;
        return pollVal;
    }
    public int peek(){
        if (isEmpty()){
            throw new RuntimeException("队列为空");
        }
        return head.val;
    }
    public boolean isEmpty(){
        return head==null;
    }

}

2)循环队列

        循环队列的底层为顺序表,为了使出队和入队的时间复杂度都是O(1),我们必须记录顺序表元素的首尾,rear为队尾控制元素入队,front为队首控制元素出队. 为了使顺序表达到循环的效果,我们需要借助公式(rear+1)%elem.length,front也同样借助这个公式.基于顺序表的特点,删除元素时只需后移front,增加元素只需在rear下标增加元素,之后后移rear即可.

class MyCircularQueue {
 public int elem[];
    public int front;
    public int rear;

    public MyCircularQueue(int k) {
        this.elem = new int[k+1];
    }

    public boolean enQueue(int value) {//入队
        if (isFull()){
            return false;
        }
        this.elem[rear] = value;
        rear = (rear +1)%elem.length;
        return true;
    }

    public boolean deQueue() {//出队
        if (isEmpty()){
            return false;
        }
        front = (front +1)%elem.length;
        return true;
    }

    public int Front() {//获取队头元素
        if (isEmpty()){
            return -1;
        }
        return elem[front];
    }

    public int Rear() {//获取队位元素
        if (isEmpty()){
            return -1;
        }
       if (rear==0){
           return elem[elem.length-1];
       }else {
           return elem[rear-1];
       }
    }

    public boolean isEmpty() {
        return front==rear;
    }

    public boolean isFull() {
        //rear的下一个如果为front
        if ((rear+1)%elem.length==front){
            return true;
        }
        return false;
    }
}

四.队列相关题目

1)用栈实现队列 

        一个栈必定无法实现队列,那么我们可以考虑用两个栈,入队时把要入队元素压入stack1中,出队时先把所有stack1中元素压入stack2中,然后弹出stack2的栈顶元素即可. 

class MyQueue {
 public Stack<Integer> stack1;
    public Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if(empty()){
            return -1;
        }
        if(stack2.empty()) {
            int size = stack1.size();
            for (int i = 0; i < size; i++) {
                stack2.push(stack1.pop());
            }
        }
         return stack2.pop();
    }
    public int peek() {
        if(empty()){
            return -1;
        }
        if(stack2.empty()) {
            int size = stack1.size();
            for (int i = 0; i < size; i++) {
                stack2.push(stack1.pop());
            }
        }
         return stack2.peek();
    }

    public boolean empty() {
        return stack1.empty()&&stack2.empty();
    }
}

2)用队列实现栈

        同样一个队列也无法实现栈,可以考虑使用两个队列,入队时哪个队列为空入哪个 ,如果都为空就入que1.但是与栈不同的是队列的出队顺序,我们不能把que1中的元素全部放入que2再出que2中的元素,而是移size-1个到que2,出que1.假设入队都在que1中,那么出队时只需将que1中的size-1个元素移到que2中,然后弹出que1中的元素即可.

class MyStack {

     public Queue<Integer> que1;
    public Queue<Integer> que2;

    public MyStack() {
        que1 = new LinkedList<>();
        que2 = new LinkedList<>();
    }
    public void push(int x) {
        if (!que1.isEmpty()){
            que1.offer(x);
        }else if (!que2.isEmpty()){
            que2.offer(x);
        }else {
            que1.offer(x);
        }
    }

    public int pop() {
        if (empty()){
            return -1;
        }
        if (!que1.isEmpty()){
            int size = que1.size();
            for (int i = 0; i <size-1 ; i++) {
                que2.offer(que1.poll());
            }
            return que1.poll();
        }
        if (!que2.isEmpty()){
            int size = que2.size();
            for (int i = 0; i <size-1 ; i++) {
                que1.offer(que2.poll());
            }
            return que2.poll();
        }
        return -1;
    }

    public int top() {
        if (empty()){
            return -1;
        }
        if (!que1.isEmpty()){
            int size = que1.size();
            int val = -1;
            for (int i = 0; i <size ; i++) {
                val = que1.poll();
                que2.offer(val);
            }
            return val;
        }
        if (!que2.isEmpty()){
            int size = que2.size();
            int val = -1;
            for (int i = 0; i <size ; i++) {
                val = que2.poll();
                que1.offer(val);
            }
            return val;
        }
        return -1;
    }

    public boolean empty() {
        return que1.isEmpty()&&que2.isEmpty();
    }
}

总结

        以上就是快速入门栈和队列的全部内容了,在了解栈和队列的各种实现并手撕相关习题,相信我们已经熟练掌握了栈和队列,如果我的文章对你有亿点点帮助和启发,麻烦不要忘记三连哦!