亲宝软件园·资讯

展开

Java栈和队列 Java数据结构学习之栈和队列

愿美梦成真 人气:0
想了解Java数据结构学习之栈和队列的相关内容吗,愿美梦成真在本文为您仔细讲解Java栈和队列的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Java栈和队列,Java数据结构,下面大家一起来学习吧。

一、栈

1.1 概述

Java为什么要有集合类: 临时存储数据。
链表的本质: 对象间通过持有和引用关系互相关联起来。

线性表: 普通线性表, 操作受限线性表(某些操作受到限制 --> 某一个线性表它的增删改操作受到限制) --> 栈 & 队列

1.1.1 线性表的概念

(1)线性表:n个数据元素的有序序列。

①首先,线性表中元素的个数是有限的。
②其次,线性表中元素是有序的。

(2)那这个”序”指的是什么呢?

除表头和表尾元素外,其它元素都有唯一前驱和唯一后继,其唯一前驱或唯一后继确定了该元素在线性表中的位置。
②因此,线性表中,每个数据元素都有一个确定的位序,这个确定的位序我们称之为索引。 表头元素有唯一后继,无前驱,表尾元素有唯一前驱,无后继。

1.1.2 栈的概念

栈是一种”操作受限”的线性表,体现在只能在一端插入和删除数据,符合FILO的特性。

FILO: 先进后出,
LIFO: 后进先出

1.1.3 栈的应用

在这里插入图片描述

线性表和哈希表在以后工作中会最常用。
栈在实际工作中不常用

应用场景:

1.函数调用栈
2.反序字符串: 实现reNumber(str)方法,反转字符串(附代码) 。

public class DemoStack1 {
    public static void main(String[] args) {

        String str = "123456789";
        String reStr = reStr(str);
        System.out.println(reStr);

    }

    // 栈先进后出
    public static String reStr(String str){
        MyArrayStack<Character> stack = new MyArrayStack<>();

        for (int i = 0; i < str.length(); i++) {
            stack.push(str.charAt(i));
        }

        StringBuffer buffer = new StringBuffer();

        // 1 2 3 4 5 6 7 8 9
        while (!stack.isEmpty()){
            Character pop = stack.pop();
            buffer.append(pop);
        }

        return buffer.toString();
    }
}

3.括号匹配问题: 实现judgeBracket(str)方法来判断括号匹配 (附代码)。

public class DemoStack2 {
    public static void main(String[] args) {

        String str = "public class) DemoStack2 {public static void main(String[] args) {}}";

        boolean bool = judgeBracket(str);
        System.out.println(bool);

    }

