Linked List Representation of Stack

• Linked list is the another way of Stack Implementation.
• Push and Pop Operation will be apply at the beginning(front) of List.
• Linked List representation is something good approach,because it is growable and shrinkable as per requirements.
• HeadPointer of Linked list work as a top variable for pointing the stack pointer.
• Linked List Representation of Stack is similar to the Insertion of node at beginning(front) in Singly Linked List.

Push & Pop (Insertion & Deletion Operation)

Working process of Push and Pop operations are following :

Code Implementation

#include <stdio.h>
#include <iostream>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
struct CreateNode   // Node Structure Initialization
{
	int  data;          // for data element
	struct CreateNode* nextNode;   //for storing the address of next element
};
struct CreateNode *top = NULL;    // Initialization of HeadPointer/front
void Push(int data)   // Method of Push Operation
{
	//Memory Initialization for NewNode
	struct CreateNode* NewNode = (struct CreateNode *)malloc(sizeof(struct CreateNode *));
	if (NewNode != NULL)
	{
		if (top == NULL)
		{
			NewNode->data = data;
			top = NewNode;
			NewNode->nextNode = NULL;
			printf("DataElement %d has been Pushed into Stack...\n", data);
		}
		else
		{
			NewNode->data = data;
			NewNode->nextNode = top;
			top = NewNode;
			printf("DataElement %d has been Pushed into Stack...\n", data);
		}
	}
	else
	{
		printf("Memory is not Initialized for New DataElement.");
	}
}
bool IsEmptyStack()    // Method to check the Empty status of Stack.
{
	return top == NULL;
}
void Pop()   // Method of Pop Operation
{
	if (!IsEmptyStack())
	{
		struct CreateNode* TempNode = NULL;  // Create one TempNode 
		TempNode = top;
		top = top->nextNode;
		printf("%d is popped from the stack\n ", TempNode->data);
		free(TempNode);  // delete the front node or Memory deallocation of front node.
	}
	else
		printf("Stack is in the Underflow Condition...");
}
int main()
{
	int data, choice, ChoosePushPop;
	do
	{
		printf("1 : for Push Operation\n");
		printf("2 : for Pop  Operation\n");
		printf("Press 1 or 2 --- : ");
		std::cin >> ChoosePushPop;
		switch (ChoosePushPop)
		{
		case 1:
			do
			{
				printf("Enter the data for Push :");
				std::cin >> data;
				Push(data);
				printf("Press 0 for more Push :");
				std::cin >> choice;
			} while (choice == 0);
			break;
		case 2:
			do
			{
				Pop();
				printf("\nPress 0 for more Pop Operation :");
				std::cin >> choice;
			} while (choice == 0);
			break;
		}
	} while (ChoosePushPop == 1 || ChoosePushPop == 2);

	printf("DataElement after Push/Pop process :\n");
	struct CreateNode *Temp = top;
	while (Temp->nextNode != NULL)
	{
		printf("%d ", Temp->data);
		Temp = Temp->nextNode;
	}
	printf("%d ", Temp->data);
	_getch();
	return 0;
}

Time & Space Complexity

• Push Operation Time Complexity will be O(1).
• Pop Operation Time Complexity will be O(1).
• IsEmptyStack Time Complexity will be O(1).
• IsFullStack Time Complexity will be O(1).
• Space Complexity will be O(n).