// C program for linked list implementation of stack #include <stdio.h> #include
ID: 3833185 • Letter: #
Question
// C program for linked list implementation of stack
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// A structure to represent a stack
struct StackNode
{
int data;
struct StackNode* next;
};
struct StackNode* newNode(int data)
{
struct StackNode* stackNode =
(struct StackNode*) malloc(sizeof(struct StackNode));
stackNode->data = data;
stackNode->next = NULL;
return stackNode;
}
int isEmpty(struct StackNode *root)
{
return !root;
}
void push(struct StackNode** root, int data)
{
struct StackNode* stackNode = newNode(data);
stackNode->next = *root;
*root = stackNode;
printf("%d pushed to stack ", data);
}
int pop(struct StackNode** root)
{
if (isEmpty(*root))
return INT_MIN;
struct StackNode* temp = *root;
*root = (*root)->next;
int popped = temp->data;
free(temp);
return popped;
}
int peek(struct StackNode* root)
{
if (isEmpty(root))
return INT_MIN;
return root->data;
}
int main()
{
struct StackNode* root = NULL;
push(&root, 10);
push(&root, 20);
push(&root, 30);
printf("%d popped from stack ", pop(&root));
printf("Top element is %d ", peek(root));
return 0;
}
output:
10 pushed to stack
20 pushed to stack
30 pushed to stack
30 pushed to stack
Top element is 20
Question: Describe how the program implements the data structure known as stack?
Explanation / Answer
Firstly the output mentioned is wrong. The correct output is as follows: -
10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top element is 20
This implementation of stack is done using linked list. the top of the stack is always pointed by root node. The description of methods of this code is as follows: -
1. A structure of StackNode is created that holds two elements. First is the data and second is the pointer pointing to next element in the list.
2. newNode(int data) - this method is used to create a new node compatible to the linked list. data passed in the function signature is assigned to the stack data and the next pointer is assigned as NULL. The node thus created is returned.
3. isEmpty(*root) - this method checks if the root is empty . . i.e. there is no element in stack. If root pointer is not there i.e. there is no element to which root is pointing, it means stack is empty.
4. push(struct StackNode** root, int data) - This method takes in the location at which element needs to be inserted. Here the property is maintained that element is always added at the root. As root always points to top. So element is always added at the top. It uses the method described in point 2) to create a new node and the next pointer is kept equal to address pointed by root node. Root pointer is not updated to new node. So, now root points to new element added which is on the top of the stack.
5. pop(struct StackNode** root) - It pops out the element which is at the top. i.e. at the position pointed by root pointer. First it checks if the stack is empty by using point 3) . If it is not empty the function pops out the element at the top and update the root pointer the location next to the popped up element. So now root element points to element which was under the popped element.
6. peek(struct StackNode* root) - This method gets the value of the top element and returns it if the list is not empty.
So peek and pop always shows and returns the last element added. So it follows LIFO principal. Thus the program implements the stack data structure.
Now about the output.
First 10 is pushed, so Now root points to 10. and message 10 pushed to stack is printed.
Now 20 is pushed, so Now root points to 20. and message 20 pushed to stack is printed.
Now 30 is pushed, so Now root points to 30. and message 30 pushed to stack is printed.
pop always pops out the element which is pointed by root. So it will pop out 30 So 30 popped from stack is printed and now root points to next element i.e. 20.
peek shows the element at root which is 20. So Top element is 20 is printed.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.