Stack List Implementation

 Linked List Implementation of Stacks using Single Linked List

A stack is a fundamental data structure that follows the Last-In-First-Out (LIFO) principle – The last element added to the stack is the first one to be removed from the list. Important operations on stack include Push(insert element), Pop(delete element) and Top(find the top most element in stack).

Stack can be implemented using arrays and linked list. While arrays are a common implementation for stacks, linked lists offer some advantages:

• Dynamic Size: Linked lists can grow or shrink as needed, eliminating the risk of stack overflow.
• Efficient Memory Usage: Memory is allocated only for the elements currently in the stack.

 

 

The declarations for Linked List implementation of Stack are

struct Node;

typedef struct Node *PtrToNode;

typedef PtrToNode Stack;

 

int IsEmpty(Stack S);

Stack CreateStack(void);

void MakeEmpty(Stack S);

 

void Push(int X, Stack S);

void Pop(Stack S);

int Top(Stack S);

 

         struct Node

{

                 int Element;

                 struct Node * Next;

         };

 

 

// Creating the Stack

Stack CreateStack()

{

         Stack S;

         S = malloc(sizeof(struct Node));

         if(S==NULL)

printf(“Memory allocation error”);

return S;

}

 

// Empty the Stack – Delete all elements

void MakeEmpty(Stack S)

{

         if(S==NULL)

                 printf(“Error – No stack. Create stack first”);

         else

                 while(!IsEmpty(S))

                          Pop(S);

}      

 

// Check for Empty Stack

int IsEmpty(Stack S)

{

         return (S->Next == NULL);

}

 

 

// Insert element

void Push(int X, Stack S)

{

         PtrToNode Tmpcell

 

         Tmpcell = malloc(sizeof(struct Node));

         if(Tmpcell == NULL)

                 printf(“Memory allocation error.”);

         else

         {

                 Tmpcell->Element = x;

                 Tmpcell->Next = S->Next;

                 S->Next = Tmpcell

         }

}

 

// Delete element

void Pop(Stack S)

{

         PtrToNode Tmpcell;

 

         if(IsEmpty(S))

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

         else

         {

                 Tmpcell = S->Next;

                 S->Next = S->Next->Next;

                 Free(Tmpcell);

         }

}

 

// Display last inserted element

int Top(Stack S)

{

         if(!IsEmpty(S))

                 return (S->Next->Element);

         printf(“Error – Empty Stack.”);

         return 0;

}

 

•