【数据结构】栈和队列

目录

1.栈Stack

1.1栈的特点及常用方法

1.2栈的模拟实现(数组)

1.3逆波兰表达式

1.3.1根据中缀表达式求后缀表达式

1.3.2后缀表达式的计算

1.3.3逆波兰表达式求值

1.4栈的oj题

1.4.1有效的括号

1.4.2栈的有效弹出序列

1.4.3最小栈

2.队列Queue

2.1队列的特点及常用方法

2.2队列的模拟实现(链表)

2.3循环队列

2.3.1设计循环队列

2.4双端队列

3.面试题

3.1用队列实现栈

3.2用栈实现队列

1.栈Stack

之前我们说的JVM栈指的是系统的一块内存，今天我们说的栈是一种数据结构。

1.1栈的特点及常用方法

特点：先进后出，和顺序表相同，底层为数组。

拓展：用链表实现栈（链式栈）

双链表无论从哪边入栈或出栈时间复杂度均为O(1)，所以LinkedList也经常被当做栈来使用；单链表可采用头插法入栈，删除头节点出栈。

public class Test {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        //push:放入数据
        stack.push(12);
        stack.push(23);
        //peek:瞥一眼，即只访问栈顶元素
        int a = stack.peek();
        System.out.println(a);//23
        //pop:删除栈顶数据
        int b = stack.pop();
        System.out.println(b);//23
        //empty:判断栈内是否为空
        System.out.println(stack.empty());//false,此时栈内还有数据12
        //search:查找数据
        //找到了返回size() - lastIndexOf(data)，没找到返回-1
        int c = stack.search(12);
        int d = stack.search(23);
        System.out.println(c);//1
        System.out.println(d);//-1
    }
}

1.2栈的模拟实现(数组)

有了之前顺序表ArrayList的铺垫，现在来自己实现栈就是手拿把掐的事情了~~

import java.util.Arrays;
public class MyStack {
    private int[] elem;//栈的底层为数组
    private int usedSize;//记录栈中有多少个有效数据

    public MyStack() { //不带参数的构造函数
        this.elem = new int[5];//默认容量为5
    }
    //判断栈是否已满
    public boolean isFull() {
        return usedSize == elem.length;
    }
    //判断栈是否为空
    public boolean isEmpty() {
        return usedSize == 0;
    }
    //push:放入数据
    public void push(int val) {
        if (isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);//已满，进行二倍扩容
        }
        elem[usedSize] = val;
        usedSize++;
    }
    //pop:删除数据
    public int pop() {
        if (isEmpty()) {
            throw new StackEmptyException("栈为空！");//抛出异常
        }
        usedSize--;
        return elem[usedSize];
    }
    //peek:获取栈顶数据
    public int peek() {
        if (isEmpty()) {
            throw new StackEmptyException("栈为空！");//抛出异常
        }
        return elem[usedSize-1];
    }
}

public class StackEmptyException extends RuntimeException{
    public StackEmptyException() {
    }
    public StackEmptyException(String message) {
        super(message);
    }
}

public class Test {
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(12);
        myStack.push(23);
        myStack.push(34);
        myStack.push(45);
        System.out.println(myStack.pop());//45
        System.out.println(myStack.peek());//34
    }
}

1.3逆波兰表达式

逆波兰表达式即后缀表达式。

1.3.1根据中缀表达式求后缀表达式

1.3.2后缀表达式的计算

1.3.3逆波兰表达式求值

逆波兰表达式求值

class Solution {
    public boolean isOperate(String x) { //判断是否为运算符
        if (x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/")) {
            return true;
        }
        return false;
    }
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String s : tokens) { //遍历字符串中每个元素
            if (!isOperate(s)) { //不是运算符即为字符串数字
                stack.push(Integer.parseInt(s));//将字符串转为数字放入栈中
            } else {
                //是运算符弹出栈顶的2个元素
                //注意这里的顺序：先弹出的元素放在运算符右侧！！！
                int num2 = stack.pop();
                int num1 = stack.pop();
                //将运算后的结果再压入栈中
                switch (s) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            }
        }
        return stack.pop();//栈顶元素即为结果值
    }
}

