Implementation of Stack
Lecture #
By: Abdul Aleem
1 / 20
Contents
Introduction
2 Stack Implementation
3 Array Implementation of Stack
4 Linked List implementation of stack
2 / 20
Introduction
Stack:
Stack is an ordered set of
elements in which insertion and
deletion are from one end of the
stack called the Top of the stack.
It works on the principle Last In
First Out (LIFO). Figure 1: Stack LIFO
3 / 20
Stack Implementation
Static Implementation (Array Implementation)
Dynamic Implementation (Linked List
Implementation)
4 / 20
Array Implementation of Stack
Array implementation of stack is a static implementation as the size of the
stack is known.
class Stack
{
int top;
int MAXSIZE = 5;
int[] arr = new int[MAXSIZE];
}
5 / 20
isFull( )
public boolean isFull()
{
if(top == (MAXSIZE-1))
return true;
else
return
false;
}
6 / 20
PUSH Operations on Stack
public void push(int x)
{
if (isFull())
{
[Link]("Overflow");
[Link](0);
}
[Link]("Inserting " + x);
arr[++top] = x;
}
7 / 20
Push operations on stack
Figure 2: PUSH operation in Stack
8 / 20
isEmpty( )
public boolean isEmpty()
{
if(top == -1)
return true;
else
return false;
}
9 / 20
POP Operations on Stack
public int pop()
{
if (isEmpty())
{
[Link]("Underflow");
[Link](0);
}
return arr[top--];
}
10 / 20
Pop operations on stack
Figure 3: POP operation in Stack
11 / 20
Display the stack
public int peek()
{
if (!isEmpty())
{ return
arr[top];
}
else {
[Link](0);
}
return -1;
}
12 / 20
Display operation on stack (Example)
Figure 4: Display the Stack elements
13 / 20
Linked List implementation of stack
Linked list allocates the memory
dy- namically.
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. Figure 5: Linked List implementation of Stack
14 / 20
PUSH Operation
Adding a node to the stack is referred to as push operation. Pushing an element to a
stack in linked list implementation is different from that of an array implementation.
In order to push an element onto the stack, the following steps are involved.
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.
15 / 20
PUSH Operation
Figure 6: Adding a node to the Stack
16 / 20
POP Operation
Deleting a node from the top of stack is referred to as pop operation. In order to pop
an element from the stack, we need to follow the following steps :
Check for the underflow condition: The underflow condition occurs when
we try to pop from an already empty stack. The stack will be empty if the head
pointer of the list points to null.
Adjust the head pointer accordingly: In stack, the elements are popped only
from one end, therefore, the value stored in the head pointer must be deleted and
the node must be free. The next node of the head node now becomes the head
node.
17 / 20
POP Operation
Figure 7: Deleting a node from the Stack
18 / 20
Display the nodes
Copy the head pointer into a temporary pointer.
Move the temporary pointer through all the nodes of the list and print the
value field attached to every node.
Figure 8: Display the nodes in the Stack
19 / 20
Reference
[1] Goodrich and Tamassia ‘Data Structures and Algorithms in java ’, Wiley, India.
20 / 20
