Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Вивчайте Структура Даних Стек у Java | Просунуті Структури Даних у Java
Структури Даних Java

bookСтруктура Даних Стек у Java

Stack — це структура даних, яка працює за принципом останній прийшов — перший пішов (LIFO). Той самий принцип застосовується і до Deque, з яким ви вже ознайомилися раніше, і саме використання Deque рекомендується Java-розробниками, коли потрібна структура даних із принципом LIFO. Структура даних Stack є застарілою та не рекомендується для використання в сучасній розробці на Java.

Однак деякі колекції більше не рекомендуються та були позначені як застарілі.

Застаріле

Коли елемент позначено як застарілий, це означає, що автори бібліотеки або мови програмування радять уникати його використання у новому коді та рекомендують застосовувати нові методи, класи або підходи, які можуть бути безпечнішими, ефективнішими чи функціональнішими.

Прикладом є клас Vector у Java. Його методи були застарілими на користь сучасніших колекцій, таких як ArrayList та LinkedList. Якщо програміст все ще використовує методи Vector, компілятор може видати попередження про те, що ці методи застарілі.

Приклад на Java:

Main.java

Main.java

copy

              
12345678910111213141516

            
package com.example;

import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        Vector<String> vector = new Vector<>();

        // Adding an element (this method is deprecated)
        vector.addElement("Item");

        // Compiler warning about the deprecated method
        // Note: 'addElement(java.lang.Object)' is deprecated.
        System.out.println(vector.get(0));
    }
}

Тому не рекомендується використовувати таку структуру даних, як Stack, але ми розглянемо її в цьому розділі, оскільки це цікава структура даних, яка використовується, наприклад, у Java Stack memory.

Стек

Коротко і по суті, розглянемо методи класу Stack:

Методи

push(E element): додає елемент на вершину стека.

Main.java

Main.java

copy

              
123456789101112

            
package com.example;

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.push("One");
        stack.push("Two");
        System.out.println("Stack: " + stack);
    }
}

Додавання виконується так само, як і в ArrayList, тому одразу розглянемо цей метод у поєднанні з методом pop():

pop(): видаляє та повертає елемент з вершини стеку.

Main.java

Main.java

copy

              
1234567891011121314

            
package com.example;

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.push("One");
        stack.push("Two");
        System.out.println("Stack: " + stack);
        stack.pop();
        System.out.println("Stack after the `pop()` method: " + stack);
    }
}

Цей метод видаляє один елемент з вершини стеку. Зверніть увагу, що метод pop() видаляє останній доданий елемент зі стеку. Саме так працює принцип LIFO.

Також можна переглянути, який елемент знаходиться на вершині стеку:

peek(): повертає елемент з вершини стеку без його видалення.

Main.java

Main.java

copy

              
123456789101112131415

            
package com.example;

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.push("One");
        stack.push("Two");
        System.out.println("Stack: " + stack);
        String top = stack.peek();
        System.out.println("Top element of the stack: " + top);
        System.out.println("Stack after the `peek()` method: " + stack);
    }
}

За допомогою цього методу ми переглядаємо верхній елемент у стеку.

Використання

Розглянемо приклад використання структури даних Stack для навігації між сторінками у браузері (ті стрілки вперед і назад, які ви часто використовуєте).

Сплануємо реалізацію історії браузера та реалізуємо методи для двох кнопок (goBack() і goForward()). Якщо ви не впевнені, про які кнопки йдеться, маються на увазі ці кнопки навігації:

Реалізуємо клас, який містить методи для роботи з цими двома кнопками за допомогою структури даних Stack.

Як це працюватиме

Ви матимете дві стеки та змінну типу String. Перший стек буде зберігати посилання, за якими ви переходите, натискаючи стрілку "назад". Другий стек буде зберігати посилання, за якими ви переходите, натискаючи стрілку "вперед". Також буде змінна типу String, яка зберігає посилання поточної сторінки.

У цьому класі буде чотири методи: visitPage(), goBack(), goForward() та getCurrentPage(). Розглянемо їх по черзі.

Метод visitPage() буде перенаправляти на URL, вказаний у параметрі. При переході на нову сторінку старе посилання буде додано до backStack. Стек forwardStack очищується при переході на нову сторінку.

Розглянемо реалізацію в коді:

BrowserHistory.java

BrowserHistory.java

copy

              
1234567891011121314151617181920212223242526

            
import java.util.Stack;

