Overview of Stack

A stack is a data structure which stores elements one above others. Consider a pile of coins. Each coin is a data element. Addition and removal of coins take place at one end. This place is called the top of the stack. 

Image Credits:Pixelbay

A unique feature of this data structure is that we can use an array or linked list for its implementation. We are concerned about its functionality instead of it is implemented in code. Thus, the stack is an abstract data type. 

We use push operation for insertion and pop operation for deletion. 


Stack uses LIFO approach which is an acronym for, "Last in first out". The newer elements are the ones which get popped first.

There are two states which can be determined by the value of the top:

  1. Overflow- It means that the stack is full.
  2. Underflow- It means that the stack is empty.


Advantages of the stack are:

  1. Easy insertion and deletion of elements. 
  2. Provides LIFO functionality which is not given by array and linked list.


Disadvantages of the stack are:

  1. Elements cannot be randomly accessed.

Note: Advantages and disadvantages of data structure used for the implementation of the stack are reflected on the stack during program execution.


Application of stack are:

1. For checking parenthesis.

2. Evaluate arithmetic expressions.

3. For converting infix expression to postfix expression and vice versa.

4. For converting infix expression to prefix expression and vice versa.

5. Reversing a string.

6. Maintain function call order in memory.

7. Compilers use the stack to check if the syntax is correct.

8. Operating systems use the stack for memory management purposes.

8. Backtracking algorithm.

Comments

Post a Comment

Popular posts from this blog

Overview of Tree Data Structure

Image
The tree is an abstract data structure which stores hierarchical data. For example, organisations have a hierarchical structure for employees. It is similar to the image given below. Several sergeants have to report to their respective captain. Now captains report to colonel. This colonel takes order from the general and assigns them to sergeants. Each of these consists of several levels. The general is on level 0, Colonel A and Colonel V are on level 1, Captain A, B and C are on level 2 and so on. Another terminology is height of the tree.  The height of a tree is longest path from the root node to any leaf node of the tree. Height of leaf node n=Level of leaf n+1.  Suppose we want to find the height of Private A. Height of private A= Level of Private A+1                                       =4+1                                       =5 In terms of computer programming, the general would be the root node of the tree. Colonel A and Colonel B are children of general. These two colonels
Read more

Overview of Three Dimensional Array

Image
A multidimensional array is an array consisting of more than 2 dimensions.  We can perceive three dimensions at most. To visual 3-dimensional array, let's take an example of a cube. Therefore, the array is cube[3][3][3]. For better understanding, represent a 3-D array as a combination of 2-D arrays.  Note: The two-dimensional array must have the same size. To conclude, a three dimensional array has arr[sub-array number][row][column]. Application of 3-D array: To represent real-world location co-ordinates. For storing spatial data such as MRI data. 3-D modelling.
Read more

Overview of Priority Queue

Image
  Consider a group of patients waiting outside the doctor's cabin for consultation. The functioning of the clinic is First In First Out basis like a queue . Suddenly, a new patient arrives with a condition which requires immediate treatment.  Then, the doctor would treat this patient first and then continue treating other patients like the previous order. In a priority queue, each data element has priority. So that crucial data does not get stuck. High priority elements are dequeue before low priority elements. If multiple elements have the same priority number, then the deletion is on a first come first serve basis. When  array implements a priority queue, an additional  2-D array is required to store the priority. When a  linked list implements a priority queue, the node stores the priority number. Applications of priority queue: Bandwidth management. Dijkstra Algorithm. Huffman Coding. Best First Search Algorithm. CPU Scheduling
Read more