1.4栈的oj题

1.4.1有效的括号

有效的括号

注意：1> 栈中只放左括号；

2> 只有当字符串遍历完成且栈为空时才是匹配成功；

3> 遍历完字符串后栈中仍有括号，说明左括号多；

4> 栈空后字符串还没有遍历完，说明右括号多。

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 == '[') {
                //ch为左括号，入栈(只有左括号可以入栈)
                stack.push(ch);
            }else { //ch为右括号
                if (stack.empty()) { //栈中没有左括号用于匹配，直接结束进程
                    return false;
                }else { //栈中有左括号
                    char tmp = stack.peek();//获取栈顶元素
                    if (ch == ')' && tmp == '(' || ch == '}' && tmp =='{' || ch == ']' && tmp == '[') {
                        //如果栈顶元素tmp与此时的ch匹配
                        //弹出tmp
                        stack.pop();
                    }else { //不匹配直接结束进程
                        return false;
                    }
                }
            }
        }
        //遍历完字符串后如果栈不为空，说明左括号多了
        if (!stack.empty()) {
            return false;
        }
        return true;
    }
}

1.4.2栈的有效弹出序列

栈的有效弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。

import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int j = 0; //用于遍历popA数组
        for (int i = 0; i < pushA.length; i++) { //遍历pushA数组
            stack.push(pushA[i]); //每次循环压入一个元素
            //使用while而非if，注意循环条件！！              //栈顶元素与弹出序列匹配
            while (!stack.empty() && j < popA.length && stack.peek() == popA[j]) {
                stack.pop();                          //引用类型 (自动拆箱) int类型
                j++;                                  
            }
        }
        return stack.empty(); //栈为空说明popA为有效弹出序列
    }
}

1.4.3最小栈

最小栈

思路：

1> 首先定义两个栈：stack和minstack

2> 入栈：第一次存放时，两个栈中均要存放数据；从第二次开始，stack栈每存入一个元素，将之与最小栈栈顶元素进行比较，小于或等于时才能将此元素放入minstack栈；

3> 出栈：stack栈每出一个元素，将之与最小栈栈顶元素进行比较，相等时minstack栈才能弹出栈顶元素。

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minstack;
    public MinStack() { //定义两个栈
        stack = new Stack<>();
        minstack = new Stack<>();
    }
    public void push(int val) {
        stack.push(val);//stack栈每次都存入元素
        if (minstack.empty()) { //最小栈为空，说明是第一次存放
            minstack.push(val);
        }else {
            if (val <= minstack.peek()) { //只有val小于或等于最小栈栈顶元素时才放入
                minstack.push(val);
            }
        }
    }
    public void pop() {
        if (stack.empty()) { //如果栈为空无法弹出
            return;
        }
        int val = stack.pop();
        if (val == minstack.peek()) { //只有val等于最小栈栈顶元素时最小栈才能弹出
            minstack.pop();
        }
    }
    public int top() { //获取stack栈的栈顶元素
        if (stack.empty()) {
            return -1;
        }
        return stack.peek();
    }
    public int getMin() { //获取stack栈的最小值
        if (minstack.empty()) {
            return -1;
        }
        return minstack.peek(); //最小栈的栈顶元素就是当前stack栈的最小值
    }
}

2.队列Queue

2.1队列的特点及常用方法

特点：先进先出

拓展：用链表实现队列

双链表无论从哪边入队或出队时间复杂度均为O(1)；

单链表(记录了最后一个节点位置的情况)采用尾入队头出队时间复杂度为O(1)，头入队尾出队时间复杂度为O(n)。

public class Test {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        //offer:入队列
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        //poll:出队列
        int a = queue.poll();
        System.out.println(a);//1
        //peek:同栈，访问队头元素
        int b = queue.peek();
        System.out.println(b);//2
        //size:获取队列中有效元素个数
        int c = queue.size();
        System.out.println(c);//2
        //isEmpty:检测队列是否为空
        System.out.println(queue.isEmpty());//false
    }
}

2.2队列的模拟实现(链表)

