CSC-221 DATA STRUCTURES AND ALGORITHMS
Instructor: Ayesha Jamal
Lecture : Stack & its implementation using arrays & linked list
STACK
2
STACK
Stack is a linear data structure in which data insertion and deletion is done
at one end.
Order may be LIFO(Last In First Out) or FILO(First In Last Out).
Stacks in real life: stack of books, stack of plates
Add new items at the top
Remove an item at the top
Stack data structure similar to real life: collection of elements arranged in a
linear order.
3
Can only access element at the top
WHAT IS A STACK?
It is an ordered group of homogeneous items.
Elements are added to and removed from the top of the stack (the most recently added
items are at the top of the stack).
The last element to be added is the first to be removed (LIFO: Last In, First Out).
4
INSERTION & DELETION ON STACK
5
6
STACK OPERATIONS
Push(): Adds an item in the stack. If the stack is full, then it is said to be
an Overflow condition.
Pop(): 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.
Top(): Returns the top element of the stack.
7
8
RELATED TERMINOLOGY
Top
A pointer that points the top element in the stack.
Stack Underflow
When there is no element in the stack, we cannot pop an element: stack underflow
Stack Overflow
When the stack contains equal number of elements as per its capacity and no more
elements can be added: stack overflow 9
IMPLEMENTATION OF STACK
There are two ways to implement a stack:
Using array
Using linked list
10
STACK IMPLEMENTATION
Implementation can be done in two ways
Static implementation
Dynamic Implementation
Static Implementation
Stacks have fixed size, and are implemented as arrays
It is also inefficient for utilization of memory
Dynamic Implementation
Stack grow in size as needed, and implemented as linked lists
Dynamic Implementation is done through pointers
11
The memory is efficiently utilized with Dynamic Implementations
PUSH OPERATION
The following steps should be taken to push (insert) data into a stack −
Step 1 − Check if the stack is full.
Step 2 − If the stack is full, produce overflow error and exit.
Step 3 − If the stack is not full, increment top to point the next empty
space.
Step 4 − Add data element to the stack location, where the top is pointing.
Step 5 − return success.
12
POP OPERATION
The following steps are taken to perform pop operation −
Step 1 − Check if the stack is empty.
Step 2 − If the stack is empty, produce underflow error and exit.
Step 3 − If the stack is not empty, access the data where top is pointing and
remove it.
Step 4 − Decrement top to point to the next available data element.
Step 5 − Return success.
13
SELF PRACTICE
Give output after following sequence of commands have been executed:
1. S.Push(‘A’);
2. S.Push(‘B’);
3. S.Push(‘C’);
4. S.Pop();
5. S.Pop();
6. S.Push(‘D’);
7. S.Push(‘E’);
8. S.Pop();
14
9. S.Pop();
Stack Implementation
using Arrays
15
STACK USING ARRAY
#include <iostream>
using namespace std;
int n=5, top=-1 ;
int stack_array[n];
16
PUSH OPERATION
void push(int data) //push operation
{
if(top=n-1) //stack is full cannot push new element
cout<<"Stack Overflow"<<endl;
else
{
top++;
stack_array[top]=data;
} 17
}
PUSH OPERATION USING IS FULL FUNCTION
void push(int data) //push operation
bool isfull()
{
{ if(top==n-1) //stack is full
if(! isfull())
cannot push new
element {
top++;
return true;
stack_array[top]=data;
else
}
return false; else
} {
cout<<"Stack Overflow"<<endl;
18
}
}
POP OPERATION
void pop() //pop operation
{
if(top==-1) //stack is empty already
cout<<"Stack Underflow"<<endl;
else
{
cout<<"The popped element is "<< stack[top] <<endl;
top--;
}
19
}
POP OPERATION USING IS EMPTY FUNCTION
void pop() //pop operation
bool isempty() {
{ if(top==-1) //stack is if(! isempty())
empty already {
return true; cout<<"The popped element is "<<
stack[top] <<endl;
else
top--;
return false;
else
}
{
cout<<"Stack Underflow"<<endl; 20
}
TRAVERSING STACK
void display() //display elements of stack array
{
if(top>=0)
{
cout<<"Stack elements are:";
for(int i=top; i>=0; i--)
{ cout<<stack[i]<<" ";
cout<<endl; }
}
else
cout<<"Stack is empty";
21
}
STACK USING ARRAY
Pros: Easy to implement. Memory is saved as pointers are not involved.
Cons: It is not dynamic. It doesn’t grow and shrink depending on needs
at runtime.
22
Stack Implementation
using Linked List
23
STACK USING LINKED LIST
We can avoid the size limitation of a stack implemented with an array by
using a linked list to hold the stack elements.
As with array, however, we need to decide where to insert elements in the list
and where to delete them so that push and pop will run the fastest.
24
THE STACK CLASS
Class Stack
{
public:
Node *Top = NULL;
void push(int);
int pop();
void displayStack();
int Top();
};
*Same node class will be used as list 25
PUSH OPERATION USING LIST
void stack::push(int value)
{
Node *ptr;
ptr=new Node();
ptr->data=value;
//ptr->next=NULL;
if(top==NULL)
{ptr->next=NULL;}
else
{ptr->next=top; }
top=ptr; 26
}
POP OPERATION
int stack::pop()
{
if(top==NULL)
{
cout<<"The stack is empty!!!";
return -1;
}
Node *temp = top;
top=top->next;
int retValue = temp->data;
delete temp;
return retValue; 27
}
DISPLAY TOP
int Stack :: top()
{
return top->data;
}
28
DISPLAY OR TRAVERSING STACK
void stack::displayStack()
{
if(top==NULL)
cout<<"stack is empty";
else
{
Node *ptr = top;
cout<<"Stack elements are: ";
}
while (ptr != NULL)
{
cout<< ptr->data <<" ";
ptr = ptr->next;
} 29
}
STACK IMPLEMENTATION USING LINKED LIST
10
Push(20);
20 10
top
Push(30); top
30 20 10
30
top
STACK IMPLEMENTATION USING LINKED LIST
30 20 10
top
Pop();
20 10
top 31
STACK USING LINKED LIST
Pros: The linked list implementation of a stack can grow and shrink
according to the needs at runtime.
Cons: Requires extra memory due to involvement of pointers.
32
REAL LIFE APPLICATIONS OF STACK
Converting infix to postfix expressions.
Undo operation is also carried out through stacks.
Forward – backward surfing in browser
History of visited websites
Message logs and all messages you get are arranged in stack
Call logs, E-mails, Google photos’ any gallery , YouTube downloads,
Notifications ( latest appears first )
33
