STACK DATASTRUCTURES
What is it?
• A stack is a useful data structure in programming.
• It is just like a pile of plates kept on top of each
other.
• LIFO(Last In First Out) Data Structure
• Here, the element which is placed (inserted or
added) last, is accessed first
• In stack, insertion operation is called PUSH
operation and removal operation is
called POP operation
Stack
• Stack is an Abstract Data Type (ADT)
• Stack is an ordered list in which, insertion and
deletion can be performed only at one end that
is called top
• Real-world stack, for example – a deck of
cards or a pile of plates, etc
Think about the things you can do with
such a pile of plates
• Put a new plate on top
• Remove the top plate
• If you want the plate at the bottom, you have
to first remove all the plates on top.
• Such an arrangement is called Last In First
Out - the last item that was placed is the first
item to go out.
LIFO Principle of Stack
• In programming terms, putting an item on top
of the stack is called "push" and removing an
item is called "pop".
stack is an abstract data structure(ADT) that allows the following
operations:
• Push: Add an element to the top of a stack
• Pop: Remove an element from the top of a
stack
• IsEmpty: Check if the stack is empty
• IsFull: Check if the stack is full
Working of Stack Data Structure
The operations work as follows:
• A pointer called TOP is used to keep track of the top
element in the stack.
• When initializing the stack, we set its value to -1 so that
we can check if the stack is empty by comparing TOP
== -1.
• On pushing an element, we increase the value
of TOP and place the new element in the position
pointed to by TOP.
• On popping an element, we return the element
pointed to by TOP and reduce its value.
• Before pushing, we check if the stack is already full
• Before popping, we check if the stack is already empty
Stack Representation
• Array, Structure, Pointer, and Linked List
• Either fixed size memory or dynamic resizing
Push and Pop Operations
Stack Structure
Top position Status of stack
-1 Empty
0 Only one element in the stack
N-1 Stack is full
N Overflow
Basic Operations
• push() − Pushing (storing) an element on the
stack
• pop() − Removing (accessing) an element
from the stack
• isFull() − check if stack is full
• isEmpty() − check if stack is empty
• Top: Returns top element of stack
The top pointer provides top value of the stack
without actually removing it.
isfull()
bool isfull()
{
if(top == MAXSIZE)
return true;
else
return false;
}
isempty()
bool isempty()
{
if(top == -1)
return true;
else
return false;
}
Push Operation
• Process of putting a new data element onto stack is known as a Push
Operation
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 − Return success
Push Implementation
void push(int data)
{
if(!isFull())
{
top = top + 1;
stack[top] = data;
}
else
{
printf("Could not insert data, Stack is full\n");
}
}
Pop Operation
• Accessing the content while removing it from the stack, is known as
a Pop Operation.
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 − Return success
Pop Implementation
int pop(int data)
{
if(!isempty())
{
data = stack[top];
top = top - 1;
return data;
}
else
{
printf("Could not retrieve data, Stack is empty.\n");
}
}
// Stack implementation in C
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
int count = 0;
// Creating a stack
struct stack {
int items[MAX];
int top;
};
typedef struct stack st;
void createEmptyStack(st *s) {
s->top = -1;
}
// Check if the stack is full
int isfull(st *s) {
if (s->top == MAX - 1)
return 1;
else
return 0;
}
// Check if the stack is empty
int isempty(st *s) {
if (s->top == -1)
return 1;
else
return 0;
}
// Add elements into stack
void push(st *s, int newitem) {
if (isfull(s)) {
printf("STACK FULL");
} else {
s->top++;
s->items[s->top] = newitem;
}
count++;
}
// Remove element from stack
void pop(st *s) {
if (isempty(s)) {
printf("\n STACK EMPTY \n");
} else {
printf("Item popped= %d", s->items[s->top]);
s->top--;
}
count--;
printf("\n");
}
// Print elements of stack
void printStack(st *s) {
printf("Stack: ");
for (int i = 0; i < count; i++) {
printf("%d ", s->items[i]);
}
printf("\n");
}
int main() {
int ch;
st *s = (st *)malloc(sizeof(st));
createEmptyStack(s);
push(s, 1);
push(s, 2);
push(s, 3);
push(s, 4);
printStack(s);
pop(s);
printf("\nAfter popping out\n");
printStack(s);
Evaluating Arithmetic Expression
• Arithmetic expressions are mathematical
expressions that consist of operands
(numbers) and operators (+, -, *, /, etc.). To
evaluate such expressions using a computer
program, we often use stack data structures
due to their Last-In-First-Out (LIFO) property.
– Infix Expression
– Postfix Expression
– Prefix Expression
Operator Precedence
• Precedence determines the order in which
operators are evaluated in an expression
when there are multiple operators.
Precedence Level Operator(s) Description
Parentheses, array
1 (Highest) (), []
subscript
2 +, - (Unary) Unary plus, minus
Multiplication, division,
3 *, /, %
modulo
4 +, - (Binary) Addition, subtraction
5 (Lowest) =, +=, etc. Assignment operators
Operator Associativity
• Associativity determines the direction (left-to-
right or right-to-left) in which operators of
the same precedence are evaluated.
Operator(s) Associativity
+, -, *, / Left-to-right
=, +=, -= Right-to-left
Unary operators (-x) Right-to-left
Exponentiation ^ (if supported) Right-to-left
Associativity
Precedence
(Left-to-right
Operator Description (Highest/High/Mediu
Or
m/Low/Lowest)
Right-to-left)
() Parentheses
^ Exponentiation
*/% Multiplication, Div.
+- Addition, Subtraction
= Assignment
Associativity
Precedence
(Left-to-right
Operator Description (Highest/High/Medium/Lo
Or
w/Lowest)
Right-to-left
() Parentheses Highest Left-to-right
^ Exponentiation High Right-to-left
*/% Multiplication, Div. Medium Left-to-right
Addition,
+- Low Left-to-right
Subtraction
= Assignment Lowest Right-to-left
Example - Operator Associativity
• 100 / 10 * 2
• a=b=c=5
• 3 + 4 * 2 / (1 - 5) ^ 2 ^ 3
Example - Operator Associativity
• 100 / 10 * 2=20(Left to Right)
• a = b = c = 5 (Right to Left)
• 3 + 4 * 2 / (1 - 5) ^ 2 ^ 3
– Evaluation order:
– Parentheses (1 - 5) → -4
– Exponentiation (Right to Left): 2 ^ 3 = 8, then (-
4)^8
– Multiplication/Division (Left to Right)
– Addition
Arithmetic Expressions
• Infix form
– operand operator operand
• 2+3 or
• a+b
– Need precedence rules
– May use parentheses
• 4*(3+5) or
• a*(b+c)
Arithmetic Expressions
• Postfix form
– Operator appears after the
operands
• (4+3)*5 : 4 3 + 5 *
• 4+(3*5) : 4 3 5 * + Right to Left
– No precedence rules Left to Right
or parentheses!
• Input expression given in postfix
form
– How to evaluate it?
Prefix
• Operator, Operand & Operand
• 3+1
• +31
• A*B+C= + *AB C
Postfix
• Operand, Operand & Operator
• 5+1
• 51+
• A*B+C= AB*C+
Rules for the conversion from
infix to postfix expression
• Print the operand as they arrive.
• If the stack is empty or contains a left parenthesis on top, push the incoming
operator on to the stack.
• If the incoming symbol is '(', push it on to the stack.
• If the incoming symbol is ')', pop the stack and print the operators until the left
parenthesis is found.
• If the incoming symbol has higher precedence than the top of the stack, push
it on the stack.
• If the incoming symbol has lower precedence than the top of the stack, pop
and print the top of the stack. Then test the incoming operator against the
new top of the stack.
• If the incoming operator has the same precedence with the top of the stack
then use the associativity rules. If the associativity is from left to right(L-R)
then pop and print the top of the stack then push the incoming operator. If the
associativity is from right to left(R-L) then push the incoming operator.
• At the end of the expression, pop and print all the operators of the stack.
Example
• A+B/C
Stack Postfix expression
+ AB
/ AB
+
/ ABC
+
ABC/+
A-B/C*D+E
Stack Postfix expression Stack Postfix expression
A + ABC/D*-
- A
ABC/D*-E
- AB
/ AB ABC/D*-E+
-
/ ABC
-
* ABC/
-
* ABC/D
-
+ ABC/D*
-
Example
I. A/B$C+D*E/F-G+H
II. (A+B)*D+E/(F+G*D)+C
Evaluating Postfix Expressions
For solving a mathematical expression, we need prefix or postfix
form. After converting infix to postfix, we need postfix evaluation
algorithm to find the correct answer.
Here also we have to use the stack data structure to solve the postfix
expressions.
From the postfix expression,
• When some operands are found, pushed them in the stack.
• When some operator is found, two items are popped from the
stack and the operation is performed in correct sequence.
• After that, the result is also pushed in the stack for future use.
• After completing the whole expression, the final result is also
stored in the stack top.
• Input: Postfix expression: 53+62/*35*+
Step-by-Step Procedure:
Output: The result is: 39
[Link]
[Link] an empty stack
[Link] the postfix expression from left to right, one symbol
(token) at a time
[Link] the following for each token:
•If the token is an operand (number):
•Push it onto the stack
•If the token is an operator (+, -, *, /, ^):
•Pop the top two operands from the stack
•Let the first popped operand be operand2
•Let the second popped operand be operand1
•Perform the operation:
result = operand1 <operator> operand2
•Push the result back onto the stack
[Link] all tokens are processed:
•The remaining item on the stack is the final result
[Link] (or print) the result
Example
• Input
598+46**7+*
• Evaluation
push(5)
push(9)
push(8)
push(pop() + pop()) /* be careful for ‘-’ */
push(4)
push(6)
push(pop() * pop())
push(7)
push(pop() + pop())
push(pop() * pop())
print(pop())
• What is the answer?
Exercise
• Input
6523+8*+3+*
• Input
abc*+de*f+g*+
• For each of the previous inputs
– Find the infix expression
Infix to Postfix Conversion
• Observation
– Operands appear in the same order in both
– Output operands as we scan the input
– Must put operators somewhere
• use a stack to hold pending operators
– ‘)’ indicates both operands have been seen
• Will allow only +, *, ‘(‘, and ‘)’, and use
standard precedence rules
• Assume legal (valid) expression
Conversion Algorithm
• Output operands as encountered
• Stack left parentheses
• When ‘)’
– repeat
• pop stack, output symbol
– until ‘(‘
• ‘(‘ is poped but not output
• If symbol +, *, or ‘(‘
– pop stack until entry of lower priority or ‘(‘
• ‘(‘ removed only when matching ‘)’ is processed
– push symbol into stack
• At end of input, pop stack until empty
Exercises
• (5 * (((9 + 8) * (4 * 6)) + 7))
• 6 * (5 + (2 + 3) * 8 + 3)
• a + b * c + (d * e + f) * g
Linked list implementation of stack
• Instead of using array, we can also use linked list
to implement stack. Linked list allocates the
memory dynamically. However, time complexity
in both the scenario is same for all the operations
i.e. push, pop and peek.
• In linked list implementation of stack, the nodes
are maintained non-contiguously in the memory.
Each node contains a pointer to its immediate
successor node in the stack. Stack is said to be
overflown if the space left in the memory heap is
not enough to create a node.
Adding a node to the stack
(Push operation)
• Create a node first and allocate
memory to it.
• If the list is empty then the item is to
be pushed as the start node of the
list. This includes assigning value to
the data part of the node and assign
null to the address part of the node.
• If there are some nodes in the list
already, then we have to add the new
element in the beginning of the list
(to not violate the property of the
stack). For this purpose, assign the
address of the starting element to
the address field of the new node
and make the new node, the starting
node of the list.
Linked list implementation of stack
void push ()
{
int val;
struct node *ptr =(struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("not able to push the element");
}
else
{ void pop()
printf("Enter the value"); {
scanf("%d",&val); int item;
if(TOP==NULL) struct node *ptr;
{
if (head == NULL)
newnode->data = x;
{
printf("Underflow");
newnode->next = top;
}
top=newnode;
else
}
{
else
item = head->val;
{
ptr = head;
newnode->data = x;
head = head->next;
newnode->next = top;
free(ptr);
head=newnode;
printf("Item popped");
}
printf("Item pushed"); }
} }
}
Queue Data Structure
• A queue is a useful data structure in
programming.
• It is similar to the ticket queue outside a
cinema hall, where the first person entering
the queue is the first person who gets the
ticket.
• Queue follows the First In First Out(FIFO) rule
- the item that goes in first is the item that
comes out first too.
FIFO Representation of Queue
In programming terms, putting an item in the queue is called an
"enqueue" and removing an item from the queue is called "dequeue".
Basic Operations of Queue
• Enqueue: Add an element to the end of the
queue
• Dequeue: Remove an element from the front
of the queue
• IsEmpty: Check if the queue is empty
• IsFull: Check if the queue is full
Working of Queue
• two pointers FRONT and REAR
• FRONT track the first element of the queue
• REAR track the last elements of the queue
• initially, set value of FRONT and REAR to -1
Enqueue Operation
• check if the queue is full
• for the first element, set value of FRONT to 0
• increase the REAR index by 1
• add the new element in the position pointed
to by REAR
Dequeue Operation
• heck if the queue is empty
• return the value pointed by FRONT
• increase the FRONT index by 1
• for the last element, reset the values
of FRONT and REAR to -1
Question
• A hospital wants to maintain a real-time list of patients
currently waiting in the emergency room (ER). Patients
arrive continuously, and each patient is assigned a
severity level (an integer where a higher number
means more critical).
• The hospital wants to keep the list sorted in descending
order of severity so that the most critical patients are
always at the front of the list.
• Task:
– Implement a singly linked list to store patients in the ER.
– Each node contains the patient’s ID and severity level.
• #include <stdio.h>
• #include <stdlib.h>
• // Creates and returns a new patient node
with given ID and severity
• struct Patient* create_patient(int id, int
severity) {
• struct Patient* new_patient = (struct
Patient*)malloc(sizeof(struct Patient));
• new_patient->patient_id = id; // Assign patient ID
• new_patient->severity = severity; // Assign severity level
• new_patient->next = NULL; // Next is initially NULL
• return new_patient; // Return the new node
• }
• // Inserts a new patient into the list in descending severity order
• void insert_patient(struct Patient** head, int id, int severity) {
• struct Patient* new_patient = create_patient(id, severity); //
Create new node
if (*head == NULL || severity > (*head)->severity) {
new_patient->next = *head; // Insert at beginning
*head = new_patient;
return;
}
struct Patient* current = *head;
while (current->next != NULL && current->next->severity >=
severity) {
current = current->next; // Traverse to the correct position
}
new_patient->next = current->next; // Insert after current
current->next = new_patient;
}
// Displays the list of patients in order
void display_patients(struct Patient* head) {
if (head == NULL) {
printf("No patients in the list.\n");
return;
}
printf("\nPatients in ER (most critical first):\n");
struct Patient* current = head;
while (current != NULL) {
printf("Patient ID: %d, Severity: %d\n", current->patient_id, current-
>severity);
current = current->next; // Move to next node
}
}
• // Main function
• int main() {
• struct Patient* er_list = NULL; // Start with
empty list
• int choice;
do {
int id, severity;
printf("\nEnter Patient ID: ");
scanf("%d", &id); // Input patient ID
printf("Enter Severity (higher means more critical): ");
scanf("%d", &severity); // Input severity
insert_patient(&er_list, id, severity); // Insert into list
printf("Do you want to add another patient? (1=Yes, 0=No): ");
scanf("%d", &choice); // Ask to continue
} while (c
display_patients(er_list); // Show all patients
free_list(er_list); // Clean up memory
return 0; // End of program
}hoice != 0); // Repeat if user wants