[Реализация Java] стек и очередь настолько просты

Java задняя часть алгоритм Apple

Введение

В предыдущей статье уже говорилось о связанных списках [Java реализует односвязный список], он и массив являются основой линейной структуры, в этой статье в основном объясняется применение линейной структуры:кучаиочередь

Если есть неправильное место, я надеюсь, что все могут быть более внимательными и правильными.Если есть лучший способ понять, я надеюсь, что вы можете оставить сообщение в комментариях, чтобы все могли учиться~

Во-вторых, структура данных [стек] настолько проста

2.1 Введение в структуру данных [стек]

Длина стека структуры данных выглядит так:

На самом деле это очень легко понять, мы можем складыватьвыглядеть как коробка

  • Помещение чего-либо в коробку называется штабелированием.
  • Взять что-то из коробки называется поппингом.
  • Нижняя часть коробки называется дном стопки.
  • Верхняя часть коробки называется вершиной стека.

Когда дело доходит до характеристик стека, должно быть классическое предложение, чтобы подвести итог:LIFO, последний вошел первым

  • Положите яблоки в коробку.Если вы хотите вынуть яблоки со дна коробки, вы должны сначала удалить яблоки в верхней части коробки.

2.2 Структура данных [стек] Реализация кода

Существует два типа стеков:

  • Статический стек (реализация массива)
  • Динамический стек (реализация связанного списка)

Из прошлой статьи о написании связного списка я понял, насколько мой алгоритм подлый, да и обычные операции с односвязным списком тоже могут вызвать у меня головокружение.

Так как мой связанный список не очень привычен, а стек не сложный, то я использую связанный список для создания динамического стека!

Поскольку это связанный список, возьмем код предыдущего узла:


public class Node {

    //数据域
    public int data;

    //指针域，指向下一个节点
    public Node next;

    public Node() {
    }

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

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
    
}

Чтобы использовать связанный список для представления стека, на этот раз будет два указателя:

  • вершина стека
  • нижняя часть стека

public class Stack {

    public Node stackTop;
    public Node stackBottom;

    public Stack(Node stackTop, Node stackBottom) {
        this.stackTop = stackTop;
        this.stackBottom = stackBottom;
    }

    public Stack() {
    }


}

2.2.1 Переместить стек

На узел, на который изначально указывает вершина стека, указывает новый узел, а вершина стека указывает на вновь добавленный узел.



    /**
     * 进栈
     *
     * @param stack 栈
     * @param value 要进栈的元素
     */
    public static void pushStack(Stack stack, int value) {

        // 封装数据成节点
        Node newNode = new Node(value);


        // 栈顶本来指向的节点交由新节点来指向
        newNode.next = stack.stackTop;

        // 栈顶指针指向新节点
        stack.stackTop = newNode;

    }

2.2.2 Обход стека

Пока указатель на верхний элемент стека не указывает на низ стека, то всегда выводить результат обхода:


    /**
     * 遍历栈(只要栈顶指针不指向栈底指针，就一直输出)
     *
     * @param stack
     */
    public static void traverse(Stack stack) {
        Node stackTop = stack.stackTop;

        while (stackTop != stack.stackBottom) {

            System.out.println("关注公众号：Java3y：" + stackTop.data);

            stackTop = stackTop.next;
        }


    }

контрольная работа:


    public static void main(String[] args) {

        //初始化栈(无元素)
        Stack stack = new Stack(new Node(), new Node());

        //栈顶和栈尾是同一指向
        stack.stackBottom = stack.stackTop;

        //指向null
        stack.stackTop.next = null;


        //进栈
        pushStack(stack, 3);
        pushStack(stack, 4);
        pushStack(stack, 5);

        traverse(stack);

    }

результат:

Это соответствует принципу «первым пришел — последним вышел».

2.2.3 Определить, пуст ли стек

