java stacks and queues

Java #2 – Queue & Stack Implementation Tutorial – Linked List Programming Explained from Scratch

In this episode, we are looking at implementing java stacks and queues. These data structures are widely used and are likely to come up on an interview. It’s extremely important to know how to implement them in Java and how to properly use them. We will be walking through both data structures line by line. We will be leveraging our previous implementation of a LinkedList (Reference: Linked List Java Implementation) to serve as a base.

Java Stacks and Queues Walkthrough

Before we begin programming, it’s important to go over the theory of stacks and queues. As mentioned above, these classic concepts come up time and time again on interviews at top software companies such as Google, Yahoo, Apple & Microsoft. Any software engineer should be able to implement them on a white board and explain their functionality.

Stack Definition & Theory

A stack is a structure which is analogous to a deck of cards. Picture a box into which you can place one card on top of the other. Naturally, the first card will remain at the bottom as you add more on top. If you decide to remove a card, you can only remove the top one. The first card to be placed, will be the last one to be removed. This structure is thus called FILO or First In Last Out.

Java Queue Explanation

A queue is a FIFO, or First In First Out structure. It is analogous to a queue at a movie theater or fast food restaurant. In other words, whoever is first, will be serviced first.

Software / Hardware Used

Eclipse – Version: Neon Release (4.6.0) Build id: 20160613-1800
Java – Version: JavaSE-1.8
Computer – MacBook Pro (Retina, 15-inch, Mid 2015)

Stack Software Implementation

public class Stack {
private SinglyLinkedList list = new SinglyLinkedList<>();
public Stack() {}
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}

As mentioned above, our Stack will rely on the LinkedList class. The class thus starts with the creation of a new LinkedList. We then proceed with initializing a new size variable which holds the number of stacked nodes. The isEmpty() function will return true if our stack has nothing stored in it.

public void push(E element) {
list.addFirst(element);
}
public E pop() {
return list.removeFirst();
}
public E top() {
return list.first();
}

The stack class is known for two primary functions: push() and pop(). The first one allows the user to put a new element on top of the stack. The second one is responsible for removing the top element. Naturally, one may want to look at the top element without removing it. The top() function does exactly that.

Reversing a String with a Stack

String reversal is a common question on interview question. Naturally, one can really easily implement a solution by using a stack. If you have a moment, try to think how you could implement this yourself. The solution is provided below:

public String reverse(String myString) {
System.out.println("Initial String = " + myString);
String newString = "";
Stack myStack = new Stack<>();
for(int i = 0; i < myString.length(); i ++) { myStack.push(myString.substring(i, i+1)); } while(!myStack.isEmpty()){ newString += myStack.pop(); } System.out.println("Final String = " + newString); return newString; }

As you would think, as you stack and un-stack a string one character at a time, you'd get it reversed. The above function accomplishes exactly that. It has a time complexity of O(n) as it walks through the string one element at a time.

Queue Software Implementation

public class Queue {
private SinglyLinkedList list = new SinglyLinkedList<>();
public Queue(){}
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}
public void enqueue(E element) {
list.addLast(element);
}
public E dequeue() {
return list.removeFirst();
}
public E first() {
return list.first();
}
}

Although the Queue data structure contains slightly different functions, the principle is similar. As discussed previously, the only "conceptual" difference is the way elements are removed.

Conclusion

It's good to have these structures memorized for your next coding challenge or interview! Think of creative ways of how you would implement this in one of your projects and let us know in the comments below.

Link to FULL SOFTWARE: Click Here

Thank you for reading & watching,
- EEEnthusiast

Leave a Reply

Your email address will not be published.

CommentLuv badge