Class 12 Stacks Queues and Linked List Revision Notes

This Class 12 Computer Science revision note on Stacks, Queues and Linked List explains the LIFO and FIFO data structures, the basic operations on a linked list (insertion, deletion and traversal), and the C++ implementation of a linked stack and a linked queue. It also includes board-style questions on deleting nodes and evaluating or converting expressions with a stack.

STACKS, QUEUES AND LINKED LIST

Stack

In computer science, a stack is a Last In, First Out (LIFO) data structure. It simply means that an element that is inserted at the end will be deleted first. To manage a stack, all the insertion and deletion takes place from one position called "top".
One of the common uses of a stack is in function calls.

Operations on the Stack

There are two fundamental operations:
Push: means to insert an element.
Pop: means to delete an element.

Queue

In computer science, a queue is a First In, First Out (FIFO) data structure. It simply means that an element that is inserted at the beginning will be deleted first. To manage a queue, all the insertion and deletion takes place from two different positions called "front" and "rear".
Every element is inserted from the rear position and deleted from the front position in the queue.

Linked List

A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data item and a reference (in other words, a link) to the next node in the sequence. More complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.

[Figure: Linked list with three nodes and a terminator. Node 1 has data 12 and a link arrow to node 2. Node 2 has data 99 and a link arrow to node 3. Node 3 has data 37 and a link arrow to a terminator box shown as a cross (end of list).]

Here the figure is an example of a linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list.

Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, such as stacks and queues, though it is not uncommon to implement the other data structures directly without using a list as the basis of implementation.

The principal benefit of a linked list over an array is that the list elements can easily be inserted or removed without reallocation or reorganisation of the entire structure, because the data items need not be stored contiguously in memory or on disk. Linked lists allow insertion and removal of nodes at any point in the list, and can do so with a constant number of operations if the link previous to the link being added or removed is maintained during list traversal.

Linked lists are dynamic structures, where memory allocation takes place at run time.

Operation on a Linked List

There are three basic operations on a linked list:
Insertion
Deletion
Traversal

Inserting a node or element into a linked list

Inserting an element into a linked list has 3 types:
1. Insertion at the beginning of the linked list
2. Insertion after or before any element of the linked list
3. Insertion at the end of the linked list

Deleting a node from the linked list

A node can be deleted in 3 ways, similar to insertion:
1. Deleting a node from the beginning of the linked list
2. Deleting a node before or after an element from the linked list
3. Deleting a node from the end of the linked list

Implementation of stacks using a linked list

The stack which is implemented using a linked list is called a linked stack or dynamic stack.

#include<iostream.h>
#include<conio.h>
struct node
{
int data;
node * next;
};
class stack
{
node *top;
public:
stack()
{
top=NULL;
}
void stackpush();
void stackpop();
void displaystack();
};
void stack::stackpush()
{
node *ptr;
ptr=new node;
cout<<"Enter the element to be pushed"<<endl;
cin>>ptr->data;
if(top==NULL)
ptr->next=NULL;
else
ptr->next=top;
top=ptr;
}
void stack ::stackpop()
{
node *ptr;
ptr=new node;
ptr=top;
cout<<"The popped element is "<<ptr->data;
top=top->next;
delete ptr;
}
void stack :: displaystack()
{
node *ptr;
ptr=new node;
ptr=top;
cout<<"The stack is "<<endl;
while(ptr!=NULL)
{
cout<<ptr->data<<endl;
ptr=ptr->next;
}
}
void main()
{
clrscr();
char ans;
stack s1;
do
{
s1.stackpush();
cout<<"wish to continue "<<endl;
cin>>ans;
}while(ans=='y');
s1.displaystack();
cout<<"Press any key to pop an element"<<endl;
getch();
s1.stackpop();
getch();
}

Implementation of queues using a linked list

The queue which is implemented using a linked list is called a linked queue or dynamic queue.

