Ever wondered how the data within the database is managed? Or how it is available so easily on our command? This has been possible with the help of data structures. Data can be inserted, updated, arranged, rearranged, deleted, and retrieved efficiently, from the database with the help of data structures. They help organize the storage in a manner that it is highly accessible to be modified or simply retrieved.
Data structure helps in understanding the nature of the problem at a deeper level and thus providing a better understanding. They are used by programmers to solve an algorithm in an orderly and effective method. Wise choices of data structures lead to better performance of computer programs.
Data structures are used every day and everywhere by us. From storing possible moves in a game to storing our usual burger choices at the cafe, data structures are needed everywhere.
The data structures commonly used are Stack, Queue and Heap. They are the oldest data structures introduced in our computer and are both commonly used. Stack and Queue both allow us to linearly, dynamically store and retrieve data items in two very alternative ways while heap allows us to manage data hierarchically. It is important to understand their properties and how they differ from each other so as to be able to implement them appropriately.
Difference between Stack and Queue and Heap
| Stack | Queue | Heap |
| Linear data structure | Linear data structure | A non-linear data structure |
| Last-in first-out (LIFO) | First-in first-out (FIFO) | Elements in heap follow heap property |
| Insertion and deletion takes place from one end | Insertion and deletion in queues takes place from the opposite ends of the list | Binary tree structure where nodes are compared during insertion and deletion |
| Insert operation is called push operation. | Insert operation is called enqueue operation. | — |
| NO types of stacks |
|
|
| Delete operation is called pop operation. | Delete operation is called dequeue operation. | — |
| We maintain only one pointer | We maintain two pointers to access the list | No pointers are used |
| Memory is allocated in a continuous, sequential manner | Memory is allocated in a continuous, sequential manner | Memory is allocated in random order |
| Shortage of memory | Memory can be expanded | Memory fragmentation |
| Bounded capacity | Not necessarily bounded capacity | Can be resized |
| No wastage of memory space as only one pointer is used | There is wastage of memory space as two-pointer is used | Memory management is complex |
| Used in recursion and backtracking | Used in sequential algorithms | Useful for heapsort (best performance), selection algorithms |
What is stack?
A stack is a linear, dynamic data set which limits data in the way that it can only be added to or removed from the top. To explain in a simple way this data structure works like stacking books one on top of the other. The last book we put on the top is the one that is the first to be removed from the stack. This means it follows the last in first out principle (LIFO).
Only one end of the stack is accessible to us to perform operations on(ie. top). Thus one must use a stack when you want to get things out in the reverse order than you put them in. The lowest elements or the elements inserted at the very first are in the stack the longest.
Various functions, parsers, expression evaluations, recursive algorithms, or backtracking algorithms can be executed using this data structure. There are two basic operations performed on a stack i.e. PUSH and POP.
PUSH operations are often used to add items to a stack while the delete operation is understood as POP.
Along with these we can also use peek (to return the item at the top of the stack) and isEmpty (to check whether the stack contains items). Since the number of operations on a stack are limited it is considered to be a restricted data structure.
A stack can easily be implemented by an array or using a linked list.
What is queue?
The queue is an abstract data type that is a simple data structure which uses pointers to represent dynamic sets.
The items in a queue are removed from the list in the same order in which they were added to it. This means they follow the first in first out principle (FIFO). An example of this is when we stand in line for getting a bus ticket; here, the person who first enters the line is the first to leave the queue as well. Thus one must use a queue when you want to get things out in the order that you put them in.
When data is inserted into a queue it is called enqueue and when data is deleted from the queue it is called dequeue.
A queue can be used to implement cache, breadth-first search, or first come first serve (FCFS) algorithms. It can be implemented using an array or better, linked list.
What is heap?
Heap is a nonlinear data structure which means it hierarchically arranges data. It is a tree-based structure, which abides the fact that heap is always a complete binary tree in which all levels of the tree are full. It also follows the heap property which says all nodes are either greater than or equal to or less than or equal to each of its children. There are two types of heap namely min-heap (parent nodes are smaller than their child nodes) and max-heap (the parent nodes are greater than the child nodes).
Heap takes a lot of time to compute and memory management is complicated.
Author
Shriya Upasani
MIT World Peace University
