STACKS
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).
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.
Push operation involves a series of steps −
Step 1 − Checks 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 data element to the stack location, where 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 procedure
Example:
void push(int data) {
if(!isFull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}
POP:Accessing the content while removing it from the stack, is known as a Pop 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 - 1
return data
end procedure
Example:
int pop(int data) {
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
}
PEEK OR TOP: Returns top element of stack.
IS EMPTY: Returns true if stack is empty, else false.
isFull() − check if stack is full.
Implementation:
There are two ways to implement a stack:
1)Using array
2)Using linked list
Applications:
▪︎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
QUEUE:
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).
Types of Queues.
1)Simple queue
2)priority queue
3)Double ended queue
4)Circular queue
Basic Operations:
1)enqueue() − add (store) an item to the queue.
Algorithm:
procedure enqueue(data)
if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
end procedure
Example:
int enqueue(int data)
if(isfull())
return 0;
rear = rear + 1;
queue[rear] = data;
return 1;
end procedure
dequeue() − remove (access) an item from the queue.
Algorithm:
procedure dequeue
if queue is empty
return underflow
end if
data = queue[front]
front ← front + 1
return true
end procedure
Example:
int dequeue() {
if(isempty())
return 0;
int data = queue[front];
front = front + 1;
return data;
}
Few more functions are required to make the above-mentioned queue operation efficient. These are −
peek() − Gets the element at the front of the queue without removing it.
isfull() − Checks if the queue is full.
isempty() − Checks if the queue is empty.
Applications:
▪︎CPU scheduling, Disk Scheduling
▪︎When data is transferred asynchronously between two processes.The queue is used for synchronization. eg: IO Buffers, pipes, file IO, etc
▪︎Handling of interrupts in real-time systems.
▪︎Call Center phone systems use Queues to hold people calling them in an order.