Очень просто, пока вершина стека и низ стека указывают на одну и ту же точку, стек пуст.


    /**
     * 判断该栈是否为空
     *
     * @param stack
     */
    public static void isEmpty(Stack stack) {
        if (stack.stackTop == stack.stackBottom) {

            System.out.println("关注公众号：Java3y---->该栈为空");
        } else {

            System.out.println("关注公众号：Java3y---->该栈不为空");

        }

    }

2.2.4 Вытолкнуть стек

  1. Проверьте, пуст ли стек, прежде чем извлекать стек, если нет, извлекайте стек...
  2. Назначить указатель элемента наверху стека (указывающий на следующий узел) указателю наверху стека (завершить всплывающее окно)
    /**
     * 出栈(将栈顶的指针指向下一个节点)
     * @param stack
     */
    public static void popStack(Stack stack) {

        // 栈不为空才能出栈
        if (!isEmpty(stack)) {

            //栈顶元素
            Node top = stack.stackTop;

            // 栈顶指针指向下一个节点
            stack.stackTop = top.next;

            System.out.println("关注公众号：Java3y---->出栈的元素是：" + top.data);

        }
    }

Тестовый поп:

Поп несколько раз:

2.2.5 Очистить стек

В то время, когда я изучал C, мне нужно было освободить ресурсы памяти, но Java не использовала это, поэтому вершина стека указывала на низ стека, и стек был пуст.


    /**
     * 清空栈
     * @param stack
     */
    public static void clearStack(Stack stack) {

        stack.stackTop = null;
        stack.stackBottom = stack.stackTop;
    }

В-третьих, структура данных [очередь] настолько проста

Длина очереди структуры данных выглядит так:

На самом деле, очередь очень легко понять, мы можем использовать очередь длястоять в очереди как дети

  • Дети в конце очереди прибыли в указанное место --> покидают очередь
  • Присоединился новый ребенок --> присоединиться к команде

По сравнению со стеком характеристики очереди таковы: первый пришел, первый ушел.

  • Дети, которые выстроятся первыми, обязательно получат еду первыми!

Существует два типа очередей:

  • Статическая очередь (реализация массива)
  • Динамическая очередь (реализация связанного списка)

На этот раз я использую массивы для реализации статических очередей. Стоит отметить, что:Часто реализуются статические очереди, нас всех превращают в круговые очереди

сделать круговую очередьПреимущество в том, что он не тратит ресурсы памяти.!

3.1 Реализация кода структуры данных [очереди]

На этот раз мы используем массив для реализации статической очереди, поэтому мы можем спроектировать ее следующим образом:


public class Queue {


    //数组
    public int [] arrays;

    //指向第一个有效的元素
    public int front;

    //指向有效数据的下一个元素(即指向无效的数据)
    public int rear;

}

Из приведенного выше дизайна мы можем найти:задний не указывает на последний допустимый элемент, что очень удобно в циклической очереди! Поскольку эта конструкция можетВыделим голову и хвост линии(В противном случае круговая очередь постоянно ставится в очередь или удаляется из нее, и позиция быстро меняется)

Так как у нас круговая очередь, тоfrontиrearзначение будет часто меняться, мы должны поставитьfrontиrearЗначение ограничено диапазоном, иначе оно превысит длину очереди.

Есть такой алгоритм:rear=（rear+1)%数组长度

  • Например, индекс сзади равен 2, длина массива равна 6, а одна цифра сзади равна 3, тогдаrear = （rear+1) % 6, результат по-прежнему 3

3.1.2 Инициализация очереди

В это время очередь пуста, и массиву выделено 6 длин (можно загрузить только 5 актуальных чисел, а задний указывает на недопустимую позицию)


    public static void main(String[] args) {

        //初始化队列
        Queue queue = new Queue();

        queue.front = 0;
        queue.rear = 0;
        queue.arrays = new int[6];
        
    }

3.1.3 Определить, заполнена ли очередь

