数据结构 Java数据结构栈和队列以及LeetCode相关面试题

admin • 2021-12-06 20:08 • Java

1. 栈(Stack)

1.1 概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。

Stack的Push和Pop遵循先进后出的原则,如图:

1.2 实现

利用顺序表实现，即使用尾插 + 尾删的方式实现
利用链表实现，则头尾皆可.
头插法: 入栈O(1) 出栈O(1)
尾插法: 入栈O(N) 出栈O(N)

相对来说，顺序表的实现上要更为简单一些，所以我们优先用顺序表实现栈。

public class MyStack {
    //简单的实现,使用int元素即可,也不考虑扩容问题
    private int[] elem = new int[100];
    private int usedSize = 0;// 栈中存在多少个有效元素
    
    //入栈
    public void push(int val){
        elem[usedSize] = val;
        usedSize++;
    }
    
    //取栈顶元素(最后进来的那个元素)
    public int peek(){
        return elem[usedSize - 1];
    }
    
    //出栈
    public int pop(){
        int ret = elem[usedSize - 1];
        usedSize--;
        return ret;
    }
}

2. 队列(Queue)

2.1 概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

2.2 实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

public class MyQueueByLinkedList {
    /**
     * Node这个类叫做"内部类",定义在某个类或者方法中的类
     * static 效果就是: 创建Node的实例不依赖 MyQueueByLinkedList 这个类的实例
     */
    static class Node{
        public int val;
        Node next = null;

        public Node(int val){
            this.val = val;
        }
    }

    // 创建一个链表,就得有头节点.此处的head节点不是傀儡节点.
    // 基于链表来实现队列,可以入队列可以从尾巴插入,出队列从头部删除;
    // 也可以入队列从头部插入,出队列从尾部删除
    // 无论是那种实现方式,最好都把头和尾都记录下来.
    private Node head = null;
    private Node tail = null;

    // 入队列(标准库的队列,入队列操作就叫 offer)
    public void offer(int val) {
        Node newNode = new Node(val);
        if(head == null){
            head = newNode;
            tail = newNode;
            return;
        }
        //如果非空
        tail.next = newNode;
        tail = newNode;
    }

    // 出队列
    public Integer poll(){
        // 如果当前队列就是空队列,再去poll显然不科学
        if(head == null){
            // 如果出队列失败,返回一个错误的值
            return null;
        }
        int ret = head.val;
        head = head.next;
        if(head == null){
            //删除当前元素之后,队列变成了空的队列
            tail = null;

        }
        return ret;
    }

    // 取队首的元素
    public Integer peek() {
        if(head == null){
            return null;
        }
        return head.val;
    }
}

2.3 循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。
环形队列通常使用数组实现。

public class MyQueueByArray {
    private int[] elem = new int[100];
    // [head,tail) 有效元素的范围. 注意, tail 可能在 head 之前
    private int head = 0; // 表示对首元素下标
    private int tail = 0; // 表示对尾下一个元素的下标
    private int size = 0; // 元素个数

    public void offer(int val){
        if (size == elem.length) {
            //队列满了, 无法继续插入
            return ;
        }
        // 保证这个操作下标不能越界
        elem[tail] = val;
        tail++;
        // tail ++ 之后如果超出数组有效范围,就从头开始
        if (tail >= elem.length){
            tail = 0;
        }
        size++;
    }

    public Integer poll(){
        if (size == 0){
            return null;
        }
        Integer ret = elem[head];
        head++;
        if(head >= elem.length){
            head = 0;
        }
        size--;
        return ret ;
    }

    public Integer peek(){
        if(size == 0){
            return null;
        }
        return elem[head];
    }
}

3. 双端队列 (Deque)

3.1 概念

双端队列（deque) 是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

4. java 中的栈和队列

Stack

方法	解释
E push(E item)	压栈
E pop()	出栈
E peek()	查看栈顶元素
boolean empty()	判断栈是否为空

Stack方法的演示:

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        //压栈
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        //查看栈顶元素
        System.out.println(stack.peek());

        //出栈
        int ret = stack.pop();
        System.out.println(ret);  //4
        ret = stack.pop();
        System.out.println(ret);  //3
        ret = stack.pop();
        System.out.println(ret);  //2
        ret = stack.pop();
        System.out.println(ret);  //1
        //判断栈是否为空
        System.out.println(stack.empty());
        //此时栈为空 如果 查看栈顶元素 或者 出栈 会报异常(EmptyStackException)
        System.out.println(stack.peek());
        System.out.println(stack.pop());
    }

运行结果:

Queue

