UNIT-2

Stacks: Abstract Data Type, Primitive Stack operations: Push & Pop, Array and
Linked Implementation of Stack in C, Application of stack: Prefix and Postfix
Expressions, Evaluation of postfix expression, Iteration and Recursion-
Principles of recursion, Tail recursion, Removal of recursion Problem solving
using iteration and recursion with examples such as binary search, Fibonacci
numbers, and Hanoi towers. Tradeoffs between iteration and recursion.
Queues: Operations on Queue: Create, Add, Delete, Full and Empty, Circular
queues, Array and linked implementation of queues in C, Dequeue and
Priority Queue.

STACK
Stack is a linear data structure that follows LIFO (Last In First Out) Principle,
the last element inserted is the first to pop out. It means both insertion and
deletion operations happen at one end only.
LIFO(Last In First Out) Principle
The LIFO principle means that the last element added to a stack is the first
one to be removed.
• New elements are always pushed on top.
• Removal (pop) also happens only from the top.
• This ensures a strict order: last in → first out.
Real-world examples of LIFO:
• Stack of plates – The last plate placed on top is the first one you pick
up.
• Shuttlecock box – The last shuttlecock inserted is the first one taken
out, since both operations happen from the same end.

Basic Terminologies of Stack

• Top: The position of the most recently inserted element. Insertions
(push) and deletions (pop) are always performed at the top.
• Size: Refers to the current number of elements present in the stack.
Types of Stack:

1. Fixed Size Stack

• A fixed size stack has a predefined capacity.
• Once it becomes full, no more elements can be added (this causes
overflow).
• If the stack is empty and we try to remove an element, it causes
underflow.
• Typically implemented using a static array.

Example: Declaring a stack of size 10 using an array.

 2. Dynamic Size Stack
• A dynamic size stack can grow and shrink automatically as needed.
• If the stack is full, its capacity expands to allow more elements.
• As elements are removed, memory usage can shrink as well.
• Can be implemented using:
-> Linked List → grows/shrinks naturally.
-> Dynamic Array (like vector in C++ or ArrayList in Java) → resizes
automatically.
Example: Stack implementation using linked list or resizable array.

Note: We generally use dynamic stacks in practice, as they can grow or

shrink as needed without overflow issues.

Common Operations on Stack:

• 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.
 • size() returns the size of the stack.

Implementation of Stack
Stack can be implemented in Different Ways :-
• Implementation of Stack using Array
• Implementation of Stack using Linked List
 1. Implementation of Stack using Array

Declaration of Stack using Array

A stack can be implemented using an array where we maintain:
• An integer array to store elements.
• A variable capacity to represent the maximum size of the stack.
• A variable top to track the index of the top element. Initially, top = -1 to
indicate an empty stack.

Operations On Stack
Push Operation:
Adds an item to the stack. If the stack is full, then it is said to be an Overflow
condition.
• 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.
 CODE
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is full*/

int isfull()
{ if(top == MAXSIZE)
return 1;
else
return 0;
}

/* Function to insert into the stack */

void push(int data)
{ if(isfull())
printf("Could not insert data, Stack is full.\n");
else
{
top = top + 1;
stack[top] = data;
}
}
int main()
{ int i;
 push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements: \n");
// print stack data
for(i = 0; i < 8; i++)
{
printf("%d ", stack[i]);
}
return 0;
}

OUTPUT:
Stack Elements:
44 10 62 123 15 0 0 0
Time Complexity: O(1)
Pop Operation:
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.
• 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.
/* Check if the stack is empty */
int isempty()
{ if(top == -1)
return 1;
else
return 0;
}

/* Function to delete from the stack */

int pop()
{ int data;
if(isempty())
{
printf("Could not retrieve data, Stack is empty.\n");
return –1;
}
else
{
data = stack[top];
top = top - 1;
return data;
}
}

Inside main function

printf("\nElements popped: \n");
// print stack data
while(!isempty())
{
int data = pop();
printf("%d ",data);
}
OUTPUT:
Stack Elements:
44 10 62 123 15 0 0 0
Elements popped:
15 123 62 10 44

Time Complexity: O(1)

Retrieving topmost Element from Stack: peek()

Returns the top element of the stack.

• Before returning the top element from the stack, we check if the stack
is empty.
• If the stack is empty (top == -1), we simply print “Stack is empty”.
• Otherwise, we return the element stored at index = top.

/* Function to return the topmost element in the stack */

int peek()
{
return stack[top];
}
 2. Implementation of Stack using Linked List

Stack can be implemented using a linked list, where each element of

the stack is represented as a node. The head of the linked list acts as
the top of the stack.

Declaration of Stack using Linked List

A stack can be implemented using a linked list where we maintain:
• A Node structure that contains:
data → to store the element.
next → pointer/reference to the next node in the stack.
• A pointer top that always points to the current top node of the stack.
Initially, top = null to represent an empty stack.

#include <stdio.h>
#include <stdlib.h>
// Define a node structure
struct Node {
int data;
 struct Node* next;
};
// Top pointer for the stack
struct Node* top = NULL;

// Function to check if the stack is empty

int isEmpty()
{
return top == NULL;
}

Push Operation

Adds an item to the stack. Unlike array implementation, there is no fixed

capacity in linked list. Overflow occurs only when memory is exhausted.
• A new node is created with the given value.
• The new node’s next pointer is set to the current top.
• The top pointer is updated to point to this new node.
// Push operation OR Insertion at begin

void push(int value)

struct Node* newNode = (struct Node*) malloc(sizeof(structNode));

if (!newNode)

printf("Heap overflow. Cannot push %d\n", value);

return;

newNode->data = value;
 newNode->next = top;

top = newNode;

printf("%d pushed to stack\n", value);

Pop Operation
Removes the top item from the stack. If the stack is empty, it is said to be an
Underflow condition.
• Before deleting, we check if the stack is empty (top == NULL).
• If the stack is empty, underflow occurs and deletion is not possible.
• Otherwise, we store the current top node in a temporary pointer.
• Move the top pointer to the next node.
• Delete the temporary node to free memory.

// Pop operation OR Deletion from begin

int pop()
{
if (isEmpty())
 {
printf("Stack underflow. Cannot pop.\n");
return -1;
}
struct Node* temp = top;

int poppedValue = temp->data;

top = top->next;

free(temp);

return poppedValue;

// Peek (top element)

int peek() {

if (isEmpty()) {

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

return -1;

return top->data;

// Display the stack

void display() {
 if (isEmpty()) {

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

return;

struct Node* temp = top;

printf("Stack elements: ");

while (temp != NULL) {

printf("%d -> ", temp->data);

temp = temp->next;

printf("NULL\n");

// Main function to test the stack

int main() {

push(10);

push(20);

push(30);

display();
 printf("Top element is %d\n", peek());

printf("%d popped from stack\n", pop());

display();
return 0;

OUTPUT
10 pushed to stack
20 pushed to stack
30 pushed to stack
Stack elements: 30 -> 20 -> 10 -> NULL
Top element is 30
30 popped from stack
Stack elements: 20 -> 10 -> NULL