Stack

A stack is a non-primitive linear data structure.

It is an ordered list in which the insertion of a new element and removal of

an existing element takes place at the same end which is called the top.

pile of plates stack of chairs stack of plates

Stack is also called LAST-IN-FIRST-OUT (LIFO) type of data structure.

To implement the stack, it is required to maintain the pointer to the top of
the stack, which is the last element to be inserted because we can access
the elements only on the top of the stack.

Stacks can be implemented either using an array or a linked list.

Basic Operations on Stack
In order to make manipulations in a stack, there are certain operations
provided to us.

➢ push( ) to insert an element into the stack

➢ pop( ) to remove an element from the stack

➢ peek( ) returns the top element of the stack.

➢ isEmpty( ) returns true if stack is empty else false.

➢ isFull( ) returns true if stack is full else false.

➢ display( ) to print all elements of the stack.

Stacks implementation using an array:
#define MAX 10
int stack_arr[MAX];
int top = -1;

(a) Empty stack (b) Push 5 (c) Push 10

top = -1 top = 0 top = 1
5 5 10
[0] [1] [2] [3] [4] [0] [1] [2] [3] [4] [0] [1] [2] [3] [4]

(d) Push 15 (e) Push 20 (f) Push 25

top = 2 top = 3 top = 4
5 10 15 5 10 15 20 5 10 15 20 25
[0] [1] [2] [3] [4] [0] [1] [2] [3] [4] [0] [1] [2] [3] [4]

(g) Pop 25 (h) Pop 20 (i) Pop 15

top = 3 top = 2 top = 1
5 10 15 20 5 10 15 5 10
[0] [1] [2] [3] [4] [0] [1] [2] [3] [4] [0] [1] [2] [3] [4]
(j) Push 30 (k) Pop 30 (L) Pop
10
top = 2 top = 1 top = 0
5 10 30 5 10 5
[0] [1] [2] [3] [4] [0] [1] [2] [3] [4] [0] [1] [2] [3] [4]
 Push Operation: Push adds an item to the stack. If the stack is full, then it is
said to be an Overflow condition. If TOP = -1, then it indicates that the stack
is empty and if TOP = MAX -1, then the stack is full.

Algorithm to PUSH an element in void push(int item)

a stack {
if(isFull())
Step 1: IF TOP = MAX-1, then {
PRINT “OVERFLOW” printf(“stack overflow”);
Goto Step 4 return;
[END OF IF] }
Step 2: SET TOP = TOP + 1 top = top + 1;
Step 3: SET STACK[TOP] = VALUE stack_arr[top] = item;
Step 4: END } Stack_arr[++top] = item;
 Pop Operation: Pop removes an item from the top of the stack. If the stack
is empty, then it is said to be an Underflow condition.

Algorithm to POP an element int pop( )

from a stack {
int item;
Step 1: IF TOP = -1, then if(isEmpty())
PRINT “UNDERFLOW” {
Goto Step 4 printf(“stack underflow”);
[END OF IF] return;
Step 2: SET VAL = STACK[TOP] }
Step 3: SET TOP = TOP - 1 item = stack_arr(top);
Step 4: END top = top-1;
return item;
} return stack_arr[top--];
 Peek Operation: return the top element of the stack.
Algorithm for Peek Operation int peek( )
{
Step 1: IF TOP = -1, then if(isEmpty())
PRINT “STACK IS EMPTY”
{
Go TO Step 3
[END OF IF] printf(“stack underflow”);
Step 2: RETURN STACK[TOP] return;
Step 3: END }
return stack_arr(top);
}

isFull( ) Operation

int isFull( )
{
if(top = MAX-1)
return 1;
else
return 0;
}
isEmpty( ) Operation int isEmpty( )
{
if(top = -1)
return 1;
else
return 0;
}

display( ): print all elements of the stack.

void display( )
{
int i;
if(isEmpty())
{
printf(“stack is empty\n”);
return;
}
printf(“stack elements: ”);
for(i=top; i>=0; i--)
printf(“%d\n”, stack_arr(i));
printf(“\n”);
}
 Disadvantages of array implementation

• It is not dynamic i.e., it doesn’t grow and shrink depending on needs at

runtime.

• The total size of the stack must be defined beforehand.

Stacks implementation using a Linked List:
• When the size of the stack is not known in advance, it is better to
implement it as a linked list.

• The main advantage of using a linked list over arrays is that it is possible to
implement a stack that can shrink or grow as much as needed.

struct node
{
int info;
struct node *link;
};
struct node *top = NULL;
(a) Empty Stack (b) Push 5 (c) Push 10
Top is NULL Top Top

5 10 5

(d) Push 15 (e) Pop

Top Top 15

15 10 5 10 5

(f) Pop (g) Pop

Top 10 Top 5

5
Push Operation: The function push( ) would be similar to the function
addatbeg( ) of single linked list.
void push(int item)
{
struct node *tmp;
tmp = (struct node*)malloc(sizeof(struct node));
tmp -> info = item;
if(tmp = = NULL) /*Memory is full*/
{
printf(“Stack Overflow\n”);
return;
}
tmp->link = top;
top = tmp;
}

(b) Push 5 (c) Push 10

Top Top

5 10 5

Prepared by: Dr Deepak Gupta, CSED, MNNIT Allahabad, India

Pop Operation: Pop delete the first element of the linked list. If the stack is
empty, then it is said to be an Underflow condition.

int pop( )
{ (e) Pop
struct node * tmp; Top 15
int item;
if(isEmpty())
{ 10 5
printf(“stack underflow”);
return;
} (f) Pop
tmp = top; Top 10
item = tmp->info;
top = top->1ink;
free(tmp);
5
return item;
}

Prepared by: Dr Deepak Gupta, CSED, MNNIT Allahabad, India

 Peek Operation: return the top element of the stack.
Algorithm for Peek Operation int peek( )
{
Step 1: IF TOP == NULL, then if(isEmpty())
PRINT “STACK IS EMPTY”
{
Go TO Step 3
[END OF IF] printf(“stack underflow”);
Step 2: RETURN STACK[TOP] return;
Step 3: END }
return top->info;
}

isEmpty( ) Operation int isEmpty( )

{
if(top == NULL)
return 1;
else
return 0;
}

isFull( ) Operation: This operation is not required.

Prepared by: Dr Deepak Gupta, CSED, MNNIT Allahabad, India
display( ): print all elements of the stack.
void display( )
{
struct node *ptr;
ptr = top;
if(isEmpty())
{
printf(“stack is empty\n”);
return;
}
printf(“stack elements: ”);
while(ptr!=NULL)
{
printf(“%d\n”, ptr->info);
ptr = ptr->link;
}
}

Prepared by: Dr Deepak Gupta, CSED, MNNIT Allahabad, India