# Stacks and Queues using linked list

Concept of Stack and Queue

1. Stack :

Now stack works on the concept of LIFO , which means last element in will be the first element out . For only understanding purpose we take stack to be horizontal ,

For our conceptual understanding consider a stack of plates example , you have to put plate one after another and can only take the top most plate out .

Now there are a few functions you should know about stacks , there are a few functions :

1. Push (): it enters value into stack ,
2. Pop() :it remove the top value of the stack
3. Display () : to display the stack

firstly the array approach to make you understand the concept of stacks

`````` int item, choice, i;
int stack;
int top = 0;//we start from the zero index ,
int exit = 0;//for the do-while condition

cout << "\nStack using array ";
do {
cout << "\n1.Push \n2.Pop \n3.Display \nOthers to exit";
cout << "\nEnter Your Choice : ";
cin>>choice;
switch (choice) {
case 1:
if (top == 10)
cout << "\n Stack is Full!";
else {
cout << "\nEnter The Value to be pushed : ";
cin>>item;
cout << "\n Position : " << top << ", Pushed Value  :" << item;
stack[top++] = item;
}
break;
case 2:
if (top == 0)
cout << "\n Stack is Empty!";
else {
--top;
cout << "\n Position : " << top << ", Popped Value  :" << stack[top];
}
break;
case 3:
cout << "\n Stack Size : " << top;
for (i = (top - 1); i >= 0; i--)
cout << "\n Position : " << i << ", Value  :" << stack[i];
break;
default:
exit = 1;
break;
}
} while (exit==0);``````

Now the problem with Stack array was that , it was not scalable , our problems our going to be static in nature .Hence we use Linked list approach or vector approach or Dynamic memory allocation approach to counter this ,

our class’s will look like this,

Our code snippet will be ,

``````void Stack ::push(int x,int counter)
{
node * newnode= new node(x);
newnode->next=top;
top=newnode;
if(counter==0)
{
bottom =newnode ;
//value of bottomest node , it's not used but if you want to find the value of it then
}
}

int Stack ::isEmpty()
{
return (top==NULL);
}

void Stack::pop()
{
int n = top->data;
node *temp=top;
top=top->next;
cout<<"value "<<n<<" is deleted ";
free (temp);
}
void Stack::Display(Stack s1)
{

node * current_node1=s1.top;
while (current_node1!=NULL)
{
cout<<current_node1->data<<"\t";
current_node1=current_node1->next;
}

}``````

2.Queue :

Now Queue works on the concept of first element pushed will be last element to be first out , for conceptual reasons we use queue to be Vertical,

For our conceptual understanding , we use an example of a line at a store , the first person who arrived gets served first ,

Now there are a few functions you should know about queue , there are a few functions :

1. Push (): it enters value into queue
2. Pop() :it remove the top value of the queue
3. Display () : to display the queue

First lets take an easy implementation of queue using array ,

``````   int item, choice, i;
int queue;
int rear = 0;///rear index of queue
int front = 0;//front index of queue
int exit = 0;

cout << "\n Queue using array";
do {
cout << "\n1.Insert \n2.Remove \n3.Display \nOthers to exit";
cout << "\nEnter Your Choice : ";
cin>>choice;
switch (choice) {
case 1:
if (rear == 10)
cout << "\nQueue Reached Max!!";
else {
cout << "\nEnter The Value to be Insert : ";
cin>>item;
cout << "\nPosition : " << rear + 1 << " , Insert Value  : " << item;
queue[rear++] = item;
}
break;
case 2:
if (front == rear)
cout << "\n## Queue is Empty!";
else {
cout << "\nPosition : " << front << " , Remove Value  :" << queue[front];
front++;
}
break;
case 3:
cout << "\nQueue Size : " << (rear - front);
for (i = front; i < rear; i++)
cout << "\nPosition : " << i << " , Value  : " << queue[i];
break;
default:
exit = 1;
break;
}
} while (exit!=0);
``````

Now the problem with queue array was that , it was not scalable , our problems our going to be static in nature .Hence we use Linked list approach or vector approach or Dynamic memory allocation approach to counter this ,

our code snippet is ,

``````
int Queue ::isEmpty()
{
return (front==NULL);
}

void Queue :: enque(int x)
{
node * newnode= new node(x);
if(isEmpty()!=0)
front=rear=newnode;
else
{
rear->next=newnode;
rear=newnode;
}
}

void Queue::deque()
{
int n = front->data;
node *temp=front;
front=front->next;
cout<<"value "<<n<<" is deleted ";
free (temp);
if(front==NULL)
rear=front;
}
void Queue::Display(Queue q1)
{

node * current_node1=q1.front;
while (current_node1!=NULL)
{
cout<<current_node1->data<<"\t";
current_node1=current_node1->next;
}

}``````

## 4 thoughts on “Stacks and Queues using linked list”

1. Cathleen says:

Very good information. Lucky me I found your website by accident
(stumbleupon). I’ve book-marked it for later!

Like

2. Credit Repair Chicago says:

Fine way of explaining, and nice piece of writing to get information on the topic of my presentation subject matter, which i am going to deliver
in institution of higher education.

Like