Page 65 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes if STACK-EMPTY(S)

then error “underfl ow”
else top[S] <- top[S] – 1
return S[top[S] + 1]
The running time for the operations is O(1) (constant time).

3.2 Implementation of Stacks

There are two basic methods for the implementation of stacks – one where the memory is used
statically and the other where the memory is used dynamically.

3.2.1 Array-based Implementation

In this scheme, an array of certain maximum size is allocated memory statically (i.e. once for all).
The stack and its operations are implemented using this array.

The following pseudo-code shows the array-based implementation of a stack. In this, the elements
of the stack are of type T.
struct stk
{ T array[max_size];
/* max_size is the maximum size */
int top = -1;
/* stack top initially given value -1 */
} stack;
void push(T e)
/*inserts an element e into the stack s*/
{
if (stack.top == max_size)
printf(“Stack is full-insertion not possible”);
else
{
stack.top = stack.top + 1;
stack.array[stack.top] = e;
}
}
T pop()
/*Returns the top element from the stack */
{
T x;
if(stack.top == -1)
printf(“Stack is empty”);
else
{
x = stack.array[stack.top];
stack.top = stack.top - l;

60 LOVELY PROFESSIONAL UNIVERSITY