public class MyQueue {
    static class ListNode { //静态内部类
        public int val;
        public ListNode next;
        public ListNode(int val) { //带一个参数的构造方法
            this.val = val;
        }
    }
    public ListNode head;//队头
    public ListNode last;//队尾
    public int usedSize;//有效元素
    //size:获取队列中有效元素个数
    public int size() {
        return usedSize;
    }
    //offer:尾插法入队
    public void offer(int val) {
        ListNode node = new ListNode(val);
        if (head == null) { //队列里没有元素
            head = node;//队头和队尾都是node
            last = node;
        }else {
            last.next = node;
            last = last.next;
        }
        usedSize++;
    }
    //poll:出队
    public void poll() {
        if (head == null) { //队列里没有元素
            return;
        }if (head.next == null) { //队列里只有一个元素
            head = null;
            last = null;
            return;
        }else {
            head = head.next; //删除队头
            usedSize--;
        }
    }
    //peek:获取队头元素
    public int peek() {
        if (head == null) {
            return -1;
        }
        return head.val;
    }
    //isEmpty:检测队列是否为空
    public boolean isEmpty() {
        return usedSize == 0;
    }
}

public class Test {
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.offer(1);
        myQueue.offer(2);
        myQueue.offer(3);
        myQueue.poll();
        System.out.println(myQueue.peek());//2
        System.out.println(myQueue.size());//2
        System.out.println(myQueue.isEmpty());//false

    }
}

2.3循环队列

 思考题：

1.什么时候队列为空？

   front == rear 时为空；

2.什么时候队列为满？

   1> 定义一个usedSize，当usedSize == length 时为满；(这种方法更简单)

   2> 浪费一个空间表示满；(下面设计循环队列使用的是这种方法)

3.rear / front 怎么从7下标走到0下标？

   (rear / front + 1) % length

2.3.1设计循环队列

设计循环队列

class MyCircularQueue {
    private int[] elem;//底层为数组
    private int front;//队头
    private int rear;//队尾
    public MyCircularQueue(int k) {
        this.elem = new int[k+1];//因为采用的是浪费一个空间的方法，所以要创建一个大小为k+1的数组
    }
    //入队
    public boolean enQueue(int value) {
        if (isFull()) { //判断数组是否已满
            return false;
        }
        elem[rear] = value;//尾插法入队
        rear = (rear+1)%elem.length;//不能直接rear++
        return true;
    }
    //出队
    public boolean deQueue() {
        if (isEmpty()) { //判断数组是否为空
            return false;
        }
        //头删法出队
        front = (front+1)%elem.length;//不能直接front++
        return true;
    }
    //得到队头元素
    public int Front() {
        if (isEmpty()) { //判断数组是否为空
            return -1;
        }
        return elem[front];//直接返回front下标元素即可
    }
    //得到队尾元素
    public int Rear() {
        if (isEmpty()) { //判断数组是否为空
            return -1;
        }
        int index = (rear == 0) ? elem.length-1 : rear-1; //重点！！！
        return elem[index];
    }
    public boolean isEmpty() {
        return rear == front;
    }
    public boolean isFull() {
        return (rear+1)%elem.length == front;
    }
}
public class Test {
    public static void main(String[] args) {
        MyCircularQueue myCircularQueue = new MyCircularQueue(3);
        System.out.println(myCircularQueue.enQueue(1));//ture
        System.out.println(myCircularQueue.enQueue(2));//true
        System.out.println(myCircularQueue.enQueue(3));//true
        System.out.println(myCircularQueue.enQueue(4));//false 浪费了一个空间，只能放下3个元素
        System.out.println(myCircularQueue.Front());//1
        System.out.println(myCircularQueue.Rear());//3
        System.out.println(myCircularQueue.isEmpty());//false
        System.out.println(myCircularQueue.isFull());//true
    }
}

2.4双端队列

定义：Deque ( double ended queue )，允许两端都可以进行入队和出队操作的队列。

注意：Deque是一个接口，使用时必须创建LInkedList对象，栈和队列均可使用该接口。

public class Test {
    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();//链式队列
        deque.offer(1);
        Deque<Integer> stack = new LinkedList<>();//链式栈
        stack.push(2);
        