错误处理	抛出异常	返回特殊值
入队列	add(e)	offer(e)
出队列	remove()	poll()
队首元素	element()	peek()

Deque

头部/尾部	头部元素（队首）		尾部元素（队尾）
错误处理	抛出异常	返回特殊值	抛出异常	返回特殊值
入队列	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
出队列	removeFirst()	pollFirst()	removeLast()	pollLast()
获取元素	getFirst()	peekFirst()	getLast()	peekLast()

总结:
Stack:
push ,pop,peek.当当前是一个空栈的,再去pop或者peek就会产生异常.
Queue:
add,remove,element 如果当前操作失败就会抛出异常;
offer,poll,peek 如果操作失败就会返回一个错误值;

5. LeetCode 题目

第一题 : 有效的括号

有效的括号
LeetCode 20:
描述:
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

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

解题思路:

1. 遍历字符串,依次取出字符串中的字符.
      1.1 如果取出的字符串为左括号例如’(’,’[’,’{’.就放入栈中
      1.2 如果取出的字符串为右括号例如’)’,’]’,’}’.就和栈顶元素比较是否匹配.
            a) 匹配就出栈,然后继续遍历.
            b) 不匹配就直接返回false
      1.3 如果栈为空,且取出的字符是右括号,则返回false没有例如字符串"]()"
2. 遍历结束后,判断是否栈为空
      2.1 如果为空则满足题意 return true;
      2.2 如果不为空表示没有足够匹配的字符, return false; 如字符串"["

画图解析:

代码实现:

    public boolean isValid(String str) {
        Map<Character,Character> map = new HashMap<>();
        map.put('(',')');
        map.put('[',']');
        map.put('{','}');

        //1.先创建一个栈,栈中保存字符类型即可
        Stack<Character> stack = new Stack<>();
        //2.遍历字符串的每个字符
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            //3.判断字符 ch 是否为左括号,如果是,就入栈
            if (ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
                continue;//进入下次循环,取出下一个字符
            }
            if(stack.empty()){
                //如果ch不是左括号,且栈为空,则不是合法括号
                return false;
            }
            //4.判断ch是否是右括号,如果是,就取栈顶元素比较是否相等
            char top = stack.pop();//栈顶元素
            //以下是3种情况合法情况 -- 写法1
            /*if(top == '(' && ch == ')') {
                continue;
            }
            if(top == '[' && ch == ']') {
                continue;
            }
            if(top == '{' && ch == '}') {
                continue;
            }*/
            // 判断合法情况 -- 写法2
            if(map.get(top) == ch){
                continue;
            }
            //如果三种情况都不满足,表示不是合法情况
            return false;
        }
        //遍历完成后 如果栈为空 则满足条件
        if(stack.empty()) {
            return true;
        }
        //否则就不合法
        return false;
    }

第二题 : 用队列实现栈

用队列实现栈
LeetCode 225:
描述:
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

解题思路:

1. 用两个队列来模拟一个栈的效果,引用两个队列 A 和 B .
2. 入栈 : 直接把元素入队到A中即可
3. 出栈 : 因为队列是先进先出的,栈是后进先出的,可以让 A队列元素出队列然后入队列到 B队列中,直到A队列中最后一个元素的时候,直接出队列,就实现了后进先出.然后要让A和B交换,始终让入栈到A队列中.
4. 取栈顶元素 : 取栈顶元素就是出栈的元素, 不过取栈顶元素要把这个元素返回去
5. 判断是否为空 : A 和 B都为空的时候就是空栈

画图解析:

代码实现:

import java.util.LinkedList;
import java.util.Queue;

public class MyStackByDoubleQueue {
    private Queue<Integer> A = new LinkedList<>();
    private Queue<Integer> B = new LinkedList<>();

    public void push(int x) {
        // x往A中入队列即可
        A.offer(x);
    }

    public Integer pop() {
        if (empty()){
            return null;
        }
        // 把A中的元素往 B 中放
        while(A.size() > 1) {
            Integer font = A.poll();
            B.offer(font);
        }
        //当循环结束后,A 中 应该只剩1个元素
        //这个元素就应该是被出栈的元素
        int ret = A.poll();
        //交换A和B
        swapAB();
        return ret;
    }

    private void swapAB(){
        Queue<Integer> tmp = A;
        A = B;
        B = tmp;
    }