Если задний указатель и передний указатель находятся рядом друг с другом, то очередь заполнена



    /**
     * 判断队列是否满了，front和rear指针紧挨着，就是满了
     * @param queue
     * @return
     */
    public static boolean isFull(Queue queue) {
        if ((queue.rear + 1) % queue.arrays.length == queue.front) {

            System.out.println("关注公众号：Java3y--->此时队列满了！");
            return true;
        } else {
            System.out.println("关注公众号：Java3y--->此时队列没满了！");
            return false;
        }
    }

3.1.4 Постановка в очередь

  1. Определить, заполнена ли очередь
  2. Значение очереди вставляется в хвост очереди (конкретная позиция — это позиция заднего указателя [опять же: задний указатель указывает на позицию недопустимого элемента]
  3. задний указатель перемещается (снова указывает на недопустимую позицию элемента)

    /**
     * 入队
     *
     * @param queue
     */
    public static void enQueue(Queue queue,int value) {

        // 不是满的队列才能入队
        if (!isFull(queue)) {

            // 将新的元素插入到队尾中
            queue.arrays[queue.rear] = value;

            // rear节点移动到新的无效元素位置上
            queue.rear = (queue.rear + 1) % queue.arrays.length;
        }
    }

3.1.5 Обход

Пока передний узел не указывает на задний узел, он всегда может выводить


    /**
     * 遍历队列
     * @param queue
     *
     */
    public static void traverseQueue(Queue queue) {

        // front的位置
        int i = queue.front;

        while (i != queue.rear) {

            System.out.println("关注公众号：Java3y--->" + queue.arrays[i]);

            //移动front
            i = (i + 1) % queue.arrays.length;
        }

    }

Когда очередь не заполнена:

Если очередь заполнена, она не может быть вставлена ​​(проверьте правильность приведенного выше метода):

3.1.6 Определить, пуста ли очередь

если толькоrearиfrontУказатель указывает на то же место, тогда очередь пуста


    /**
     * 判断队列是否空，front和rear指针相等，就是空了
     * @param queue
     * @return
     */
    public static boolean isEmpty(Queue queue) {
        if (queue.rear  == queue.front) {
            System.out.println("关注公众号：Java3y--->此时队列空的！");
            return true;
        } else {
            System.out.println("关注公众号：Java3y--->此时队列非空！");
            return false;
        }
    }

3.1.7 Удаление из очереди

Логика удаления из очереди также очень проста:

  1. Проверить, является ли очередь нулевой
  2. Если не ноль, удалить из очереди,Пока передний указатель перемещается назад, он удаляется из очереди.!


 	/**
     * 出队
     *
     * @param queue
     */
    public static void outQueue(Queue queue) {

        //判断该队列是否为null
        if (!isEmpty(queue)) {


            //不为空才出队
            int value = queue.arrays[queue.front];
            System.out.println("关注公众号：Java3y--->出队的元素是：" + value);

            // front指针往后面移
            queue.front = (queue.front + 1) % queue.arrays.length;

        }


    }

результат:

4. Резюме

Существует множество применений стеков и очередей структур данных, это лишь самое простое введение, и понять его несложно.

  • стек: первый пришел, последний вышел
  • Очередь: первый пришел первый вышел

По поводу структуры данных пока остановлюсь здесь.Начать просто,и продолжу открывать новые статьи для написания,когда столкнусь с более сложными.Ведь уровня сейчас не хватает,и я не могу понять более глубокие вещи. Данные Структура обязательна, и я буду пересматривать ее, когда буду изучать коллекцию, или продолжу учиться, когда столкнусь с новыми и сложными. …

Студенты, которые хотят углубиться в структуру данных, должны читать соответствующие книги ~ Это только верхушка айсберга.

Если в статье есть какие-либо ошибки, пожалуйста, поправьте меня, и мы сможем общаться друг с другом. Учащиеся, привыкшие читать технические статьи в WeChat и желающие получить больше ресурсов по Java, могутОбратите внимание на публичный аккаунт WeChat: Java3y

Категории