Зміст курсу

Java Data Structures

Stack

A Stack is another data structure that operates on the Last In, First Out (LIFO) principle. The same principle can be applied to a Deque, which you learned about earlier, and Java developers recommend using Deque if there is a need for a data structure that operates on the LIFO principle. The Stack data structure is deprecated.

Deprecated

When an element is marked as deprecated, it means that the authors of the library or programming language advise avoiding its use in new code and recommend adopting new methods, classes, or approaches that may provide safer, more efficient, or more functional solutions.

An example is the Vector class in Java. Its methods have been deprecated in favor of more modern collections like ArrayList and LinkedList. If a programmer still uses Vector methods, the compiler may issue a warning that these methods are deprecated.

Example in Java:

main


              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));
    }
}

Therefore, it is not recommended to use a data structure like Stack, but we will discuss it in this chapter because it is an interesting data structure used, for example, in the Java Stack memory.

Stack

Straight to the point, let's look at the methods of the Stack class:

Methods

push(E element) (addition): Adds an element to the top of the stack:

main


              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);
    }
}

Adding is done the same way as in ArrayList, so let's immediately look at this method in combination with the pop() method:

pop(): Removes and returns the element from the top of the stack:

main


              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);
    }
}

This method removed one element from the top of the stack. Note that the pop() method removes the last added element from the stack. That's exactly how the LIFO principle works.

We can also see which element is at the top of the stack:

Peek: Returns the element from the top of the stack without removing it:

main


              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);
    }
}

With this method, we look at the top element in the stack.

Usage

Let's consider an example of using the stack data structure for navigating between pages in a browser (those forward and backward arrows that we frequently use).

Let's plan the implementation of the browser history and implement methods for two buttons (goBack() and goForward()). If you're not sure which buttons I'm referring to, I'm talking about these buttons:

Let's implement a class that has methods for operating these two buttons using the Stack data structure.

How it will work:

We will have two stacks and a String variable. The first stack will store the links we navigate by clicking the "back" arrow. The second stack will store the links we navigate by clicking the "forward" arrow. We will also have a String variable that stores the current page's link;
In this class, there will be four methods: visitPage(), goBack(), goForward(), and getCurrentPage(). Let's go through them step by step:
- The visitPage() method will redirect us to the URL specified in the parameter. When moving to a new page, the old link will be added to the backStack. The forwardStack will be cleared as we move to a new page.

Let's look at the implementation in the code:

BrowserHistory


              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);
    }
}

This way, we can return to the previous page when navigating to a new page. Let's implement the method for going back. It will work like this: we add the current link to the forwardStack, then remove this link from the backStack, and assign it to currentUrl. Let's look at the implementation in the code:

BrowserHistory


              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.");
    }
}

I'll remind you that the pop() method removes the element from the top of the stack and returns it. Therefore, using this method, we immediately assign the value of the URL to the variable currentUrl. We also check to ensure that the backStack is not empty; otherwise, we won't be able to go back to the previous link (simply because it won't be there). If the stack is empty, we output a corresponding message;
In the same manner, we implement the method for navigating to the forward page. We simply swap the elements in the stack:

BrowserHistory


              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.");
    }
}

Now, all that's left is to implement the getCurrentPage() method, which will simply return the value of currentUrl.

Testing

Next, let's test all of this in the main method. We'll use the visitPage() method three times to ensure these links are saved in the history. Then, we'll use the goBack() method twice, followed by the goForward() method once, to verify the functionality of the written methods.

During this process, we'll track our state using the getCurrentPage() method. You can run the code below and also try inserting more links and using different methods to test the functionality of this class:

Main


              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;
    }
}

Note
If the large number of console outputs is bothersome, you can remove the console print operations from the methods, leaving only intermediate screen outputs.

Remember that the Stack class is deprecated, and it's better to use Deque instead. In this example, Stack is implemented based on the LIFO principle, and we can also implement Deque since it is a double-ended queue that can operate based on both FIFO and LIFO principles.

If you encounter difficulties understanding the example or the code in general, feel free to click on "Unclear?" and ask your question. I'll do my best to help you understand the material as soon as possible!

Also, don't forget that you can take advantage of the "Chat With Community" feature, where users like you are ready to help you!

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

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