Stack Array Implementation

 Array implementation of Stack

 

The array implementation for Stack uses a TopOfStack variable which is –1 for an empty stack. Every time an element is inserted into the stack, the TopOfStack is incremented and Stack[TopOfStack] is set to the newly inserted element

Stack[TopOfStack] = X

Where Stack is the array representing the actual stack.

 

The declarations for Array implementation of Stack are

struct StackRecord;

typedef struct StackRecord *Stack;

 

int IsEmpty(Stack S);

int IsFull(Stack S);

Stack CreateStack(int maxElements);

void DisposeStack(Stack S);

void MakeEmpty(Stack S);

 

void Push(int X, Stack S);

void Pop(Stack S);

int Top(Stack S);

int TopAndPop(Stack S);

 

#define EmptyTOS (–1)

#define MinStackSize (5);

 

         struct StackRecord

{

                 int Capacity;

                 int TopOfStack;

                 int *Array;

         };

 

 

// Creating the Stack

Stack CreateStack(int maxElements)

{

         Stack S;

         S = malloc(sizeof(struct StackRecord));

         S->Array = malloc(sizeof(int)*maxElements);

         S->Capacity = maxElements;

return S;

}

 

// Empty the Stack – Delete all elements

void MakeEmpty(Stack S)

{

         S->TopOfStack = –1;

}      

 

// Dispose the Stack – delete array and Stack

void DisposeStack(Stack S)

{

if( S != NULL )

{

free( S->Array );

free( S );

}

}

 

// Check for Empty Stack

int IsEmpty(Stack S)

{

         return (S->TopOfStack == -1);

}

 

// Check for Full Stack

int IsFull(Stack S)

{

         return (S->TopOfStack == (S->Capacity–1));

}

 

 

// Insert element

void Push(int X, Stack S)

{

         if(IsFull(S))

                 printf(“Error – Full Stack. Cannot Insert.”);

         else

                 S->Array[++S->TopOfStack] = X;

}

 

// Delete element

void Pop(Stack S)

{

         if(IsEmpty(S))

                 printf(“Error – Empty Stack. Cannot Delete.”);

         else

                 S->TopOfStack––; 

}

 

// Display last inserted element

int Top(Stack S)

{

         if(!IsEmpty(S))

                 return (S->Array[S->TopOfStack]);

         printf(“Error – Empty Stack.”);

         return 0;

}

 

// Display last inserted element and delete it

int TopAndPop(Stack S)

{

         if(!IsEmpty(S))

                 return (S->Array[S->TopOfStack––]);

         printf(“Error – Empty Stack.”);

         return 0;

}