Stacks, Queues and Big O Notation

If you are familiar with programming languages, you may already know that there are multiple ways to solve a coding problem. However, one way is going to be more efficient than the other for each case, and as a developer, you got to know which data structures you are going to use and what are the pros and cons of choosing it. For a better understanding, we can start explaining what is a big notation and what are its classes.

What is a Big O notation?

Big O notation(“O” stands for “order”) is the language we use in Computer Science to describe the performance of an algorithm.

Here are three of the possibilities for the speed of an algorithm

• O(1): constant time (fastest)
• O(n): linear time, increases with the input n (medium fast)
• O(n²): Quadratic time, increases exponentially with input n (slowest, examples: nested iterations and loops)

Now that we are familiar with time complexity in programming language, we can dive into how Stacks and Queues work, differences between both of them, and their Big O notation.

Stacks

“Last-In/First-Out (LIFO) or First-In/Last-Out (FILO)”

First, we will talk about stacks. A Stack is a linear data structure that is very similar to a list because it stores items in an order, but you can only access to an item at the top. One example in the real world is when you press Command + Z and Command + Y on Mac or Control + Z and Control + Y on Microsoft to undo and redo something, in both cases you are only going to have access to the last change you have made. Another demonstration of a stack would be when you try to go backward or forward on the browser. Furthermore, a Stack is an abstract data type, but it could also be implemented using concrete data structures like Dynamic Arrays and Linked Lists.

“Spotify browser going back and forth”

Between all the methods a Stack has, the most important are:

• Peek: look at the top
• Pop: remove the item at the top
• Push: put an item on the stack

Below is the code for the methods of a Stack

“stack in a linked list”

“stack in an array”

Queues

First In/First Out (FIFO) or Last In/Last Out (LILO)

Unlike stacks, in a Queue, the last item to get in will be the last to get out and the first item that got in will be the first to get out. Some applications of a queue in the real world are scheduling systems, networking and handling congestion, multiplayer gaming, interview questions, music, etc. A Queue is an abstract data type, but it could also be implemented using concrete data structures like Dynamic Arrays and Linked Lists.

“John Travolta is the last in the queue of the hospital, thus he will the last to be called”

Between all the methods a Queue has, the most important are:

• Enqueue: add to the queue
• Dequeue: remove from the queue
• Front: look at the front of the queue

Below is the code for the methods of a Queue

“queue in a linked list”

“queue in an array”

Linked lists and Dynamic Arrays

To understand how the time complexity works in a Stack or Queue implementation with a Linked List and Dynamic Array, first, we need to know what are these last two, what do they have in common and their differences.

First, let’s define them. An Array is a data structure that stores values of the same data type and a Linked List is a sequence of data elements, which are connected together via links.

Second, let’s define what they have in common. They both are ordered, both implement methods: insert, append, prepend, read, and they are concrete Data Structures that can implement the ADT(abstract data type)/ Interface / Protocol.

And for the last one, we are going to explain what are their differences. An Array can access arbitrary address of the array in constant time — so it can find the middle element with binary search. In a Linked List, you can’t access the middle directly (you have to traverse from the beginning) so a binary search would not work.