        Deque<Integer> stack2 = new ArrayDeque<>();//双端队列的线性实现
        Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现
    }
}

3.面试题

3.1用队列实现栈

用队列实现栈

只用一个队列是无法完成这个任务的，需要两个队列来解决这个问题。

思考题：

1.如何入栈？

哪个队列不为空就往哪push；

2.如何出栈？

出不为空的队列的size-1个元素，剩下的哪个元素就是要pop的元素。

class MyStack {
    //一个队列无法完成，要定义两个队列
    private Queue<Integer> qu1;
    private Queue<Integer> qu2;
    public MyStack() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }
    public void push(int x) {
        //放到不为空的队列
        if (!qu1.isEmpty()) {
            qu1.offer(x);
        } else if (!qu2.isEmpty()) {
            qu2.offer(x);
        } else { //如果两个队列都为空默认放到第一个
            qu1.offer(x);
        }
    }
    public int pop() {
        if (empty()) { //当两个队列都是空时无法弹出
            return -1;
        }
        if (!qu1.isEmpty()) { //当qu1不为空时
            int currentSize = qu1.size();
            for (int i = 0; i < currentSize-1; i++) { //出不为空队列的size-1个元素并放入空队列
                int x = qu1.poll();
                qu2.offer(x);
            }
            return qu1.poll();//剩下的最后一个元素就是要pop的值
        }
        if (!qu2.isEmpty()) { //当qu2不为空时，同上
            int currentSize = qu2.size();
            for (int i = 0; i < currentSize-1; i++) { //不能直接写 i < qu1.size()-1
                int x = qu2.poll();                   //因为size一直在变
                qu1.offer(x);
            }
            return qu2.poll();
        }
        return -1;
    }
    public int top() { //即peek
        if (empty()) { 当两个队列都是空时无法peek
            return -1;
        }
        if (!qu1.isEmpty()) {
            int x = -1;
            int currentSize = qu1.size();
            for (int i = 0; i < currentSize; i++) { //这里是 i < currentSize!!
                x = qu1.poll();
                qu2.offer(x);
            }
            return x;
        }
        if (!qu2.isEmpty()) {
            int x = -1;
            int currentSize = qu2.size();
            for (int i = 0; i < currentSize; i++) {
                x = qu2.poll();
                qu1.offer(x);
            }
            return x;
        }
        return -1;
    }
    public boolean empty() { //判断两个队列是否同时为空
        return qu1.isEmpty() && qu2.isEmpty();
    }
}

3.2用栈实现队列

 用栈实现队列

和上题一样，只用一个栈是无法完成任务的，也需要两个栈。

思考题：

1.如何入队？

统一入到第一个栈中；

2.如何出队？

将第一个栈中的全部数据倒入第二个栈中，然后出第二个栈的栈顶元素。

import java.util.Stack;

class MyQueue {
    //一个栈无法完成，要定义两个栈
    private Stack<Integer> s1;
    private Stack<Integer> s2;
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    public void push(int x) { //入队只入第一个栈s1
        s1.push(x);
    }
    public int pop() { 
        if (!s2.isEmpty()) { //如果s2不为空
            return s2.pop(); //返回s2栈顶元素
        }else {
            while (!s1.isEmpty()) { //如果s2为空，s1不为空
                int val = s1.pop(); //将s1中所有元素倒入s2中
                s2.push(val);
            }
            return s2.pop(); //返回s2栈顶元素
        }
    }
    public int peek() { //原理与pop一模一样
        if (!s2.isEmpty()) {
            return s2.peek(); //此处pop改为peek即可
        }else {
            while (!s1.isEmpty()) {
                int val = s1.pop();
                s2.push(val);
            }
            return s2.peek(); //此处pop改为peek即可
        }
    }
    public boolean empty() { //判断两个栈是否同时为空
        return s1.isEmpty() && s2.isEmpty();
    }
}

一句话来概括就是：吃了就吐是栈，吃了就拉是队列（这是一篇有味道的博客哈哈哈），通俗易懂~之后就是二叉树的学习了，加油加油，，肝就完了！！！