As an exercise, i will design and implement my own stack ADT.

First of all we need to build necessary structures.

The Head structure will contain a counter and a pointer to stack nodes.

The node structure will contain a data pointer and a node pointer.

typedef struct node2
{
   void *dataPtr;
   struct node2 *nodePtr;
} NODE;
 
typedef struct
{
   int count;
   NODE *top;
} STACK;

We have constructed two structures: STACK structure will be the head of the stack. The head structure has a NODE pointer to the top of the stack and an integer to hold the number of the nodes. NODE structure will hold the given data. And of course, it has a link to another node.

Since we have constructed the structures, we can start to implement the operations.

Let me talk about the operations that i will implement. I am going to implement create, push and pop operations. Push adds data to the stack and pop retrieves data. As you know, all the operations affect the top of the stack.

In order to create a stack, we need to allocate the necessary memory and then we must update the head node:

STACK *createStack(void)
{
   STACK* stack;
 
   stack = (STACK*)(malloc(sizeof(STACK));
 
   if(stack)
   {
      stack->count = 0;
      stack->top = NULL;
   }
 
   return stack;
}

This one is easy to explain. We simply allocate memory for the head node and if allocation is done successfully, we simply set the counter as zero and pointer as NULL due to having no items at the stack.

After successfully creating the stack, the next goal is adding data to the stack. It is a little bit more trivial but still easy to understand. I will not explain the code, not now at least.

// it will return 1 if the operation is successful, 0 otherwise
// thanks to the generic pointer, any type of data can be pushed
int pushStack(STACK* stack, void* data)
{
    // allocate memory for the new node
    NODE* node;
    node = (NODE*)malloc(sizeof(NODE));
 
    // check if allocations is done
    if(!node)
       return 0;   
 
   // update the node
   node->nodePtr = stack->top;
   node->dataPtr = data;
 
   // update the head
   stack->top = node;
   (stack->count)++;
 
   return 1;
}

Now it is time to retrieve data.

void *popStack(STACK* stack)
{
    void *dataOut; //again, we love you generic pointer
 
   // empty stack cannot be popped
   if(stack->count==0)
     dataOut = NULL;
   else
   {
      dataOut = stack->head->dataPtr;
      NODE* temp = stack->top; // we dont want no leaks
      stack->top = stack->top>nodePtr;
      (stack->count)--;
      free(temp); // freedom <3
   }
 
return dataOut; 
}

I know i have not explained neither the code nor the ADT itself well enough. I will try to update this post -most probably i will not- but the whole point of this post is implementing stacks on my own and recapping it.

I have written all the code on wordpress and have not compiled. If you try any errors or if you have any questions, please feel free to ask or inform me.