    public static  boolean judgeBracket(String str){
        MyArrayStack<Character> stack = new MyArrayStack<>();

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            // 判断c 是left括号, 然后入栈

            if (c == '{'){
                stack.push('}');
            } else if (c == '['){
                stack.push(']');
            }else if (c == '('){
                stack.push(')');
            } else if (c == '}' || c == ')' || c == ']'){
                Character pop = stack.pop();
                if (c != pop){// 不匹配
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}

4.编译器利用栈实现表达式求值

5.浏览器的前进后退功能

6. 利用栈实现 DFS: depth-first-search 深度优先遍历(树 图)

编译器利用栈实现表达式求值

中缀表达式: 2 + 3 * 2 给人看的 , 运算符放到中间
前缀表达式: + 2 * 3 2 运算符放到之前
后缀表达式: 2 3 2 * + 运算符放到后面

// 中缀表达式转化为后缀:
// 遍历中缀表达式
// 遇到操作数输出
// 遇到操作符, 出栈, 直到遇到更低优先级的操作符, 操作符入栈
// 遍历完成, 全部弹栈

// 中缀表达式转化为前缀:
// 遍历中缀表达式: 逆序遍历
// 遇到操作数输出: 头插法
// 遇到操作符, 出栈, 只弹出更高优先级的操作符, 操作符入栈
// 遍历完成, 全部弹栈

二、队列

2.1 队列的概念

队列也是一种”操作受限”的线性表,体现在一端插入数据在另一端删除数据,特性是FIFO。

在这里插入图片描述

2.2 队列的实现

实现一个集合类
集合类: 数据容器
底层: 数组 or 链表
数据结构表现: 队列

(1)用数组实现一个队列。

/**
 * 用数组实现一个队列
 * 集合类角度: 数据容器
 * 底层: 数组
 * 表示: 队列
 */
public class MyArrayQueue <T> {

    private final int MAX_CAPACITY = Integer.MAX_VALUE - 8;
    private final int INIT_CAPACITY = 16;

    private Object[] objs;
    private int size;
    private int head;// 头的下标
    private int end;// 尾的下标


    public MyArrayQueue(){
        objs = new Object[INIT_CAPACITY];
    }
    public MyArrayQueue(int initCapcity){
        if (initCapcity <= 0 || initCapcity > MAX_CAPACITY) throw new IllegalArgumentException("" + initCapcity);

        objs = new Object[initCapcity];
    }

    public boolean offer(T t){
        // 如果数组满了
        if (size == objs.length){
            int newLen = getLen();
            grow(newLen);
        }

        // 可以添加
        if (isEmpty()){
            // 没有任何元素存储: 新添加的元素就是唯一的元素
            objs[head] = t;
            end = head;
            size++;
            return true;
        } else {
            // 原本存储就有内容

            // 尾后移一位
            end = (end + 1) % objs.length;
            objs[end] = t;
            size++;
            return true;
        }
    }

    private void grow(int newLen) {
        Object[] newArr = new Object[newLen];
        for (int i = 0; i < objs.length; i++) {
            int index = (head + i) % objs.length;

            newArr[i] = objs[index];
        }
        objs = newArr;
        head = 0;
        end = size - 1;
    }

    private int getLen() {
        int oldLen = objs.length;
        int newLen = oldLen << 1;
        // 判断新长度是否溢出
        if (newLen <= 0 || newLen > MAX_CAPACITY){
            newLen = MAX_CAPACITY;
        }
        // 如果新长度和旧长度一样
        if (newLen == oldLen)throw  new RuntimeException("stack can not add");

        return newLen;
    }


    public T poll(){
        if (isEmpty()) throw new RuntimeException("queue is empty");

        if (size == 1){
            // 原队列中只剩一个元素
            T oldValue = (T)objs[head];
            head = 0;
            end = 0;
            size--;
            return oldValue;
        } else {
            // 队列中超过一个元素
            T oldValue = (T)objs[head];
            head = (head + 1) % objs.length;
            size--;
            return oldValue;
        }
    }

    public T peek(){
        if (isEmpty()) throw new RuntimeException("queue is empty");
        return (T)objs[head];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }
}

(2)用链表实现一个链表。

public class MyLinkedQueue <T> {

    private Node head;// 队头
    private Node end; // 队尾
    private int size;

    // 添加 offer
    // 删除 poll
    // 查看队头元素 peek

    public  boolean offer(T t){

        // 如果原队列为空
        if (isEmpty()){// 原队列空
            // 让头尾都指向这个新加的结点
            head = new Node(t, null);
            end = head;
            size++;
            return true;
        }

        // 原队列不空
        // 把这个元素添加到队尾
        end.next = new Node(t, null);
        end = end.next;// end后移
        size++;
        return true;
    }

    public T poll(){
        if (isEmpty()) throw  new RuntimeException("queue is empty");

        if (size == 1){
            // 代表着, 链表中只有一个元素
            T oldVlaue = head.value;
            head = null;
            end = null;
            size--;
            return  oldVlaue;
        }else {
            T oldVlaue = head.value;
            head = head.next;
            size--;
            return oldVlaue;
        }
    }

    public T peek(){
        if (isEmpty()) throw  new RuntimeException("queue is empty");
        return head.value;
    }


    public boolean isEmpty(){
        return size == 0;
    }
    public int size(){
        return size;
    }




    class Node{
        T value;
        Node next;

        public Node(T value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}

2.3 队列的应用

(1)队列更不常用(自己写代码使用不常用):

(2)常见, 很多jdk源码, 中间件的源码上 很多地方使用了队列

Eg:

①生产者消费者问题

生产者 – 消费者
生产者: 厨师
消费者: 吃面包的人
桌子: 放面包的地方

②线程池

线程池: 任务
生产者: 产生任务
消费者: 线程
桌子: 队列

③生态环境:

第三方轮子: 要看懂
Maven

④消息队列和缓存。

(3)普通队列的应用场景是很有限的,一般在工程中用到的是阻塞队列。

①阻塞队列(有一个队列, 大小一定):常用于生产者-消费者模型中。
当队列满的时候,入队列就阻塞。
当队列空的时候,出队列就阻塞。

②利用队列实现 BFS:breadth first search 广度优先搜索/ 遍历 ()

加载全部内容

相关教程
猜你喜欢
用户评论