public class BrowserHistory {
    private Stack<String> backStack;
    private Stack<String> forwardStack;
    private String currentUrl;

    public BrowserHistory() {
        backStack = new Stack<>();
        forwardStack = new Stack<>();
        currentUrl = "https://codefinity.com/profile/my-home";
    }

    public void visitPage(String url) {
        // When visiting a new page, add the current page to the "back" stack
        backStack.push(currentUrl);

        // Reset the "forward" stack as we moved to a new page
        forwardStack.clear();

        // Set the current page to the new URL
        currentUrl = url;

        System.out.println("Visited page: " + url);
    }
}

Таким чином, можна повернутися на попередню сторінку при переході на нову сторінку.

Реалізуємо метод для повернення назад. Він працюватиме так: ми додаємо поточне посилання до forwardStack, потім видаляємо це посилання з backStack і присвоюємо його змінній currentUrl.

Розглянемо реалізацію в коді:

BrowserHistory.java

BrowserHistory.java

copy

              
12345678910

            
public void goBack() {
    if (!backStack.isEmpty()) {
        // Navigate to the previous page, move from the backStack to the forwardStack
        forwardStack.push(currentUrl);
        currentUrl = backStack.pop();
        System.out.println("Went back to: " + currentUrl);
    } else {
        System.out.println("Cannot go back. Already at the beginning.");
    }
}

Нагадаю, що метод pop() видаляє елемент з вершини стеку та повертає його. Тому, використовуючи цей метод, ми одразу присвоюємо значення URL змінній currentUrl.

Також перевіряємо, що backStack не порожній; інакше ми не зможемо повернутися до попереднього посилання (оскільки його просто не буде). Якщо стек порожній, виводимо відповідне повідомлення.

Аналогічно реалізуємо метод для переходу вперед. Просто міняємо місцями елементи у стеці:

BrowserHistory.java

BrowserHistory.java

copy

              
12345678910

            
public void goForward() {
    if (!forwardStack.isEmpty()) {
        // Navigate to the next page, move from the forwardStack to the backStack
        backStack.push(currentUrl);
        currentUrl = forwardStack.pop();
        System.out.println("Went forward to: " + currentUrl);
    } else {
        System.out.println("Cannot go forward. Already at the latest page.");
    }
}

Тепер залишилося лише реалізувати метод getCurrentPage(), який просто повертатиме значення currentUrl.

Тестування

Далі перевіримо все це у методі main. Скористаємося методом visitPage() тричі, щоб переконатися, що ці посилання збережені в історії. Потім використаємо метод goBack() двічі, а після цього метод goForward() один раз, щоб перевірити працездатність написаних методів.

Під час цього процесу відстежуватимемо наш стан за допомогою методу getCurrentPage(). Ви можете запустити наведений нижче код, а також спробувати додати більше посилань і скористатися різними методами для тестування функціональності цього класу:

Main.java

Main.java

copy

              
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778

            
package com.example;

import java.util.Stack;

class Main {
    public static void main(String[] args) {
        BrowserHistory browser = new BrowserHistory();

        System.out.println("Default page: " + browser.getCurrentPage());

        browser.visitPage("https://codefinity.com/courses/tracks/7dfbcd35-5cde-49d3-80f1-bf1096487903");
        browser.visitPage("https://codefinity.com/courses/v2/8204075c-f832-4cb9-88b1-4e24e74ebdcb/bb00e195-715e-477d-8927-964e6e27cf16/e66c57b4-5f36-43b2-bd3b-e1398044fcab");
        browser.visitPage("https://codefinity.com/courses/v2/8204075c-f832-4cb9-88b1-4e24e74ebdcb/bb00e195-715e-477d-8927-964e6e27cf16/1585fb29-47cd-47a6-9fb3-5b391cad24e0");

        System.out.println("Current Page after visiting 3 pages: " + browser.getCurrentPage());

        browser.goBack();
        browser.goBack();

        System.out.println("Current Page after going back 2 times: " + browser.getCurrentPage());

        browser.goForward();

        System.out.println("Current Page after going forward: " + browser.getCurrentPage());
    }
}

class BrowserHistory {
    private Stack<String> backStack;
    private Stack<String> forwardStack;
    private String currentUrl;

    public BrowserHistory() {
        backStack = new Stack<>();
        forwardStack = new Stack<>();
        currentUrl = "https://codefinity.com/profile/my-home";
    }

