Зміст курсу
Java Data Structures
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
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
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
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
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 aString
variable that stores the current page's link; - In this class, there will be four methods:
visitPage()
,goBack()
,goForward()
, andgetCurrentPage()
. 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 thebackStack
. TheforwardStack
will be cleared as we move to a new page.
- The
Let's look at the implementation in the code:
BrowserHistory
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 thebackStack
, and assign it tocurrentUrl
. Let's look at the implementation in the code:
BrowserHistory
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 variablecurrentUrl
. We also check to ensure that thebackStack
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
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 ofcurrentUrl
.
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
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!
Дякуємо за ваш відгук!