Stack and Queue in Data Structures
Stack Data Structure
What is Stack?
Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).There are many real-life examples of a stack. Consider an example of plates stacked over one another in the canteen. The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO(Last In First Out)/FILO(First In Last Out) order.
Stack Concept
Stack
is an important data structure which stores its elements in an ordered manner.
Analogy:
You must have seen a pile of plates where one
plate is placed on top of another. When you
want to remove a plate, you remove
the topmost plate first. Hence, you can add and
remove an element (i.e. the
plate) only at/from one position which is the topmost position.
Mainly the following three basic operations are performed in the stack:
- Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.
- Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.
- Peek or Top: Returns top element of stack.
- isEmpty: Returns true if stack is empty, else false.
- Balancing of symbols
- Infix to Postfix /Prefix conversion
- Redo-undo features at many places like editors, photoshop.
- Forward and backward feature in web browsers
- Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem.
- Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and sudoku solver.
- In Graph Algorithms like Topological Sorting and Strongly Connected Components.
Implementation:
There are two ways to implement a stack:
There are two ways to implement a stack:
- Using array
- Using linked list
Array Representation
- Stack has two variables:
-> TOP
which is used to store the address of the topmost element of the stack
-> MAX
which is used to store the maximum number of elements that the stack can hold
- If TOP = NULL, then indicates that
the stack is empty
- If TOP = MAX – 1, then the stack is
full
- TOP=4, insertion and deletion will
be done at this position
Linked List Representation
- Technique
of creating a stack using array is easier, but the drawback is that the array
must be declared to have some fixed size.
- In
a linked stack, every node has two parts:
-> One
that stores data
-> One
that stores the address of the next node
- The
START pointer of the linked list is used as TOP
- All
insertions and deletions are done at the node pointed by the TOP
- If
TOP = NULL, then it indicates that the stack is empty
Prefix : An expression is called the prefix expression if the operator appears in the expression before the operands. Simply of the form (operator operand1 operand2).
Example : *+AB-CD (Infix : (A+B) * (C-D) )
Example : *+AB-CD (Infix : (A+B) * (C-D) )
Postfix: An expression is called the postfix expression if the operator appears in the expression after the operands. Simply of the form (operand1 operand2 operator).
Example : AB+CD-* (Infix : (A+B * (C-D) )
Example : AB+CD-* (Infix : (A+B * (C-D) )
Infix : An expression is called the Infix expression if the operator appears in between the operands in the expression. Simply of the form (operand1 operator operand2).
Example : (A+B) * (C-D)
Example : (A+B) * (C-D)
Queue Data Structure
A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.
Operations on Queue:
Mainly the following four basic operations are performed on queue:
Mainly the following four basic operations are performed on queue:
Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
Front: Get the front item from queue.
Rear: Get the last item from queue.
Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
Front: Get the front item from queue.
Rear: Get the last item from queue.
Applications of Queue:
Queue is used when things don’t have to be processed immediatly, but have to be processed in First InFirst Out order like Breadth First Search. This property of Queue makes it also useful in following kind of scenarios.
Queue is used when things don’t have to be processed immediatly, but have to be processed in First InFirst Out order like Breadth First Search. This property of Queue makes it also useful in following kind of scenarios.
1) When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
2) When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.
2) When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.
Array implementation Of Queue
For implementing queue, we need to keep track of two indices, front and rear. We enqueue an item at the rear and dequeue an item from front. If we simply increment front and rear indices, then there may be problems, front may reach end of the array. The solution to this problem is to increase front and rear in circular manner.
Circular Queue
Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called ‘Ring Buffer’.
Operations on Circular Queue:
- Front: Get the front item from queue.
- Rear: Get the last item from queue.
- enQueue(value) This function is used to insert an element into the circular queue. In a circular queue, the new element is always inserted at Rear position.
- Steps:
- Check whether queue is Full – Check ((rear == SIZE-1 && front == 0) || (rear == front-1)).
- If it is full then display Queue is full. If queue is not full then, check if (rear == SIZE – 1 && front != 0) if it is true then set rear=0 and insert element.
- deQueue() This function is used to delete an element from the circular queue. In a circular queue, the element is always deleted from front position.
- Steps:
- Check whether queue is Empty means check (front==-1).
- If it is empty then display Queue is empty. If queue is not empty then step 3
- Check if (front==rear) if it is true then set front=rear= -1 else check if (front==size-1), if it is true then set front=0 and return the element.
Deque
Deque or Double Ended Queue is a generalized version of Queue data structure that allows insert and delete at both ends.
Operations on Deque:
Mainly the following four basic operations are performed on queue:
Mainly the following four basic operations are performed on queue:
insertFront(): Adds an item at the front of Deque.
insertLast(): Adds an item at the rear of Deque.
deleteFront(): Deletes an item from front of Deque.
deleteLast(): Deletes an item from rear of Deque.
insertLast(): Adds an item at the rear of Deque.
deleteFront(): Deletes an item from front of Deque.
deleteLast(): Deletes an item from rear of Deque.
Applications of Deque:
Since Deque supports both stack and queue operations, it can be used as both. The Deque data structure supports clockwise and anticlockwise rotations in O(1) time which can be useful in certain applications.
Also, the problems where elements need to be removed and or added both ends can be efficiently solved using Deque. For example see Maximum of all subarrays of size k problem., 0-1 BFS and Find the first circular tour that visits all petrol pumps.
Since Deque supports both stack and queue operations, it can be used as both. The Deque data structure supports clockwise and anticlockwise rotations in O(1) time which can be useful in certain applications.
Also, the problems where elements need to be removed and or added both ends can be efficiently solved using Deque. For example see Maximum of all subarrays of size k problem., 0-1 BFS and Find the first circular tour that visits all petrol pumps.
Implementation:
A Deque can be implemented either using a doubly linked list or circular array. In both implementation, we can implement all operations in O(1) time. We will soon be discussing C/C++ implementation of Deque Data structure.
A Deque can be implemented either using a doubly linked list or circular array. In both implementation, we can implement all operations in O(1) time. We will soon be discussing C/C++ implementation of Deque Data structure.
Priority Queue
Priority Queue is an extension of queue with following properties.
- Every item has a priority associated with it.
- An element with high priority is dequeued before an element with low priority.
- If two elements have the same priority, they are served according to their order in the queue.
In the below priority queue, element with maximum ASCII value will have the highest priority.
A typical priority queue supports following operations.
insert(item, priority): Inserts an item with given priority.
getHighestPriority(): Returns the highest priority item.
deleteHighestPriority(): Removes the highest priority item.
insert(item, priority): Inserts an item with given priority.
getHighestPriority(): Returns the highest priority item.
deleteHighestPriority(): Removes the highest priority item.
How to implement priority queue?
Using Array: A simple implementation is to use array of following structure.
Using Array: A simple implementation is to use array of following structure.
struct item {
int item;
int priority;
}
insert() operation can be implemented by adding an item at end of array in O(1) time.
getHighestPriority() operation can be implemented by linearly searching the highest priority item in array. This operation takes O(n) time.
deleteHighestPriority() operation can be implemented by first linearly searching an item, then removing the item by moving all subsequent items one position back.
We can also use Linked List, time complexity of all operations with linked list remains same as array. The advantage with linked list is deleteHighestPriority() can be more efficient as we don’t have to move items.
Using Heaps:
Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked list. In a Binary Heap, getHighestPriority() can be implemented in O(1) time, insert() can be implemented in O(Logn) time and deleteHighestPriority() can also be implemented in O(Logn) time.
With Fibonacci heap, insert() and getHighestPriority() can be implemented in O(1) amortized time and deleteHighestPriority() can be implemented in O(Logn) amortized time.
Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked list. In a Binary Heap, getHighestPriority() can be implemented in O(1) time, insert() can be implemented in O(Logn) time and deleteHighestPriority() can also be implemented in O(Logn) time.
With Fibonacci heap, insert() and getHighestPriority() can be implemented in O(1) amortized time and deleteHighestPriority() can be implemented in O(Logn) amortized time.
Applications of Priority Queue:
1) CPU Scheduling
2) Graph algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree, etc
3) All queue applications where priority is involved.
1) CPU Scheduling
2) Graph algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree, etc
3) All queue applications where priority is involved.
Breadth First Search
Breadth First Traversal (or Search) for a graph is similar to Breadth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array. For simplicity, it is assumed that all vertices are reachable from the starting vertex.
For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. A Breadth First Traversal of the following graph is 2, 0, 3, 1.
For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. A Breadth First Traversal of the following graph is 2, 0, 3, 1.
Depth First Search
Depth
First Search (DFS)
is an algorithm for traversing or
searching in a
tree or graph. We start at the root of the tree (or some arbitrary node in graph) and explore as
far as possible along each branch before backtracking.
DFS
has many applications, such as :
- Finding
articulation point and bridge in a graph
- Finding
connected component
- Topological
sorting
- etc.
Source :
https://www.geeksforgeeks.org/stack-data-structure-introduction-program/
https://binusmaya.ac.id
https://www.geeksforgeeks.org/priority-queue-set-1-introduction/
https://www.geeksforgeeks.org/queue-data-structure/#implementation
https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
Comments
Post a Comment