    public void visitPage(String url) {
        // When visiting a new page, add the current page to the "back" stack
        backStack.push(currentUrl);

        // Reset the "forward" stack as we moved to a new page
        forwardStack.clear();

        // Set the current page to the new URL
        currentUrl = url;

        System.out.println("Visited page: " + url);
    }


    public void goBack() {
        if (!backStack.isEmpty()) {
            // Navigate to the previous page, move from the backStack to the forwardStack
            forwardStack.push(currentUrl);
            currentUrl = backStack.pop();
            System.out.println("Went back to: " + currentUrl);
        } else {
            System.out.println("Cannot go back. Already at the beginning.");
        }
    }

    public void goForward() {
        if (!forwardStack.isEmpty()) {
            // Navigate to the next page, move from the forwardStack to the backStack
            backStack.push(currentUrl);
            currentUrl = forwardStack.pop();
            System.out.println("Went forward to: " + currentUrl);
        } else {
            System.out.println("Cannot go forward. Already at the latest page.");
        }
    }

    public String getCurrentPage() {
        return currentUrl;
    }
}

Пам’ятайте, що клас Stack є застарілим і не рекомендується для використання у сучасній розробці на Java. Замість нього краще використовувати Deque, який є ефективнішою альтернативою. У цьому прикладі Stack реалізовано на основі принципу LIFO, а також можна реалізувати Deque, оскільки це черга з двома кінцями, яка підтримує як принцип FIFO, так і LIFO.

1. Який основний принцип структури даних Stack?

2. Який метод використовується для додавання елемента на вершину стеку в Java?

3. Яка з наступних колекцій Java вважається сучаснішою альтернативою Stack?

4. У Java, що повертає метод pop() класу Stack?

question mark

Який основний принцип структури даних Stack?

Select the correct answer

question mark

Який метод використовується для додавання елемента на вершину стеку в Java?

Select the correct answer

question mark

Яка з наступних колекцій Java вважається сучаснішою альтернативою Stack?

Select the correct answer

question mark

У Java, що повертає метод pop() класу Stack?

Select the correct answer

Все було зрозуміло?

Як ми можемо покращити це?

Дякуємо за ваш відгук!

Секція 2. Розділ 4

Запитати АІ

expand

Запитати АІ

ChatGPT

Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат

Suggested prompts:

What are the main differences between Stack and Deque in Java?

Can you show how to implement the same browser history example using Deque?

Why is Stack considered obsolete in Java?

bookСтруктура Даних Стек у Java

Свайпніть щоб показати меню

Stack — це структура даних, яка працює за принципом останній прийшов — перший пішов (LIFO). Той самий принцип застосовується і до Deque, з яким ви вже ознайомилися раніше, і саме використання Deque рекомендується Java-розробниками, коли потрібна структура даних із принципом LIFO. Структура даних Stack є застарілою та не рекомендується для використання в сучасній розробці на Java.

Однак деякі колекції більше не рекомендуються та були позначені як застарілі.

Застаріле

Коли елемент позначено як застарілий, це означає, що автори бібліотеки або мови програмування радять уникати його використання у новому коді та рекомендують застосовувати нові методи, класи або підходи, які можуть бути безпечнішими, ефективнішими чи функціональнішими.

Прикладом є клас Vector у Java. Його методи були застарілими на користь сучасніших колекцій, таких як ArrayList та LinkedList. Якщо програміст все ще використовує методи Vector, компілятор може видати попередження про те, що ці методи застарілі.

Приклад на Java:

Main.java

Main.java

copy

              
12345678910111213141516

            
package com.example;

import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        Vector<String> vector = new Vector<>();

        // Adding an element (this method is deprecated)
        vector.addElement("Item");

        // Compiler warning about the deprecated method
        // Note: 'addElement(java.lang.Object)' is deprecated.
        System.out.println(vector.get(0));
    }
}

Тому не рекомендується використовувати таку структуру даних, як Stack, але ми розглянемо її в цьому розділі, оскільки це цікава структура даних, яка використовується, наприклад, у Java Stack memory.

Стек

Коротко і по суті, розглянемо методи класу Stack:

Методи

push(E element): додає елемент на вершину стека.

Main.java

Main.java

copy

              
123456789101112

            
package com.example;

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.push("One");
        stack.push("Two");
        System.out.println("Stack: " + stack);
    }
}

Додавання виконується так само, як і в ArrayList, тому одразу розглянемо цей метод у поєднанні з методом pop():

pop(): видаляє та повертає елемент з вершини стеку.

