Objective:C++ program for stack ADT using linked list implementation.
Concept: A stack data structure can be implemented by using linked list data structure. The stack implemented using linked list can work for unlimited number of values. That means, stack implemented using linked list works for variable size of data. So, there is no need to fix the size at the beginning of the implementation. The Stack implemented using linked list can organize as many data values as we want. In linked list implementation of a stack, every new element is inserted as ‘top’ element. That means every newly inserted element is pointed by ‘top’. Whenever we want to remove an element from the stack, simply remove the node which is pointed by ‘top’ by moving ‘top’ to its next node in the list. The next field of the first element must be always NULL.
ALGORITHM:
1. Define a struct for each node in the stack. Each node in the stack contains data and link to the next node. TOP pointer points to last node inserted in the stack.
2. The operations on the stack are
a. PUSH data into the stack
b. POP data out of stack
3. PUSH DATA INTO STACK
a. Enter the data to be inserted into stack.
b. If TOP is NULL
i. The input data is the first node in stack.
ii. The link of the node is NULL.
iii. TOP points to that node.
c. If TOP is NOT NULL
i. The link of TOP points to the new node.
ii. TOP points to that node.
4. POP DATA FROM STACK
a. 4a. If TOP is NULL
i. the stack is empty
b. 4b.If TOP is NOT NULL
i. The link of TOP is the current TOP.
ii. The pervious TOP is popped from stack.
5. The stack represented by linked list is traversed to display its content.
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
class Linked_list_Stack
{
private:
struct node
{
int data;
node *next;
};
node *top;
node *entry;
node *print;
node *bottom;
node *last_entry;
node *second_last_entry;
public:
Linked_list_Stack( );
void pop( );
void push( );
void print_list( );
void show_working( );
};
Linked_list_Stack::Linked_list_Stack ( )
{
top=NULL;
bottom=NULL;
}
void Linked_list_Stack::push( )
{
int num;
cout<<"\n\t Enter value to push onto Stack : ";
cin>>num;
entry=new node;
if(bottom==NULL)
{
entry->data=num;
entry->next=NULL;
bottom=entry;
top=entry;
}
else
{
entry->data=num;
entry->next=NULL;
top->next=entry;
top=entry;
}
cout<<"\n\t *** "<
Stack."<
}
void Linked_list_Stack::pop( )
{
if(bottom==NULL)
cout<<"\n\t *** Error : Stack is empty. \n"<
else
{
for(last_entry=bottom;last_entry->next!=NULL;
last_entry=last_entry->next)
second_last_entry=last_entry;
if(top==bottom)
bottom=NULL;
int poped_element=top->data;
delete top;
top=second_last_entry;
top->next=NULL;
cout<<"\n\t *** "<
the Stack."<
}
}
void Linked_list_Stack::print_list( )
{
print=bottom;
if(print!=NULL)
cout<<"\n\t Values pushed onto Stack are : \n"<
else
cout<<"\n\t *** Nothing to show. "<
while(print!=NULL)
{
cout<<"\t "<data<
print=print->next;
}
}
void Linked_list_Stack::show_working( )
{
int choice;
clrscr( );
cout<<"\n\n********** Implementation of Linked List as a
Stack **********"<
cout<<"\n1.Push elements to stack"<
cout<<"2.Pop elements to stack"<
cout<<"3.Print the elements of stack"<
cout<<"4.Exit"<
do
{
cout<<"\nEnter your Choice : ";
cin>>choice;
switch(choice)
{
case 1: push();
break;
case 2: pop();
break;
case 3: print_list( );
break;
case 4: exit(0);
break;
default:
cout<<"enter the valid choice";
}
}while(1);
}
int main( )
{
Linked_list_Stack obj;
obj.show_working( );
return 0;
}