Assignment 7: Stack
Stack Data Structure –
Complete Explanation
A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The element inserted last is removed first, similar to a stack of plates.
Definition
A stack is an ordered collection of elements where insertion and deletion occur only at one end called the TOP.
LIFO Principle:
Push 10
Push 20
Push 30
Stack:
|30| ← TOP
|20|
|10|
Pop → 30 removed
Basic Operations
| Operation | Description |
|---|---|
| Push | Add an element to the top of the stack |
| Pop | Remove the top element |
| Peek/Top | View the top element without removing it |
| isEmpty | Check whether the stack is empty |
| isFull | Check whether the stack is full (array implementation) |
1. Push
Adds an element to the top.
Example:
Stack: Empty
Push(5)
|5|
Push(10)
|10|
|5|
2. Pop
Removes the top element.
Before:
|10|
|5|
Pop()
After:
|5|
3. Peek
Returns the top element.
Stack:
|20|
|15|
|10|
Peek() = 20
4. isEmpty
Checks if the stack contains no elements.
If TOP = -1
Stack is Empty
5. isFull
For array implementation:
If TOP = MAX - 1
Stack is Full
Stack Representation
Array Representation
TOP=3
|40| ← Top
|30|
|20|
|10|
Advantages:
Simple implementation.
Fast access.
Disadvantage:
Fixed size.
Linked List Representation
TOP
↓
30 → 20 → 10 → NULL
Advantages:
Dynamic size.
No overflow until memory is exhausted.
Algorithms
Push Operation
Algorithm PUSH(Stack, item)
1. Check if stack is full.
2. If full, print Overflow.
3. Else
TOP = TOP + 1
Stack[TOP] = item
4. Stop.
Pop Operation
Algorithm POP(Stack)
1. Check if stack is empty.
2. If empty, print Underflow.
3. Else
item = Stack[TOP]
TOP = TOP - 1
4. Return item.
Time Complexity
| Operation | Complexity |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Peek | O(1) |
| Search | O(n) |
Stack Overflow and Underflow
Overflow
Occurs when trying to insert into a full stack.
Example:
Size = 3
Push 10
Push 20
Push 30
Push 40
Overflow!
Underflow
Occurs when trying to delete from an empty stack.
Empty Stack
Pop()
Underflow!
Applications of Stack
Function call management (recursion).
Browser back/forward history.
Undo and redo operations.
Expression evaluation.
Parentheses matching.
Depth-first search (DFS).
Syntax parsing in compilers.
Backtracking algorithms.
Real-Life Examples
| Situation | Stack Behavior |
|---|---|
| Stack of plates | Last plate placed is first removed |
| Browser history | Last page visited is first returned |
| Undo in Word | Last action undone first |
| Book stack | Last book placed removed first |
Worked Example
Perform:
Push 10
Push 20
Push 30
Pop
Push 40
Peek
Step 1
Push 10
|10|
Step 2
Push 20
|20|
|10|
Step 3
Push 30
|30|
|20|
|10|
Step 4
Pop()
|20|
|10|
Removed = 30
Step 5
Push 40
|40|
|20|
|10|
Step 6
Peek() = 40
C Program for Stack Using Array
#include<stdio.h>
#define MAX 5
int stack[MAX];
int top = -1;
void push(int x){
if(top == MAX-1)
printf("Overflow\n");
else
stack[++top] = x;
}
void pop(){
if(top == -1)
printf("Underflow\n");
else
printf("Deleted: %d\n", stack[top--]);
}
void display(){
for(int i=top;i>=0;i--)
printf("%d\n", stack[i]);
}
int main(){
push(10);
push(20);
push(30);
display();
pop();
display();
return 0;
}
Advantages
Simple to implement.
Fast insertion and deletion.
Efficient memory access.
Useful in recursion and expression evaluation.
Disadvantages
Limited size in array implementation.
Only top element is directly accessible.
Searching is slower than direct-access structures.
Viva Questions
What is a stack?
What is the LIFO principle?
What is the difference between stack overflow and underflow?
What are the basic stack operations?
What is the time complexity of push and pop?
How is a stack implemented using arrays and linked lists?
What is the role of a stack in recursion?
Give four real-world applications of stacks.
University Exam Questions
Short Questions
Define a stack with an example.
Explain push and pop operations.
What is stack overflow and underflow?
List applications of stacks.
Long Questions
Explain stack operations with suitable algorithms and diagrams.
Describe array and linked list implementations of a stack.
Write a C program to implement a stack using an array.
Explain the applications of stacks in computer science with examples.
Key Point to Remember:
Stack = LIFO (Last In, First Out), where insertion (Push) and deletion (Pop) occur only at the TOP of the stack.
Set A
a) Implement a stack library (ststack.h) of integers using a static implementation of the stack and implementing the above six operations. Write a driver program that includes stack library and calls different stack operations.
Library Function ( .h file )
NOTE: save file name as ' ststack.h'.
struct node
{
int info;
struct node *ptr;
}*top,*top1,*temp;
int topelement();
void push(int data);
void pop();
void empty();
void display();
void destroy();
void stack_count();
void create();
int count = 0;
void create()
{
top = NULL;
}
void stack_count()
{
printf("\n No. of elements in stack : %d", count);
}
void push(int data)
{
if (top == NULL)
{
top =(struct node *)malloc(1*sizeof(struct node));
top->ptr = NULL;
top->info = data;
}
else
{
temp =(struct node *)malloc(1*sizeof(struct node));
temp->ptr = top;
temp->info = data;
top = temp;
}
count++;
}
void display()
{
top1 = top;
if (top1 == NULL)
{
printf("Stack is empty");
return;
}
while (top1 != NULL)
{
printf("%d ", top1->info);
top1 = top1->ptr;
}
}
void pop()
{
top1 = top;
if (top1 == NULL)
{
printf("\n Error : Trying to pop from empty stack");
return;
}
else
top1 = top1->ptr;
printf("\n Popped value : %d", top->info);
free(top);
top = top1;
count--;
}
int topelement()
{
return(top->info);
}
void empty()
{
if (top == NULL)
printf("\n Stack is empty");
else
printf("\n Stack is not empty with %d elements", count);
}
void destroy()
{
top1 = top;
while (top1 != NULL)
{
top1 = top->ptr;
free(top);
top = top1;
top1 = top1->ptr;
}
free(top1);
top = NULL;
printf("\n All stack elements destroyed");
count = 0;
}
Program:- sstack.c
#include <stdio.h>
#include <stdlib.h>
#include "ststack.h"
void main()
{
int no, ch, e;
printf("\n 1 - Push");
printf("\n 2 - Pop");
printf("\n 3 - Top");
printf("\n 4 - Empty");
printf("\n 5 - Exit");
printf("\n 6 - Display");
printf("\n 7 - Stack Count");
printf("\n 8 - Destroy stack");
create();
while (1)
{
printf("\n Enter choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter data : ");
scanf("%d", &no);
push(no);
break;
case 2:
pop();
break;
case 3:
if (top == NULL)
printf("No elements in stack");
else
{
e = topelement();
printf("\n Top element : %d", e);
}
break;
case 4:
empty();
break;
case 5:
exit(0);
case 6:
display();
break;
case 7:
stack_count();
break;
case 8:
destroy();
break;
default :
printf(" Wrong choice, Please enter correct choice ");
break;
}
}
}
b) Implement a stack library (dystack.h) of integers using a dynamic (linked list) implementation of the stack and implementing the above five operations. Write a driver program that includes stack library and calls different stack operations.
#include <stdio.h>
#include <stdlib.h>
#include "dystack.h"
int main()
{
int n, ch;
do
{
printf("\n\nStack Menu\n1. Push \n2. Pop\n3. Display\n0. Exit");
printf("\nEnter Choice 0-3? : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("\nEnter number ");
scanf("%d", &n);
push(n);
break;
case 2:
pop();
break;
case 3:
display();
break;
}
}while (ch != 0);
}
Library Function ( .h file )
NOTE: save file name as ' dystack.h'.
struct node
{
int data;
struct node *next;
};
struct node *top = NULL;
void display();
void push(int);
void pop();
void push(int item)
{
struct node *nptr = malloc(sizeof(struct node));
nptr->data = item;
nptr->next = top;
top = nptr;
}
void display()
{
struct node *temp;
temp = top;
while (temp != NULL)
{
printf("\n%d", temp->data);
temp = temp->next;
}
}
void pop()
{
if (top == NULL)
{
printf("\n\nStack is empty ");
}
else
{
struct node *temp;
temp = top;
top = top->next;
printf("\n\n%d deleted", temp->data);
free(temp);
}
}
Set B
a) Write a program to check whether the contents of two stacks are identical. Use stack library to perform basic stack operations. Neither stack should be changed.
#include <stdio.h>
#include "stststack.h"
int main(void)
{
stack s1,s2;
init(&s1);
init(&s2);
int num,n,i,j,size,number;
printf("How many elements in stack1: ");
scanf("%d",&n);
printf("Enter element to push: ");
for(i=0;i<n;i++)
{
scanf("%d",&num);
push(&s1,num);
}
printf("How many elements in stack2: ");
scanf("%d",&size);
printf("Enter elements in push: ");
for(i=0;i<size;i++)
{
scanf("%d",&number);
push(&s2,number);
}
stack t1,t2;
init(&t1);
init(&t2);
while(!isempty(&s1) && !isempty(&s2) && (peek(&s1)==peek(&s2)))
{
push(&t1,pop(&s1));
push(&t2,pop(&s2));
}
if(isempty(&s1) && isempty(&s2))
{
printf("\nStacks are identical\n");
}
else
{
printf("\nNot Equal\n");
}
while(!isempty(&t1))
push(&s1,pop(&t1));
while(!isempty(&t2))
push(&s2,pop(&t2));
}
Stack Library:
typedef struct stack
{
int data[200];
int top;
} stack;
void push(stack *ps,int num)
{
ps->data[++ps->top]=num;
}
int pop(stack *ps)
{
int num;
num=ps->data[ps->top--];
return num;
}
int isempty(stack *ps)
{
if(ps->top==-1)
return 1;
return 0;
}
int isfull(stack *ps)
{
if(ps->top==20-1)
return 1;
return 0;
}
int peek(stack *ps)
{
return ps->data[ps->top];
}
int init(stack *ps)
{
ps->top=-1;
}
b) Write a program that copies the contents of one stack into another. Use stack library to perform basic stack operations. The order of two stacks must be identical.(Hint: Use a temporary stack to preserve the order).
#include<stdio.h>
#include "stststack.h"
int main(void)
{
stack s1,t,s2;
init(&s1);
init(&s2);
init(&t);
int i,n,num;
printf("How many elements in stack1: ");
scanf("%d",&n);
printf("Enter element in stack1: ");
for(i=0;i<n;i++)
{
scanf("%d",&num);
push(&s1,num); //pushing elements in stack1
}
while(!isempty(&s1))
{
push(&t,pop(&s1)); //pushing stack1 elements in temporary stack
}
while(!isempty(&t))
{
push(&s1,peek(&t)); //pushing temporary stack element in stack1
push(&s2,pop(&t)); //pushing temporary stack element in stack2
}
printf("\n-----Elements of stack1 is copied in stack2------\n");
}
Stack Library:
typedef struct stack
{
int data[200];
int top;
} stack;
void push(stack *ps,int num)
{
ps->data[++ps->top]=num;
}
int pop(stack *ps)
{
int num;
num=ps->data[ps->top--];
return num;
}
int isempty(stack *ps)
{
if(ps->top==-1)
return 1;
return 0;
}
int isfull(stack *ps)
{
if(ps->top==20-1)
return 1;
return 0;
}
int peek(stack *ps)
{
return ps->data[ps->top];
}
int init(stack *ps)
{
ps->top=-1;
}
No comments:
Post a Comment