Main.java

Main.java

copy

              
1234567891011121314

            
package com.example;

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.push("One");
        stack.push("Two");
        System.out.println("Stack: " + stack);
        stack.pop();
        System.out.println("Stack after the `pop()` method: " + stack);
    }
}

Цей метод видаляє один елемент з вершини стеку. Зверніть увагу, що метод pop() видаляє останній доданий елемент зі стеку. Саме так працює принцип LIFO.

Також можна переглянути, який елемент знаходиться на вершині стеку:

peek(): повертає елемент з вершини стеку без його видалення.

Main.java

Main.java

copy

              
123456789101112131415

            
package com.example;

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.push("One");
        stack.push("Two");
        System.out.println("Stack: " + stack);
        String top = stack.peek();
        System.out.println("Top element of the stack: " + top);
        System.out.println("Stack after the `peek()` method: " + stack);
    }
}

За допомогою цього методу ми переглядаємо верхній елемент у стеку.

Використання

Розглянемо приклад використання структури даних Stack для навігації між сторінками у браузері (ті стрілки вперед і назад, які ви часто використовуєте).

Сплануємо реалізацію історії браузера та реалізуємо методи для двох кнопок (goBack() і goForward()). Якщо ви не впевнені, про які кнопки йдеться, маються на увазі ці кнопки навігації:

Реалізуємо клас, який містить методи для роботи з цими двома кнопками за допомогою структури даних Stack.

Як це працюватиме

Ви матимете дві стеки та змінну типу String. Перший стек буде зберігати посилання, за якими ви переходите, натискаючи стрілку "назад". Другий стек буде зберігати посилання, за якими ви переходите, натискаючи стрілку "вперед". Також буде змінна типу String, яка зберігає посилання поточної сторінки.

У цьому класі буде чотири методи: visitPage(), goBack(), goForward() та getCurrentPage(). Розглянемо їх по черзі.

Метод visitPage() буде перенаправляти на URL, вказаний у параметрі. При переході на нову сторінку старе посилання буде додано до backStack. Стек forwardStack очищується при переході на нову сторінку.

Розглянемо реалізацію в коді:

BrowserHistory.java

BrowserHistory.java

copy

              
1234567891011121314151617181920212223242526

            
import java.util.Stack;

public class BrowserHistory {
    private Stack<String> backStack;
    private Stack<String> forwardStack;
    private String currentUrl;

    public BrowserHistory() {
        backStack = new Stack<>();
        forwardStack = new Stack<>();
        currentUrl = "https://codefinity.com/profile/my-home";
    }

    public void visitPage(String url) {
        // When visiting a new page, add the current page to the "back" stack
        backStack.push(currentUrl);

        // Reset the "forward" stack as we moved to a new page
        forwardStack.clear();

        // Set the current page to the new URL
        currentUrl = url;

        System.out.println("Visited page: " + url);
    }
}

Таким чином, можна повернутися на попередню сторінку при переході на нову сторінку.

Реалізуємо метод для повернення назад. Він працюватиме так: ми додаємо поточне посилання до forwardStack, потім видаляємо це посилання з backStack і присвоюємо його змінній currentUrl.

Розглянемо реалізацію в коді:

BrowserHistory.java

BrowserHistory.java

copy

              
12345678910

            
public void goBack() {
    if (!backStack.isEmpty()) {
        // Navigate to the previous page, move from the backStack to the forwardStack
        forwardStack.push(currentUrl);
        currentUrl = backStack.pop();
        System.out.println("Went back to: " + currentUrl);
    } else {
        System.out.println("Cannot go back. Already at the beginning.");
    }
}

Нагадаю, що метод pop() видаляє елемент з вершини стеку та повертає його. Тому, використовуючи цей метод, ми одразу присвоюємо значення URL змінній currentUrl.

Також перевіряємо, що backStack не порожній; інакше ми не зможемо повернутися до попереднього посилання (оскільки його просто не буде). Якщо стек порожній, виводимо відповідне повідомлення.

Аналогічно реалізуємо метод для переходу вперед. Просто міняємо місцями елементи у стеці:

BrowserHistory.java

BrowserHistory.java

copy

              
12345678910

            
public void goForward() {
    if (!forwardStack.isEmpty()) {
        // Navigate to the next page, move from the forwardStack to the backStack
        backStack.push(currentUrl);
        currentUrl = forwardStack.pop();
        System.out.println("Went forward to: " + currentUrl);
    } else {
        System.out.println("Cannot go forward. Already at the latest page.");
    }
}

