Unit-2

Stack
Basic Concept of Stack:

A Stack is a linear data structure that 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). LIFO implies that the element that is inserted last, comes out first
and FILO implies that the element that is inserted first, comes out last.

It behaves like a stack of plates, where the last plate added is the first one to
be removed. Think of it this way:

 Pushing an element onto the stack is like adding a new plate on top.
 Popping an element removes the top plate from the stack.
Stack Operations:

In order to make manipulations in a stack, there are certain operations

provided to us.

 push() to insert an element into the stack

 pop() to remove an element from the stack
 top() Returns the top element of the stack.
 isEmpty() returns true if stack is empty else false.
 isFull() returns true if the stack is full else false.

Push Operation on Stack (Adds an item to the stack)

If the stack is full, then it is said to be an Overflow condition.

Algorithm for Push Operation:

 Before pushing the element to the stack, we check if the stack is full .
 If the stack is full (top == capacity-1) , then Stack Overflows and we
cannot insert the element to the stack.
 Otherwise, we increment the value of top by 1 (top = top + 1) and the
new value is inserted at top position .
 The elements can be pushed into the stack till we reach the capacity of
the stack.

Pop Operation on Stack (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.

Algorithm for Pop Operation:

 Before popping the element from the stack, we check if the stack
is empty .
 If the stack is empty (top == -1), then Stack Underflows and we cannot
remove any element from the stack.
 Otherwise, we store the value at top, decrement the value of top by 1 (top
= top – 1) and return the stored top value.

Sample Code of Stack Operation:

#include <stdio.h>

#include <stdlib.h>

#define MAX 10 // Define maximum size of the stack

// Stack structure

struct Stack {

int arr[MAX];

int top;

};

// Function to initialize the stack

void initStack(struct Stack* stack) {

stack->top = -1; // Stack is initially empty

}
// Check if the stack is full

int isFull(struct Stack* stack) {

return stack->top == MAX - 1;

// Check if the stack is empty

int isEmpty(struct Stack* stack) {

return stack->top == -1;

// Push element onto the stack

void push(struct Stack* stack, int value) {

if (isFull(stack)) {

printf("Stack overflow! Cannot push %d\n", value);

} else {

stack->arr[++stack->top] = value;

printf("Pushed %d onto the stack.\n", value);

// Pop element from the stack

int pop(struct Stack* stack) {

if (isEmpty(stack)) {

printf("Stack underflow! Cannot pop.\n");

return -1;
 } else {

return stack->arr[stack->top--];

// Display the elements of the stack

void display(struct Stack* stack) {

if (isEmpty(stack)) {

printf("Stack is empty.\n");

} else {

printf("\nStack elements: ");

for (int i = 0; i <= stack->top; i++) {

printf("%d ", stack->arr[i]);

printf("\n");

// Main function to demonstrate the stack operations

int main() {

struct Stack stack;

initStack(&stack);

push(&stack, 10);

push(&stack, 20);
 push(&stack, 30);

push(&stack, 40);

display(&stack);

printf("\nPopped element: %d\n", pop(&stack));

display(&stack);

return 0;

Output:

Pushed 10 onto the stack.

Pushed 20 onto the stack.

Pushed 30 onto the stack.

Pushed 40 onto the stack.

Stack elements: 10 20 30 40

Popped element: 40

Stack elements: 10 20 30

Stack Applications:
Stacks have many practical applications in computer science, including in various
algorithms, problem-solving scenarios, and real-world systems.
1. Undo Mechanism in Applications

 In many applications, such as text editors (e.g., Microsoft Word), an undo

operation is essential. A stack is used to store previous states or actions (like
text entered, modified, or deleted).
 When the undo button is pressed, the last action is popped from the stack,
and the state is reverted to that point.

2. Balanced Parentheses/Brackets

 Syntax checking: Stacks are used to check for balanced parentheses, braces,
and brackets in expressions.
 For every opening symbol (like (, {, [), you push it onto the stack, and for
every closing symbol (), }, ]), you check whether it matches the symbol on
top of the stack.
 If the stack is empty or the symbols don’t match, the expression is not
balanced.

3. Backtracking Algorithms

 Stacks are useful in backtracking algorithms, where we try out possible

solutions and revert to previous decisions when necessary.

4. Checking Palindromes

 A palindrome is a string that reads the same forwards and backwards. A

stack can be used to check whether a string is a palindrome by comparing
the characters from the beginning and end of the string.

Conversion from Infix to Postfix/Prefix Notation using Stacks

In infix notation, operators are placed between operands (e.g., A + B).

In postfix notation (also called Reverse Polish Notation, RPN), operators are
placed after operands (e.g., A B +), and in prefix notation (Polish Notation),
operators are placed before operands (e.g., + A B).

These notations eliminate the need for parentheses to define the order of
operations, making them easier to evaluate using a stack.

Let's walk through the steps for converting infix expressions to postfix and prefix
using a stack data structure.

1. Infix to Postfix Conversion (using Stack)

The postfix notation is more convenient for computation because it eliminates the
need for parentheses to enforce precedence rules.

Rules for Conversion:

1. Operands (i.e., variables or numbers) are added directly to the result.

2. Left Parenthesis ( is pushed onto the stack to indicate the start of a sub-
expression.
3. Right Parenthesis ) causes the stack to pop operators and add them to the
result until a left parenthesis is encountered, which is discarded.
4. Operators (+, -, *, /, etc.) are pushed onto the stack, but before doing so,
pop higher or equal precedence operators from the stack to the result.

Operator Precedence:

 *, / have higher precedence than +, -.

 Operators with the same precedence are evaluated from left to right (except
for exponentiation, which is right to left).

Steps for Conversion:

1. Read the infix expression from left to right.

2. Use a stack to temporarily store operators and parentheses.
3. Output the final postfix expression.
Example:

Convert the infix expression A + B * C to postfix.

1. Start with an empty stack and an empty result.

2. Read A: It's an operand, so add it to the result → Result: A
3. Read +: It's an operator, so push it onto the stack → Stack: +
4. Read B: It's an operand, so add it to the result → Result: A B
5. Read *: It's an operator. Compare its precedence to +. Since * has higher
precedence, push it onto the stack → Stack: + *
6. Read C: It's an operand, so add it to the result → Result: A B C
7. End of expression: Pop all remaining operators from the stack and add them
to the result → Result: A B C * +

Final Postfix Expression: A B C * +

Algorithm (Infix to Postfix):

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX 20

char stk[20];
int top = -1;

int isEmpty()
{
return top == -1;
}
int isFull()
{
return top == MAX - 1;
}

char peek()
{
return stk[top];
}
char pop()
{
if(isEmpty())
return -1;

char ch = stk[top];
top--;
return(ch);
}

void push(char oper)

{
if(isFull())
printf("Stack Full!!!!");

else{
top++;
stk[top] = oper;
}
}

int checkIfOperand(char ch)

{
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}

int precedence(char ch)

{
switch (ch)
{
case '+':
case '-':
return 1;

case '*':
case '/':
return 2;

case '^':
return 3;
 }
return -1;
}

int covertInfixToPostfix(char* expression)

{
int i, j;

for (i = 0, j = -1; expression[i]; ++i)

{
if (checkIfOperand(expression[i]))
expression[++j] = expression[i];

else if (expression[i] == '(')

push(expression[i]);

else if (expression[i] == ')')

{
while (!isEmpty() && peek() != '(')
expression[++j] = pop();
if (!isEmpty() && peek() != '(')
return -1;
else
pop();
}
else
{
while (!isEmpty() && precedence(expression[i]) <= precedence(peek()))
expression[++j] = pop();
push(expression[i]);
}

while (!isEmpty())
expression[++j] = pop();

expression[++j] = '\0';
printf( "%s", expression);
}
int main()
{
//char expression[] = "((x+(y*z))-w)";
char expression[] = "(a+b)*c";
covertInfixToPostfix(expression);
return 0;
}

Output:

ab+c*

2. Infix to Prefix Conversion (using Stack)

Prefix notation (also called Polish notation) requires that operators precede their
operands. The conversion is similar to the postfix conversion, but the process is
reversed in terms of order.

Steps for Conversion:

1. Reverse the infix expression.

2. Convert the reversed expression to postfix using the same steps as the infix-
to-postfix conversion.
3. Reverse the resulting postfix expression to get the final prefix expression.

Example:

Convert the infix expression A + B * C to prefix.

1. Reverse the infix expression: C * B + A.

2. Now convert the reversed expression to postfix:
o Start with an empty stack and an empty result.
o Read C: It's an operand, so add it to the result → Result: C
o Read *: It's an operator, so push it onto the stack → Stack: *
o Read B: It's an operand, so add it to the result → Result: C B
o Read +: Compare the precedence of + and *. Since + has lower
precedence, pop * and add it to the result, then push + → Result:
C B *, Stack: +
 oRead A: It's an operand, so add it to the result → Result: C B *
A
3. End of expression: Pop all remaining operators from the stack →
Result: C B * A +
4. Reverse the result → + A * B C

Final Prefix Expression: + A * B C

Algorithm (Infix to Prefix):

def infix_to_prefix(expression):
expression = expression[::-1] # Reverse the
expression
expression = expression.replace('(', ')')
expression = expression.replace(')', '(')

postfix = infix_to_postfix(expression) # Convert

reversed expression to postfix
return postfix[::-1] # Reverse the result to get
prefix

Key Differences between Postfix and Prefix Conversions:

 Postfix: Operators appear after operands (e.g., A B +).

 Prefix: Operators appear before operands (e.g., + A B).