Page 66 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 3: Stacks

return(x); Notes
}
}
boolean empty()
/* checks if the stack is empty * /
{
boolean empty = false;
if(stack.top == -1)
empty = true else empty = false;
return(empty);
}
void initialise()
/* This procedure initializes the stack s * /
{
stack.top = -1;
}
The above implementation strategy is easy and fast since it does not have run-time overheads.

At the same time it is not flexible since it cannot handle a situation when the number of elements
exceeds max_size. Also, let us say, if max_size is derided statically to 100 and a stack actually has
only 10 elements, then memory space for the rest of the 90 elements would be wasted.

Task Write a syntax to declare array in a program.

3.2.2 Pointer-based Implementation

Here the memory is used dynamically. For every push operation, the memory space for one
element is allocated at run-time and the element is inserted into the stack. For every pop
operation, the memory space for the deleted element is de-allocated and returned to the free
space pool. Hence the shortcomings of the array-based implementation are overcome. But since,
this allocates memory dynamically, the execution is slowed down.

The stack is implemented as a linked list as shown in Figure 3.1.
Figure 3.1: Implementation of a Stack using a Linked List

Top
23 45 –98
Nil

The following pseudo-code is for the pointer-based implementation of a stack. Each element of
the stack is of type T.

struct stk
{
T element;

LOVELY PROFESSIONAL UNIVERSITY 61