A stack is an abstract data structure where elements are pushed and deleted from only one end. We call this top of a stack.
This program implement stack using a linked-list structure. The linked-list is a linear list in which you can enter data only from one end. You must always insert from the front of the linked list so that it works like a stack.
The basic stack operations are given below.
- Push()
- Pop()
The Push () function insert an item into the stack and Pop () deletes the item from top of the stack. In the figure below, items are added to top and deleted from top. This is called Last In, First Out mechanism.
Problem Definition
A stack can be implemented using array data structure or a dynamically growing linked-list data structures. The linked-list implementation of stack does not need to check for “stack being full” because the list grows dynamically.
A linked-list has nodes that are linked together using pointers. A linked-list node has a data and a link pointer of type node that points to the next node element in the list.
An example of a node
struct node {
int data;
node* next;
};Steps to build a linked-list based stack is as follows
Step 1: Declare pointers to build initial stack.
struct node *head, *temp;The *head pointer of type struct points to the first node of the linked-list and the *temp pointer of type struct points to any new node you create. The pointers are created but does not point to anything. You must point to some variable or allocate memory to initialize them.
Step 2: Initialize the head node.
In C programming language, you must initialize any pointer by dynamically allocating memory using function malloc (). You initialize pointer head as follows
head =(struct node* )malloc( ( struct node))Now that have assigned memory to the head node, give values to its variables.
head->data=10;
head->next =NULL;See the following diagram to understand what initializing a node means.
The head pointer points to a location which has address 0x3000 and data value is 10. The node->next is also a pointer that maintain the linked-list and currently points to NULL.
Step 3: Create a new node and *temp points to it
We now create a new node by allocating memory dynamically for *temp.
temp = (struct node*) malloc ((struct node));assign values to the variable and point the next pointer to NULL.
temp->data = 20;
temp->next = NULL;See the memory drawing below to understand the process.
Right now, we have two independent nodes, not a linked-list. To start building a list and making sure that the linked-list work like a stack.
Step 4: Now temp nodes must point to head node so that it becomes the first node or head node.
temp->next = head;
Step 5: Write a pop () function that removes the top element.
In the stack, pop () function directly removes the top element automatically. You need to skip the top element and make the second element as the head of the linked-list based stack.
To make a new head use following code
head = head->next;Flowchart
Program Code – Stack using Linked-List
#include < stdio.h >
#include < stdlib.h >
#include < malloc.h >
struct node
{
int data;
struct node * next;
} * head, * temp, * p;
void push();
void pop();
int main()
{
int n, i;
char ch;
printf("how many nodes ?:");
scanf("%d", & n);
head = (struct node * ) malloc(sizeof(struct node));
printf("Enter a value for node->data:");
scanf("%d", & head - > data);
head - > next = NULL;
for (i = 0; i < n - 1; i++)
{
push();
}
printf("\n\n");
printf("Top = %d \n\n ", head - > data);
printf("Do you wish to Pop:y/n:");
scanf("%s", & ch);
if (ch == 'y')
{
pop();
printf("\n\n");
printf("new top = %d\n", head - > data);
printf("\n\n");
}
system("PAUSE");
return 0;
}
void push()
{
temp = (struct node * ) malloc(sizeof(struct node));
printf("Enter a value for node->data:");
scanf("%d", & temp - > data);
temp - > next =
head = temp;
}
void pop()
{
head = head - > next;
}Output
When you run the program, enter the number of nodes required for linked-list based stack. Then start entering value to the top of the stack. In the following figure, 434 is the last in entry, so it is the top of the stack, also head of the linked-list.
If you decide to pop() the top element – 434, then the second last entry becomes the top element. In this case, 125 is the new top element.
