Implementing a stack using linked list is the a very basic application of the linked list data structure. It tests your ability to visualize the usage of a complex data structure (such as a Stack) in terms of a more primitive data structure such as a linked list. Stack is a LIFO (Last In First Out) structure. That means that the last element in is the first element out. In programming terms, that means that you insert new elements at the top of the list and you remove elements from the top too. Simple, right?

First, let's define our linked list data structure. This is the same as in our previous examples:

typedef struct linked_list

{

int data;

struct linked_list *next;

} Node;

For us to be able to test our code, we need to define a way to display our stack. There are multiple ways to display the stack – you can use a loop (do-while) or you can use recursion. Guess what? We have already covered recursion. So let's try recursion to display the stack.

// recursively display the contents

// of the stack

void DisplayStack(Node* currentNode)

{

// recursive termination condition

if (currentNode == NULL)

{

return;

}

// the node is not null

// display the data

printf(" -> %d", currentNode->data);

// recursively call the display to

// display the next element in the stack

DisplayStack(currentNode->next);

}

Now that we have figured out the display, let's check out the code for pushing an element onto the stack.

// push item on the stack

// this is same as adding a node

// at the top of the list

void Push(int dataToAdd)

{

// assumption: head is already defined elsewhere in the program

// 1. create the new node

Node *temp = new Node;

temp->data = dataToAdd;

// 2. insert it at the first position

temp->next = head;

// 3. update the head to point to this new node

head = temp;

}

// pop an element from the stack

// this is same as removing the first element

// from the list

Node* Pop()

{

// check for empty list

if (head == NULL)

{

printf("Stack is empty\n");

return NULL;

}

// get the top node

Node *firstNode = head;

// move the head

head = head->next;

// disconnect the node

// from the list

firstNode->next = NULL;

// return the top node

return firstNode;

}

That's it. You now know how you can implement a stack using linked list. We will discuss another application of stacks (using linked lists) in a future post.

cooooollllll maaaahnnnnn

ReplyDelete;*

damn interview!!!!!!!!

ReplyDeletewot d hell s wrong wt u...:/:/