In this article, we will give a brief introduction to Data Structure: Stacks and Queues. In this, we will also discuss the Stacks operations and Queue operations. And also, the difference between Stacks and Queues.
Let's begin..
Data Structure: Stacks
A Stack follows LIFO (Last In First Out) principle. When an element is added to the stack, it is added at the top of the stack and will be deleted from the stack from the same end. It means Stack has only one end. In other words, Insertion and Deletion are performed from one end only.
Stack Operations:
Stack is used for the following two basic operations:
Push(): Pushing an element on the stack.
Pop(): Removing an element out of the stack.
Push() Operation
The process of putting a new data element in the stack is known as a Push Operation. Push operation involves a series of steps −
Step 1 − Check if the stack is full.
Step 2 − If the stack is full, produces an error and exit.
Step 3 − If the stack is not full, increments top to point next empty space.
Step 4 − Adds the data element to the stack location, where the top is pointing.
Step 5 − Returns success.
Algorithm:
begin procedure push: stack, data
if stack is full
return null
endif
top ← top + 1
stack[top] ← data
end procedurePop() Operation
A Pop operation may involve the following steps −
Step 1 − Checks if the stack is empty.
Step 2 − If the stack is empty, produces an error and exit.
Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
Step 4 − Decreases the value of top by 1.
Step 5 − Returns success.
Algorithm
begin procedure pop: stack
if stack is empty
return null
endif
data ← stack[top]
top ← top - 1return data
end procedureTypes of Stack:
There are two types of stacks:
Register Stack
Memory Stack
1. Register Stack
The register stack is a memory device present in the memory unit, but it handles a small amount of data. The stack depth is always limited in the register stack because the size of the register stack s very small compared to the memory.
2. Memory Stack
In the memory stack, the stack depth is flexible. It occupies a large amount of memory data, whereas, in the register stack, only a finite number of memory words will be stored.
Data Structure: Queues
Queue follows FIFO (First In First Out) principle. The Queue has two ends: REAR and FRONT. An element is added to the queue from the REAR end and an element is deleted from the queue from the FRONT end. For example, people are waiting in line for a movie ticked.
Queue Operations:
Queue performs the following two operations:
Enqueue(): Add an element to the queue.
Dequeue(): Remove an element to the queue.
Enqueue() Operation
The following steps should be taken to enqueue (insert) data into a queue −
Step 1 − Check if the queue is full.
Step 2 − If the queue is full, produce overflow error and exit.
Step 3 − If the queue is not full, increment rear pointer to point the next empty space.
Step 4 − Add data element to the queue location, where the rear is pointing.
Step 5 − return success.
Algorithm
procedure enqueue(data)if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
end procedureDequeue() Operation
The following steps are taken to perform dequeue operation −
Step 1 − Check if the queue is empty.
Step 2 − If the queue is empty, produce underflow error and exit.
Step 3 − If the queue is not empty, access the data where front is pointing.
Step 4 − Increment front pointer to point to the next available data element.
Step 5 − Return success.
Algorithm
procedure dequeue
if queue is empty
return underflow
end if
data = queue[front]
front ← front + 1return true
end procedureTypes of Queue:
There are four different types of queues:
Simple Queue
Priority Queue
Circular Queue
Double Ended Queue
1. Simple Queue
In this type of queue, insertion (addition) takes place from the REAR end, and deletion (Removal) takes place from the FRON end.
2. Priority Queue
In this type of queue, an element is associated with a priority and served according to its priority hence it's called a priority queue. In this, insertion is based on the arrival but the removal of an element is based on their priority. If the elements have the same priority, they are served according to their order in the queue.
3. Circular Queue
In this type of queue, the last element points to the first element which makes a circle. It is better in memory utilization because in case the last position is full but the first position is empty, it will insert an element in the first position.
4. Double Ended Queue
In this type of queue, insertion and deletion of an element can be performed from both sides: REAR and FRONT. It neither follows FIFO nor LIFO principle.
The Difference:
Stack | Queue |
Stacks are based on the LIFO principle, i.e., the element inserted at the last, is the first element to come out of the list. | Queues are based on the FIFO principle, i.e., the element inserted at the first, is the first element to come out of the list. |
Insertion and deletion in stacks takes place only from one end of the list called the top. | Insertion and deletion in queues takes place from the opposite ends of the list. The insertion takes place at the rear of the list and the deletion takes place from the front of the list. |
Stack is used in solving problems works on recursion. | Queue is used in solving problems having sequential processing. |
Can be considered as a vertical collection visual. | Can be considered as a horizontal collection visual. |
In stacks we maintain only one pointer to access the list, called the top, which always points to the last element present in the list. | In queues we maintain two pointers to access the list. The front pointer always points to the first element inserted in the list and is still present, and the rear pointer always points to the last inserted element. |
Stack are of two types: 1. Register Stack and 2. Memory Stack | Queues are of three types: 1. Circular Queue 2. Priority Queue 3. Double-Ended Queue 4. Simple Queue |
The Tech Platform
Коментарі