    public Integer top() {
        if (empty()){
            return null;
        }
        // 把A中的元素往 B 中放
        while(A.size() > 1) {
            Integer font = A.poll();
            B.offer(font);
        }
        //当循环结束后,A 中 应该只剩1个元素
        //这个元素就应该是被出栈的元素
        int ret = A.poll();
        B.offer(ret); // top 和 pop的区别就是 top要把元素返回去,pop不需要返回去
        //交换A和B
        swapAB();
        return ret;
    }

    public boolean empty() {
        return A.isEmpty() && B.isEmpty();
    }
}

第三题 : 用栈实现队列

用栈实现队列
LeetCode 232:
描述:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

解题思路:

1. 引用2个栈A和B,A专门用来入队列;B专门用来出队列
2. 实现入队列: 先把B中的所有元素都放到A中(因为出栈的时候元素会放入B中),然后直接往A里入栈.
3. 实现出队列: 后进先出的栈实现先进先出的队列,要让A中的所有元素移入B中,先出的的元素就是后进的,此时栈顶就是就是最先进入的元素,B中出栈操作即可
4. 实现取队首元素: 同出队列操作,把A所有元素放入B中,然后取B的栈顶元素就是队首元素.
5. 判空: A 和 B 都为空.

画图解析:

代码实现:

import java.util.Stack;

public class MyQueueByDoubleStack {
    private Stack<Integer> A = new Stack<>();
    private Stack<Integer> B = new Stack<>();

    public void push(int x) {
        //1.先将B中的元素 放入 A 中
        while (!B.isEmpty()){
            int tmp = B.pop();
            A.push(tmp);
        }
        //2.把新元素放入A中
        A.push(x);
    }


    public Integer pop() {
        //1.如果为空 直接返回
        if(empty()){
            return null;
        }
        //2.把A中的元素都给B
        while(!A.isEmpty()){
            int tmp = A.pop();
            B.push(tmp);
        }
        //3.针对B进行出栈
        return B.pop();
    }

    public Integer peek() {
        //1.如果为空 直接返回
        if(empty()){
            return null;
        }
        //2.把A中的元素都给B
        while(!A.isEmpty()){
            int tmp = A.pop();
            B.push(tmp);
        }
        //3.取B的栈顶元素
        return B.peek();
    }

    public boolean empty() {
        return A.isEmpty() && B.isEmpty();
    }
}

第四题 : 最小栈

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

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

解题思路:

1. 引用2个栈A和B, A按照正常栈的规则入栈出栈,B存放的是A的最小值以及A历史的最小值
2. 实现入栈操作: A中: 直接入栈 . B中: 取要入栈的值和 B栈顶元素比较,把较小值入栈到B中.
3. 实现出栈操作: A 和 B 一起出栈
4. 实现取栈顶元素操作: 直接取 A 栈顶元素
5. 实现取最小值操作: 直接取 B 栈顶元素

画图解析:

代码实现:

import java.util.Stack;

public class MinStack {
    private Stack<Integer> A = new Stack<>();
    private Stack<Integer> B = new Stack<>();

    public void push(int x){
        //A 直接入栈
        A.push(x);
        //如果B为空 直接入栈
        if(B.isEmpty()){
            B.push(x);
            return;
        }
        //如果B不为空,比较x和B栈顶的较小值,将较小值入栈
        int min = B.peek();
        min = min < x ? min : x;
        B.push(min);
    }

    public Integer pop(){
        //如果A为空 直接返回
        if(A.isEmpty()){
            return null;
        }
        //B和A同时出栈
        B.pop();
        return A.pop();
    }

    public Integer top(){
        //如果A为空 直接返回
        if(A.isEmpty()){
            return null;
        }
        return A.peek();
    }

    public Integer getMin(){
        //如果B为空 直接返回
        if(B.isEmpty()){
            return null;
        }
        //B的栈顶即使最小元素
        return B.peek();
    }

}

第五题 : 设计循环队列

设计循环队列
LeetCode 622:
描述:
设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

解题思路:

1. 循环队列运用数组实现. head和tail是下标,head位置始终都是队首的元素;tail位置始终都是队尾的下一个元素有效元素个数[ head, tail) 左闭右开
2. 入队列 : 把新元素放到 tail 位置上,同时 tail++.
3. 出队列 : 取出 head 位置的元素,同时 head++.
4. 空队列 : 有效元素个为0
5. 满队列 : 有效元素个数等于数组长度
6. 注意当head 和 tail达到元素上线时,回到最开始的位置.

画图解析:

代码实现:

public class MyCircularQueue {
    private int[] elem;
    private int head = 0;//队首元素下标
    private int tail = 0;//队尾下一个元素下标
    private int size = 0;//有效元素个数

