Push Operation
The PUSH operation is broken down into the following steps:
🚀 Before adding an element to a stack, we make sure it's not already full.
🚀 When we try to insert the element into a stack that is already full, we get an
overflow problem.
🚀 When we create a stack, we set the value of top to -1 to ensure that it is empty.
🚀 When a new element is added to a stack, the top value is first incremented
(top=top+1), and the element is then relocated to the new top position.
🚀 The items will be added to the stack until it reaches its maximum capacity.
STEP 1 START public void push(int x)
STEP 2 Store the element to push into array {
STEP 3 Check if top== (MAXSIZE-1) then stack is if (top >= (MAX - 1))
full else goto step 4 cout<<"Stack Overflow";
STEP 4 Increment top as top = top+1 else {
STEP 5 Add element to the position top++;
stk[top]=num a[top] = x;
STEP 6 STOP cout<<"Item pushed into stack = “<<x;
}
}
Pop Operation :
The steps involved in the POP procedure are as follows:
🚀 Before eliminating an element from the stack, we make sure it's empty.
🚀 We get an underflow problem when we try to remove an element from an
empty stack.
🚀 We start with the element pointed to by the top if the stack isn't empty.
🚀 After the pop operation, the top is decremented by one, i.e. top=top-1.
POP operation can be performed in the below int pop()
steps {
Step 1 − Checks stack has some element or stack if (top < 0) {
is empty. cout<<"Stack Underflow";
Step 2 − If the stack has no element means it is return 0;
empty then display “underflow” }
Step 3 − If the stack has element some element, else {
int x = a[top];
accesses the data element at which top is
top--;
pointing.
return x;
Step 4 − Decreases the value of top by 1.
}
Step 5 − POP operation performed successfully.
}
Application of Stack Data Structure:
• Function calls and recursion: When a function is called, the current state of the program is
pushed onto the stack. When the function returns, the state is popped from the stack to resume
the previous function’s execution.
• Undo/Redo operations: The undo-redo feature in various applications uses stacks to keep track
of the previous actions. Each time an action is performed, it is pushed onto the stack. To undo
the action, the top element of the stack is popped, and the reverse operation is performed.
• Expression evaluation: Stack data structure is used to evaluate expressions in infix, postfix, and
prefix notations. Operators and operands are pushed onto the stack, and operations are
performed based on the stack’s top elements.
Application of Stack Data Structure:
• Browser history: Web browsers use stacks to keep track of the web pages you visit. Each time
you visit a new page, the URL is pushed onto the stack, and when you hit the back button, the
previous URL is popped from the stack.
• Balanced Parentheses: Stack data structure is used to check if parentheses are balanced or not.
An opening parenthesis is pushed onto the stack, and a closing parenthesis is popped from the
stack. If the stack is empty at the end of the expression, the parentheses are balanced.
• Backtracking Algorithms: The backtracking algorithm uses stacks to keep track of the states of
the problem-solving process. The current state is pushed onto the stack, and when the algorithm
backtracks, the previous state is popped from the stack.
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)
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) )
Input : Prefix : *+AB-CD
Output : Infix : ((A+B)*(C-D))
Input : Prefix : *-A/BC-/AKL
Output : Infix : ((A-(B/C))*((A/K)-L))
Algorithm for Prefix to Infix:
• Read the Prefix expression in reverse order (from right to left)
• If the symbol is an operand, then push it onto the Stack
• If the symbol is an operator, then pop two operands from the Stack
• Create a string by concatenating the two operands and the operator between them.
string = (operand1 + operator + operand2)
• And push the resultant string back to Stack
• Repeat the above steps until the end of Prefix expression.
• At the end stack will have only 1 string i.e resultant string
STEP 1 START
STEP 2 Store the element to insert
STEP 3 Check if REAR= MAX-1 then write Overflow else goto step 6
STEP 4 Check if REAR= -1 then
set FRONT=REAR=0
else
set REAR=REAR+1
STEP 5 set QUEUE [REAR]=NUM
STEP 6 STOP
Advantages of Queue C++:
• It is used in applications in which data is transferred asynchronously between
two processes. The queue in C++ can be used for obtaining the
synchronization.
• The call center systems use queues to hold the incoming calls and to resolve
them one by one.
• The queues can handle the interrupts in a real-time system and are ideal for
disk scheduling and CPU scheduling.
void dequeue() {
STEP 1 START
if (isEmpty()) {
STEP 2 Store the element to insert
cout << "Error: Queue is empty" << endl;
STEP 3 Check if FRONT=-1 or FRONT > REAR
return;
writes Underflow else goto step 4 }
STEP 4 Set VAL=QUEUE [FRONT] if (front == rear) {
front = -1;
Set FRONT= FRONT + 1
rear = -1;
STEP 5 STOP
} else
front++; }