Тепер залишилося лише реалізувати метод getCurrentPage(), який просто повертатиме значення currentUrl.

Тестування

Далі перевіримо все це у методі main. Скористаємося методом visitPage() тричі, щоб переконатися, що ці посилання збережені в історії. Потім використаємо метод goBack() двічі, а після цього метод goForward() один раз, щоб перевірити працездатність написаних методів.

Під час цього процесу відстежуватимемо наш стан за допомогою методу getCurrentPage(). Ви можете запустити наведений нижче код, а також спробувати додати більше посилань і скористатися різними методами для тестування функціональності цього класу:

Main.java

Main.java

copy

              
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778

            
package com.example;

import java.util.Stack;

class Main {
    public static void main(String[] args) {
        BrowserHistory browser = new BrowserHistory();

        System.out.println("Default page: " + browser.getCurrentPage());

        browser.visitPage("https://codefinity.com/courses/tracks/7dfbcd35-5cde-49d3-80f1-bf1096487903");
        browser.visitPage("https://codefinity.com/courses/v2/8204075c-f832-4cb9-88b1-4e24e74ebdcb/bb00e195-715e-477d-8927-964e6e27cf16/e66c57b4-5f36-43b2-bd3b-e1398044fcab");
        browser.visitPage("https://codefinity.com/courses/v2/8204075c-f832-4cb9-88b1-4e24e74ebdcb/bb00e195-715e-477d-8927-964e6e27cf16/1585fb29-47cd-47a6-9fb3-5b391cad24e0");

        System.out.println("Current Page after visiting 3 pages: " + browser.getCurrentPage());

        browser.goBack();
        browser.goBack();

        System.out.println("Current Page after going back 2 times: " + browser.getCurrentPage());

        browser.goForward();

        System.out.println("Current Page after going forward: " + browser.getCurrentPage());
    }
}

class BrowserHistory {
    private Stack<String> backStack;
    private Stack<String> forwardStack;
    private String currentUrl;

    public BrowserHistory() {
        backStack = new Stack<>();
        forwardStack = new Stack<>();
        currentUrl = "https://codefinity.com/profile/my-home";
    }

    public void visitPage(String url) {
        // When visiting a new page, add the current page to the "back" stack
        backStack.push(currentUrl);

        // Reset the "forward" stack as we moved to a new page
        forwardStack.clear();

        // Set the current page to the new URL
        currentUrl = url;

        System.out.println("Visited page: " + url);
    }


    public void goBack() {
        if (!backStack.isEmpty()) {
            // Navigate to the previous page, move from the backStack to the forwardStack
            forwardStack.push(currentUrl);
            currentUrl = backStack.pop();
            System.out.println("Went back to: " + currentUrl);
        } else {
            System.out.println("Cannot go back. Already at the beginning.");
        }
    }

    public void goForward() {
        if (!forwardStack.isEmpty()) {
            // Navigate to the next page, move from the forwardStack to the backStack
            backStack.push(currentUrl);
            currentUrl = forwardStack.pop();
            System.out.println("Went forward to: " + currentUrl);
        } else {
            System.out.println("Cannot go forward. Already at the latest page.");
        }
    }

    public String getCurrentPage() {
        return currentUrl;
    }
}

Пам’ятайте, що клас Stack є застарілим і не рекомендується для використання у сучасній розробці на Java. Замість нього краще використовувати Deque, який є ефективнішою альтернативою. У цьому прикладі Stack реалізовано на основі принципу LIFO, а також можна реалізувати Deque, оскільки це черга з двома кінцями, яка підтримує як принцип FIFO, так і LIFO.

1. Який основний принцип структури даних Stack?

2. Який метод використовується для додавання елемента на вершину стеку в Java?

3. Яка з наступних колекцій Java вважається сучаснішою альтернативою Stack?

4. У Java, що повертає метод pop() класу Stack?

question mark

Який основний принцип структури даних Stack?

Select the correct answer

question mark

Який метод використовується для додавання елемента на вершину стеку в Java?

Select the correct answer

question mark

Яка з наступних колекцій Java вважається сучаснішою альтернативою Stack?

Select the correct answer

question mark

У Java, що повертає метод pop() класу Stack?

Select the correct answer

Все було зрозуміло?

Як ми можемо покращити це?

Дякуємо за ваш відгук!

Секція 2. Розділ 4
some-alt