*950*

An implementation of stack is similar to that of a Linked List. We will try to discuss the basic operations in a stack discussed in this post.

#### MAIN OPERATIONS ON A STACK:-

**push( int )**:- Inserts a data into the stack**pop**:- Returns the topmost data from the stack

#### AUXILIARY OPERATIONS ON A STAC**K**

**int Top( )**:- returns the topmost element on the stack**int Size( )**:- returns the total size of the stack**int isStackEmpty( )**:- returns true if the stack is empty

The data structure for a stack can be made as the same as that of a single Linked List. We need a node with a next element.

struct stackNode { int data; struct stackNode * next; };

Now we need to define the basic function of pushing a node in the stack. A PUSH operation, adds a new node in the stack and points the TOP of the stack to this new node.

// defining the generic function to PUSH an element into the stack struct stackNode * push(struct stackNode * top, int element) { //creating a temporary node and assigning the element to be PUSHED struct stackNode * temp = (struct stackNode *)malloc(sizeof(struct stackNode)); temp -> data = element; // we need to point the NEXT of this node to the previous TOP temp -> next = top; // we need to update the TOP node and then return it // we can simply return the 'temp' node as it points to the new TOP node. return temp; }

Now let us define a function to check if the stack is empty. A stack is empty, if the top node points to a NULL location

// defining a function to check if a stack is empty int isStackEmpty(struct stackNode * top) { if(top == NULL) return 1; else return 0; }

Now to define the POP function. To define the POP function, we must check if the stack is empty or not. If the stack is empty, that means we cannot POP any value and it is a case of stack underflow. However, if the stack is not empty, we simply print the TOP value and delete the top node.

// defining a function to pop an element from a stack struct stackNode * pop(struct stackNode * top) { // check if the stack is empty if(isStackEmpty(top)) { printf("STACK IS EMPTY...Stack underflow"); return NULL; } else { printf("POP element = %d",top -> data); // we need to delete the top and move to the next element. struct stackNode * temp = top; // move to the next node top = top -> next; // delete the original top free(temp); // return the new top return top; } }

The last function to get the number of elements in the stack is same as calculating the length of a single Linked List.

// function to get the size of the stack int getStackSize(struct stackNode * top) { int count = 0; while(top) { count++; top = top -> next; } return count; }

These were the basic functions used in implementing a stack and being generic functions can be used anytime we need to implement stacks. Here is a working demo of the code that utilizes all the above function. Use your favorite editor to edit it. (gEdit, vim, notepad++)

## 2 comments

This program has a flaw of not passing double pointer. So POP routine here needs to be corrected to reflect the right pointer in the caller.

Hi Sai,

We cannot pass a double pointer in C. Consider it a limitation. The POP routine is correct and it returns the correct pointer. Have a look at this code snippet

Also find the working demo here http://ideone.com/H99BUq

Feel free to ask if you have any other queries.

Comments are closed.