Data Structures and Complexity Part 3: linear Data Structures Stacks and Queues.

stacks :

Definition :

a stack is a linear data structure that respects the principal of LIFO “Last In First Out” it means that the last element that was entered into the stack will be the first element to get out or the principal of FIFO “Fist In First Out”which means first in first out so the first element entered to the stack will be the first element that gets out, it’s used to model real world problems and it has tow main operations pop() which is used to get the first top element in the stack and push() which is used to add an element at the top of the stack along side with other operation like peek and ifEmpty that will discuss later.

Why we use stacks ?

Stacks are used to solve many problems since it mimics the behavior of many real world problems so it’s used as a model of those problems things like :

• the undo mechanism in the text editors .
• used in compilers in things like storing the recursive calls and in syntax checking.
• used to model a real world pile of anything(ex : books).
• used in DFS (Depth First Search) algorithm in graphs.
• used in so many algorithms because it can model a lot of real world problems.

How to implement a stack ?

Mainly there is two ways to implement a stack either you use arrays or linked lists and in our example we will use linked lists.

Note : this data structure is already implemented in most of the languages and the implementation sometimes is different from one language to another one , but for the sake of understanding the mechanism of it, we will implement it with it’s operation.

Stacks and Complexity :

The following operations push , pop, peek,isFull,isEmpty all has a O(1) time complexity cause they all depends on a simple instructions but if we want to do something like search an element that will take O(n) time complexity since we have to pull every element and put it back in order to loop over all the elements.

Solving a problem using stacks ( balanced brackets problem) :

In this part we will take a problem and try to solve it using the stack and as an example we are taking the famous balanced brackets problem where you need to check if the syntax and the closing of the parenthesis is correct or not in a group of parenthesis ex :

• {()} ==> correct.
• {()]} ==> false.
• {()[] ==> false.

Input : a string containing the parenthesis → Output : true or false.

Solution :

In order to solve it using stack what we could do is to add each parenthesis to the stack one by one and each time check if the stack is not empty if the first element in the stack is the right one in example if we are adding the ‘(‘ and the the first element in the stack is ‘)’ then we simply delete the first element from the stack but if not we add the element that we wanted to add and at the end of all the string that we are looping over it’s characters (parenthesis) we check if stack is empty then we return true else we return false that’s indicates that there is a syntax error.

Queues :

Definition :

A Queue is a linear data structure that models a real world queue with tow main operations dequeue and enqueue , the queue is similar to the stack but it has tow entry's for the operations one entry for enqueuing elements (from the end) and the other will be for dequeuing elements (from the front) so that the queue will follow the principal of FIFO (First In First Out) in a way that the first added element is the first accessed.

Why we use Queues ?

Queues can be used to model many real world problems like :

• waiting lines .
• request in web sites to know which client should be served.
• BFS (Breadth First Search) in graphs.
• keep track of the added elements.
• manage shared resources between some entities like CPU processes.
• asynchronous data transfer.

How to implement a Queue ?

As the stack the queue can be implemented using the arrays or the linked lists data structures , in our implementation we will use linked lists.

Note : this data structure is already implemented in most of the languages and the implementation sometimes is different from one language to another one , but for the sake of understanding the mechanism of it, we will implement it with it’s operation.

Queues and Complexity :

The basic operations of the queue like enqueue ,dequeue, peek and isEmpty will take O(1) time complexity but operations like contain (search) and remove an element from the middle will take O(n) time complexity since it’s required to dequeue all the element and enqueue then again.

Solving a Problem using Queues ( BFS algorithm) :

we will try to solve the BFS algorithm with queues (we will talk about tree data structure in the next’s articles)

Considering that we have a tree T we want to search for an element X using the BFS algorithm it means that we will go through the tree elements knowing that we go to through the breadth of each branch first.

Input : tree T , value X → Output : true / false (or you can return the value if it’s found and -1 else).

The steps will be the next :

• add the root of the tree to the queue and market as a discovered node or a visited node.
• loop over the queue elements and each time do :

1/ check if the dequeued element is equal to the value that we are searching for and if true return true .

2/ loop over the nodes that are in the same line as the node that we dequeued it means the adjacent nodes and for each node do :

1/ add the node to the queue and mark it as visited or discovered

• and at the end if the loop ended without returning a value that means that the value is not found and we must return false.

Note : in this solution the methods markeNode(),isMarked(), getAdjacentNodes() are methods for the tree structures that are used for : mark a node as visited, check if a node is visited or not, get the adjacent node of some node in a the tree.

Conclusion :

• stacks and Queues are so important in Data structures world and with no doubt they are a must know concepts for all programmers.
• some real world problems require some specific data structures that can model the real world problem into something can be manipulated by the programmer with the best experience in terms of complexity , so you should always seek to know different data structures and concept in order to have many perspectives and different views for the same problems and make your own data structure if it’s the best way.
• understanding the concept of the data structure is the key to know how to use in the best way.
• Hope you had a good reading and learned something from that and stay tuned for the next article about another Data structure .