Let's start by understanding the problem statement of this task.
You have to implement a stack using a linked list.
Hint:
For implementing a stack using a linked list, you have to just keep shifting the head pointer to the next node and keep clearing the node which was the former head.
Quick Think:
For implementing a stack using a linked list, we need to keep the following points in mind:-
- If the node is null, return -1 and terminates the process.
- The stack to be inserted into the linked list should be inserted in a similar manner as the node is inserted into the linked list.
- Every time we remove a stack from the linked list, we will need to shift the head node pointer to the next node in the list.
Algorithm:
Declare a function to push the stack into the linked list which will work in a similar manner as it for inserting a node into a linked list and another function to pop the stack from the list with the argument as the pointer to the head of the linked list and follow the steps to get the output:-
Step1: Check for the node to be NULL, if yes then return -1 and terminate the process, else go to step 2.
Step2: Declare a temporary node and store the pointer to the head node.
Step3: Now, shift the pointer to the current head stack to the next stack in the linked list.
Step4: Store the data of the current node and then delete the node.
Step5: Return the stored data of the popped node, which will be our stack which is popped out from the list.
Implementation Of The Above Algorithm:
Now let's see the implementation of the above algorithm,
#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
struct node * next;
};
struct node* newnode(int data)
{
struct node * node;
node = (struct node *) malloc(sizeof(struct node));
node->data = data;
node->next = NULL;
return node;
}
/*Function to push the stack into the list. */
void push(struct node **head_ref, int data)
{
struct node *node = newnode(data);
node->next = (*head_ref);
(*head_ref) = node;
cout << "Pushed to stack " << data << endl;
}
/*Function to print the first element in the list. */
int peek(struct node *head)
{
if (head == NULL)
return -1;
int peeked = head->data;
return peeked;
}
/*Function to pop the stack from the list. */
int pop(struct node **head_ref)
{
if ((*head_ref) == NULL)
return -1;
struct node *temp = *head_ref;
(*head_ref) = (*head_ref)->next;
int popped = temp->data;
free(temp);
return popped;
}
/*Driver function to test the above algorithm. */
int main()
{
struct node *root = NULL;
push(&root, 67);
push(&root, 70);
push(&root, 20);
cout << "Popped from stack = " << pop(&root) << endl;
cout << "Top element is = " << peek(root) << endl;
return 0;
}
The time complexity of the above algorithm: O(n)
The output of the above algorithm is: Pushed into stack 67,
Pushed into stack 70,
Pushed into stack 20,
Popped from stack = 20,
The top element is 70.
Explanation Of The Above Algorithm:
Let us take an example of the stack as shown in the above diagram and follow the steps below to reach the output:-
- The node with data 67 is pushed into the list and the next node is made the head node as shown in the diagram above.
- Next, we have a node with data 70 which is also pushed into the list and the next node is made the head node as shown in the diagram above.
- Similarly, the node with data 20 is pushed into the list, as shown in the diagram above.
- Now, the first node is to be popped out from the list and 20 is popped out and hence the top element becomes 70 as shown in the above diagram.