!Stacks && Queues... Stacks || Queues!

Stacks and Queues

  Stacks and Queues are sometimes verbally used interchangeably or together with an "and" and do somewhat of a similar things. They hold a series of values or data, in which you can add or remove a value and the order of each cannot be rearranged. They are actually very different structures however and have vastly different real world applications, so let's find out what they are!

Stacks

  Stacks are a non-primitive data structure (or abstract data type) that have a few methods, .push() and .pop(), being the most used, but also have a .peek() to get the top element without removing it, .isFull() to check if it's full, and .isEmpty() to check if it's empty. Stacks work from the Last In First Out principle (LIFO), meaning the element that you .push() onto the stack is also the same element returned when you .pop() an item off. This can be seen in the diagram below:

This LIFO property is important for stacks and the largest difference between it and a queue which has a First In First Out property (FIFO). Imagine a stack like a pile of unorganized DVD's on the shelf when you are trying to watch a movie. To get to "Kindergarten Cop", which you haven't watched in years, you have to sift through all the other DVD's on top of it first. Another example would be, that you just bought and watched "Spider-man: Into the Spider-Verse" so you toss it on the top of the pile. Now tomorrow night when you want to watch it again, you don't have to sort through 150 scratched copies of 80's kung fu movies to get to it, you know it's right on top where you left it. Obviously this is a primitive example, so what are the real world applications when it comes to algorithms and programming?

Stack Creation

  First, to create a stack, we need a list of organized data and we always need reference to the item at the top of the stack (or the head if you will... bet you can guess where this is going). We can make a functional stack using a linked list! WOW! So meta... Using a linked list we can add elements to the head and remove them from the head at a constant time complexity (O₁) because we never need to iterate through the list, just update the pointer of the head. We can also add an instance variable for length so we never have to iterate for .isFull() or .isEmpty() either.

Stack algorithm

  A very simple example of an algorithm where you would use a stack for efficiency is reversing a string. After all elements are added to the stack, you simply pop them off and they come out in reverse order (LIFO).

public String reverseString(String str){
    //initialize a new stack
    Stack<Character> stack = new Stack<Character>();
    //iterate through the string adding each char to stack
    for(int i = 0; i < string.length; i++){
        stack.push(str.charAt(i));
    };
    //initialize a new reversed string
    String reversedString = new String;
    //now push each char onto a new string
    while(!stack.isEmpty()){
        reversedString = reversedString + stack.pop;
    };
    //return the reversed string
    return reversedString;
};

Here we don't have to create an Array, keep track of the end of it, or remember whether we are adding or grabbing characters from the right end of the array.

Queues

  Queues are the same ordered list of elements that a stack contains but the elements get pulled off the opposite end of that they are added. To visualize, a line of cars entering a tunnel come out of the tunnel in the same order (barring we are actually in a fast and the furious film):

Queues have two main functions as well but they are known as .enqueue() and .dequeue() instead of .push() and .pop() (because developers love making you type "q u e u e" to try and make you trip up) and also contain .peek() for seeing the element on the end of the queue, .isFull() and .isEmpty(). There are also different implementations of queues, including Priority Queue, Circular Queue, and Doubly Ended Queue. A priority queue is a queue where each element also has a "priority" value, and elements with a higher priority are served first. Circular Queue is where the tail or end of the Queue holds reference to the first element. Lastly a Doubly Ended Queue is a queue where elements can be both added and removed from either end of the queue.

Queue Creation

   Queues are a list of organized data where we need reference to the head to add items to the queue and the tail to remove items. Yup you guessed it, it is a doubly linked list! This means adding and removing elements is constant (O₁) because to add we push at the head and add a pointer to the rest of the list and removing from the tail removes the pointer to and from the element behind it.

Queue Algorithm

  There are a lot of uses for queues in computing and telecom and we use them every day in person, at say the supermarket, where the first person in line to check out, gets checked out first. But where can we use them in computer science and improving algos? They are very handy at improving the complexity of Binary Search Tree operations and traversal, but we will talk more about that next week! A more simple problem to utilize a queue is a function takes requests from users and serves information back in the correct order using a standard queue. Say you have a game and want to ensure that a user presses the buttons in the correct order, the clicks or keypresses can be logged in a queue and analyzed with maintained order!

Next week we will dive into the right time to use binary search trees!

references

https://techdifferences.com/difference-between-stack-and-queue.html