    /**
     * 构造器，设置队列长度为 k 。
     * @param k 队列长度
     */
    public MyCircularQueue(int k) {
        this.elem = new int[k];
    }

    /**
     * 向循环队列插入一个元素。如果成功插入则返回真。
     * @param value 插入元素
     * @return
     */
    public boolean enQueue(int value) {
        //队满就无法入队 返回false
        if(size == elem.length){
            return false;
        }
        elem[tail] = value;
        tail++;
        //tail>=队列长度 要归零
        if(tail >= elem.length){
            tail = 0;
        }
        size++;
        return true;
    }

    /**
     * 从循环队列中删除一个元素。如果成功删除则返回真。
     * 队头出
     * @return
     */
    public boolean deQueue() {
        //如果队列为空 没有要删除的返回false
        if(size == 0){
            return false;
        }
        head++;
        //head>=队列长度 要归零
        if(head >= elem.length){
            head = 0;
        }
        size--;
        return true;
    }

    /**
     * 从队首获取元素。如果队列为空，返回 -1 。
     * @return
     */
    public int Front() {
        if(size == 0){
            return -1;
        }
        return elem[head];
    }

    /**
     * 获取队尾元素。如果队列为空，返回 -1 。
     * @return
     */
    public int Rear() {
        if(size == 0){
            return - 1;
        }
        if(tail==0) return elem[elem.length - 1];
        return elem[tail-1];
    }

    /**
     * 检查循环队列是否为空。
     * @return
     */
    public boolean isEmpty() {
        if(size == 0){
            return true;
        }
        return false;
    }

    /**
     * 检查循环队列是否已满
     * @return
     */
    public boolean isFull() {
        if(size == elem.length){
            return true;
        }
        return false;
    }

}

第六题 : 逆波兰表达式求值(后缀表达式)

后缀表达式
 逆波兰表达式求值
LeetCode 150:
剑指 Offer Ⅱ 036:
描述:
根据逆波兰表示法，求表达式的值。

有效的算符包括+、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

解题思路:

1. 中缀记法是一个通用的算术或逻辑公式表示方法,中缀表达式如3 + 4
前缀表达式如+ 3 4 , 后缀表达式如3 4 +. 前缀和后缀表达式都表示3+4
2. 用栈解决逆波兰表达式, 遍历字符数组
① 如果为数字入栈
② 如果为 +、-、*、/出栈两个数字完成对应操作,然后将得到的数据入栈
3. 注意完成对应 +、-、*、/操作时,是后一个出栈的数据 +、-、*、/ 前一个出栈的数据

画图解析:

代码实现:

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        int sum = 0;
        //遍历
        for (int i = 0; i < tokens.length; i++) {
            if("+".equals(tokens[i])){
                // '+' 运算
                stack.push(stack.pop() + stack.pop());
            }else if ("-".equals(tokens[i])){
                // '-' 运算
                stack.push(-stack.pop() + stack.pop());
            }else if ("/".equals(tokens[i])){
                // '/' 运算 
                int m = stack.pop();
                int n = stack.pop();
                stack.push(n / m);
            }else if ("*".equals(tokens[i])){
                // '*' 运算
                stack.push(stack.pop() * stack.pop());
            }else{
                // 不是运算符 直接入栈
                stack.push(Integer.valueOf(tokens[i]));
            }
        }
        //遍历结束 出栈即是结果
        return stack.pop();
    }

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

java leetcode 数据结构栈队列

二维码

接口自动化测试-使用openpyxl库读取xlsx测试用例数据【python+unittest+requests+openpyxl】

< <上一篇

【MySQL 数据库进阶】面试官常问索引+事务+JDBC

下一篇>>

数据结构 Java数据结构 栈和队列 以及LeetCode相关面试题

栈和队列

1. 栈(Stack)

1.1 概念

1.2 实现

2. 队列(Queue)

2.1 概念

2.2 实现

2.3 循环队列

3. 双端队列 (Deque)

3.1 概念

4. java 中的栈和队列

5. LeetCode 题目

第一题 : 有效的括号

解题思路:

画图解析:

代码实现:

第二题 : 用队列实现栈

解题思路:

画图解析:

代码实现:

第三题 : 用栈实现队列

解题思路:

画图解析:

代码实现:

第四题 : 最小栈

解题思路:

画图解析:

代码实现:

第五题 : 设计循环队列

解题思路:

画图解析:

代码实现:

第六题 : 逆波兰表达式求值(后缀表达式)

解题思路:

画图解析:

代码实现:

最新文章

分类

标签云

数据结构 Java数据结构栈和队列以及LeetCode相关面试题