#include<iostream.h>
#include<conio.h>
struct node
{
int data;
node * next;
};
class queue
{
node *front,*rear;
public:
queue()
{
rear=front=NULL;
}
void insqueue();
void delqueue();
void dispqueue();
};
void queue::insqueue()
{
node *ptr;
ptr=new node;
cout<<"Enter the element to be insert"<<endl;
cin>>ptr->data;
ptr->next=NULL;
if(rear==NULL)
front=rear=ptr;
else
{
rear->next=ptr;
rear=ptr;
}
}
void queue ::delqueue()
{
node *ptr;
ptr=new node;
ptr=front;
cout<<"The deleted element is "<<ptr->data;
if(front==rear)
front=rear=NULL;
else
front=front->next;
delete ptr;
}
void queue :: dispqueue()
{
node *ptr;
ptr=new node;
ptr=front;
cout<<"The queue is "<<endl;
while(ptr!=NULL)
{
cout<<ptr->data<<endl;
ptr=ptr->next;
}
}
void main()
{
clrscr();
char ans;
queue q1;
do
{
q1.insqueue();
cout<<"wish to continue "<<endl;
cin>>ans;
}while(ans=='y');
q1.dispqueue();
cout<<"Press any key to delete an element ...."<<endl;
getch();
q1.delqueue();
getch();
}

Some Questions based on Board Examination: Linked Stack and Linked Queue

Q1. Write a function in C++ to delete a node containing customer's information, from a dynamically allocated Queue of Customers implemented with the help of the following structure:
struct Customer
{
int CNo;
char CName[20];
Customer *Link;
};

Answer:
struct Customer
{
int CNo;
char CName[20];
Customer *Link;
} *Front, *Rear, *ptr;
void DELETE()
{
if(Front == NULL)
cout<<"\n Queue Underflow\n";
else
{
ptr = Front;
if(Front == Rear)
Front = Rear = NULL;
else
Front = Front->Link;
delete ptr;
}
}

Teacher's Note:
a) The printed answer used "Front = FrontLink", which is not valid C++; the correct statement is Front = Front->Link.
b) The printed answer also had "==" written as "= =" and used curly quotes, which must be corrected before compiling.
c) When only one customer is in the queue, Front and Rear must both become NULL, otherwise Rear keeps a deleted node.

Q2. Write a function in C++ to delete a node containing Book's information, from a dynamically allocated Stack of Books implemented with the help of the following structure.
struct Book
{
int BNo;
char BName[20];
Book *Next;
};

Answer:
struct Book
{
int BNo;
char BName[20];
Book *Next;
}*Front, *Rear, *ptr;
void POP()
{
if(Front == NULL)
cout<<"\n Stack Underflow\n";
else
{
ptr = Front;
Front = Front->Next;
delete ptr;
}
}

Teacher's Note:
a) The printed answer used "Front = Front→Link", but the structure has a field named Next, so the correct statement is Front = Front->Next.
b) In a stack, the top element is kept in Front, so only one pointer is needed for deletion.

Q 3. Evaluate the postfix notaion of expression.
4, 10 , 5 , + , * , 15 , 3 ,/ , -

Answer:
1. Scan the postfix expression from left to right and push each operand on the stack.
2. When an operator is read, pop the top two operands, apply the operator, and push the result back.
3. Push 4, 10 and 5. The stack is [4, 10, 5].
4. Read +: pop 5 and 10, compute 10 + 5 = 15, push 15. The stack is [4, 15].
5. Read *: pop 15 and 4, compute 4 × 15 = 60, push 60. The stack is [60].
6. Push 15 and 3. The stack is [60, 15, 3].
7. Read /: pop 3 and 15, compute 15 / 3 = 5, push 5. The stack is [60, 5].
8. Read -: pop 5 and 60, compute 60 - 5 = 55, push 55.
9. The final value is 55.

Teacher's Note:
a) An operand is pushed, and an operator always works on the top two values.
b) Keep the order of the two popped values: the first one popped is the right operand.
c) The stack shows the operands waiting to be used, which makes the working easy to check.

Q. 4. Convert the following infix expression to its equivalent postfix expression, showing the stack contents for each step of conversion.
X / Y + U* (V-W)

Answer:
1. X / Y + U* (V-W) = ((X / Y) + (U * (V - W)))
2. Scan the expression from left to right. Operands go straight to the postfix output. Operators are pushed on the stack, and a closing bracket pops operators up to the matching opening bracket.

Postfix expression: X / Y + U * (V-W) = XY/UVW-*+

Teacher's Note:
a) An opening bracket is pushed and is removed only when its closing bracket is read.
b) Operators with higher precedence, such as * and /, are placed in postfix before + and -.
c) The printed working kept the outer bracket out of the stack column; the stack shown here is the exact content after each step.