In this guide, we will explore the variance between Static Queue and Singly Linked List in C++. Prior to delving into their distinctions, it is essential to understand the Static Queue and Singly Linked List in C++, including their functions and an illustrative example.
What is the Static Queue?
Static queues are a fundamental form of data structure employed for organizing and controlling sets of items based on the First-In-First-Out (FIFO) concept.
Items are inserted at one extremity of a fixed queue (referred to as the rear or tail) and taken out from the other end (referred to as the head or front). The element added first is always the first to be retrieved due to the fixed Queue preserving the sequence of element addition.
Arrays represent data structures with a set capacity and unchanging size commonly employed for constructing static queues. Static queues, distinct from dynamic queues, maintain a consistent size that cannot be altered during program execution. While dynamic queues offer increased flexibility, static queues prove beneficial in scenarios where memory optimization is crucial, and the quantity of elements is predetermined.
Some benefits of fixed queues consist of their simple establishment, efficiency in memory usage, and consistent performance. They eliminate the necessity for reallocating or managing dynamic memory since the memory allocation is predetermined and remains unchanged, minimizing extra tasks and preventing memory fragmentation.
Additionally, the add and remove functions of fixed queues offer O(1) time complexity as they involve basic array indexing and pointer adjustments. It is crucial to be mindful of the constraints associated with static queues. Due to their predetermined capacity, these queues can only store a set number of elements, potentially resulting in wasted memory if not fully occupied or inadequate space if the size exceeds requirements. Moreover, resizing a static queue can be more challenging and less efficient compared to dynamic queues since it involves adjusting the array size.
Functions of the Static Queue:
The following are the main functions that a static queue supports:
- Enqueue: Adding an item to the rear of the Queue is known as enqueue. The rear pointer is incremented to the next available position once an element is inserted into the Array at the Position specified by the rear pointer. If the Array has space, enqueue operations are performed in constant time O(1).
- Dequeue: Removing an item from the front of the Queue is known as dequeue. By incrementing the froncpp tutorialer to the next element in the Queue, the element at the position specified by the froncpp tutorialer is removed during this operation. Also performed in constant time O(1) are dequeue operations.
- Front: Retrieving the element at the head of the Queue without removing it. This operation allows users to peek at the element that would be dequeued next. The front operation performs in O(1) constant time.
- IsEmpty: Determines whether the Queue is empty. If there are no elements in the Queue, this operation returns true; otherwise, it returns false. The IsEmpty function performs in O(1) constant time.
- IsFull: Determining whether there is a full queue. If the number of elements in the Queue equals the Array's capacity, which indicates that the Queue is full, this operation returns true since the Array's size is fixed.
Example:
Let's consider an example to demonstrate the concept of a static queue in C++.
#include <iostream>
#define MAX_SIZE 100
// Maximum size of the Queue
class StaticQueue
{
private:
int data[MAX_SIZE];
//Array for storing queue elements
int front;
//Index of the front element
int rear;
//Index of the rear element
public:
// Constructor for the Queue's initialization
StaticQueue()
{
front = -1;
//Initialize the front Index
rear = -1;
//Initialize the rear index
}
// Function to verify whether the Queue is empty
bool isEmpty()
{
return front == -1;
//Queue is empty if the front is equal to -1
}
// Function to verify if the Queue is full
bool isFull()
{
return (rear + 1) % MAX_SIZE == front;
//Queue is full if the rear is one Position before the front
}
// Function to enqueue an element to the rear of the Queue
void enqueue(int ele)
{
if (isFull())
{
std::cout << "The Queue is full. Cannot enqueue the elements.\n";
return;
}
if (isEmpty())
{
front = 0;
// If the Queue is empty, set the front to 0
}
rear = (rear + 1) % MAX_SIZE;
// Move rear circularly.
data[rear] = ele;
// Insert element at rear
std::cout << "The enqueued element is: " << ele << std::endl;
}
// Function to dequeue an element from the front of the Queue
void dequeue()
{
if (isEmpty())
{
std::cout << "Queue is empty. Cannot dequeue element.\n";
return;
}
int d = data[front];
// Get the element at the front
if (front == rear)
{
front = -1;
// If there is only one element in the Queue, reset the front and rear
rear = -1;
}
else
{
front = (front + 1) % MAX_SIZE;
// Move front circularly
}
std::cout << "The dequeued element is: " << d << std::endl;
}
// Function to display the elements of the Queue.
void display()
{
if (isEmpty())
{
std::cout << "Queue is empty.\n";
return;
}
std::cout << "The Queue elements are: ";
int m = front;
do {
std::cout << data[m] << " ";
m = (m + 1) % MAX_SIZE;
// Move to the next element circularly.
} while (m != (rear + 1) % MAX_SIZE);
// Loop continues until the rear element is reached.
std::cout << std::endl;
}
};
int main()
{
StaticQueue q;
q.enqueue(20);
q.enqueue(29);
q.enqueue(38);
q.enqueue(42);
q.display();
q.dequeue();
q.dequeue();
q.display();
q.enqueue(57);
q.enqueue(64);
q.display();
return 0;
}
Output:
The enqueued element is: 20
The enqueued element is: 29
The enqueued element is: 38
The enqueued element is: 42
The Queue elements are: 20 29 38 42
The dequeued element is: 20
The dequeued element is: 29
The Queue elements are: 38 42
The enqueued element is: 57
The enqueued element is: 64
The Queue elements are: 38 42 57 64
Explanation:
This C++ script utilizes an array to define the functionality of a static queue data structure. By employing an array to hold data elements and utilizing integer variables front and rear to indicate the Queue's front and rear positions, the StaticQueue class encapsulates the Queue's operations. Within the class, there are functions available to check if the Queue is empty or full, to add elements to the front of the Queue (enqueue), to remove elements from the rear of the Queue (dequeue), and to exhibit the elements within the Queue. In the main function, a static queue named q is instantiated to showcase the queue operations, including enqueuing, dequeuing, and displaying elements. The Queue's circular behavior is maintained, ensuring that elements are efficiently managed using circular array indexing.
What is the Singly LinkedList?
In C++, a key data structure for efficiently handling and structuring a group of items is known as a singly linked list. This list comprises nodes, each consisting of two components: data and a pointer or reference to the subsequent node in the series. This setup allows for efficient operations like adding, removing, navigating, and finding elements, and facilitates the utilization of dynamic memory allocation. The ability to dynamically allocate memory is a primary advantage of singly linked lists.
Memory can be efficiently utilized and controlled by dynamically allocating nodes as needed. This feature is particularly beneficial when the size of the ListList is unpredictable or varies greatly during runtime.
Adding and removing elements in a ListList is typically efficient as it doesn't involve resizing or shifting existing elements. This allows for easy customization of list sizes to suit specific application needs.
Iterating through a singly linked list involves starting at the initial head node and sequentially moving through each subsequent node by following the pointers until reaching the end of the ListList. This approach facilitates tasks such as locating specific values or conducting computations on the stored information, allowing for effective access to all data elements.
However, there are specific constraints associated with singly linked lists too. Retrieving an element involves navigating the linked list from the start since linked lists do not offer direct access to elements based on their index, unlike arrays. Moreover, singly linked lists necessitate extra memory allocation for storing pointers, which can affect both memory consumption and efficiency when compared to contiguous data structures such as arrays.
Example:
Let's consider an example to demonstrate the Singly Linked List concept in C++.
#include <iostream>
//Creating a node structure
struct Node
{
int node_data;
Node* next;
//Constructor
Node(int d) : node_data(d), next(nullptr) {}
};
//Creating a Linked List class
class LinkedList
{
private:
Node* head;
public:
// Constructor of the class
LinkedList() : head(nullptr) {}
// Destructor of the class
~LinkedList()
{
Node* curr_ent = head;
while (curr_ent != nullptr)
{
Node* next = curr_ent->next;
delete curr_ent;
curr_ent = next;
}
head = nullptr;
}
//Insertion at the beginning
void InsertingAtBeginning(int new_data)
{
Node* new_Node = new Node(new_data);
new_Node->next = head;
head = new_Node;
}
//Insertion at the end
void InsertingAtEnd(int new_data)
{
Node* new_Node = new Node(new_data);
if (head == nullptr)
{
head = new_Node;
}
else
{
Node* curr_ent = head;
while (curr_ent->next != nullptr)
{
curr_ent = curr_ent->next;
}
curr_ent->next = new_Node;
}
}
// Display the linked ListList
void Display()
{
Node* curr_ent = head;
while (curr_ent != nullptr)
{
std::cout << curr_ent->node_data << " ";
curr_ent = curr_ent->next;
}
std::cout << std::endl;
}
// Searching for a value
bool search(int key_element)
{
Node* curr_ent = head;
while (curr_ent != nullptr)
{
if (curr_ent->node_data == key_element)
{
return true;
}
curr_ent = curr_ent->next;
}
return false;
}
// Deleting a value at the beginning
void DeletingAtBeginning()
{
if (head == nullptr)
{
std::cout << "ListList is empty. Cannot delete the element." << std::endl;
return;
}
Node* t = head;
head = head->next;
delete t;
}
// Deleting a value at a specific position
void DeletingAtPosition(int p)
{
if (head == nullptr)
{
std::cout << "ListList is empty. Cannot delete the element." << std::endl;
return;
}
if (p == 0)
{
DeletingAtBeginning();
return;
}
Node* curr_ent = head;
Node* prev = nullptr;
int index = 0;
while (curr_ent != nullptr && index != p)
{
prev = curr_ent;
curr_ent = curr_ent->next;
index++;
}
if (curr_ent == nullptr)
{
std::cout << "Position is out of range. Cannot delete the element." << std::endl;
return;
}
prev->next = curr_ent->next;
delete curr_ent;
}
};
int main()
{
LinkedList l;
// Inserting some elements
l.InsertingAtEnd(15);
l.InsertingAtEnd(24);
l.InsertingAtEnd(38);
// Displaying the ListList of elements
std::cout << "The Linked List elements are: ";
l.Display();
// Inserting an element at the beginning
l.InsertingAtBeginning(1);
std::cout << "After inserting elements at the beginning is: ";
l.Display();
// Deleting an element at a position
l.DeletingAtPosition(2);
std::cout << "After deleting element at position 2: ";
l.Display();
// Searching for an element
int key_element = 38;
if (l.search(key_element))
{
std::cout << key_element << " element is found in the list." << std::endl;
}
else
{
std::cout << key_element << " element is not found in the list." << std::endl;
}
// Deleting an element at the beginning
l.DeletingAtBeginning();
std::cout << "After deleting the element at the beginning, it is: ";
l.Display();
return 0;
}
Output:
The Linked List elements are: 15 24 38
After inserting elements at the beginning is: 1 15 24 38
After deleting element at position 2: 1 15 38
38 element is found in the list.
After deleting the element at the beginning, it is: 15 38
Explanation:
This C++ script presents a singly linked list data structure along with its corresponding functionalities. Each node in the LinkedList is comprised of a Node structure that holds numeric data and a pointer to the subsequent node. The LinkedList is enclosed within the LinkedList class, which also encompasses functions for adding and removing elements at the start and end of the LinkedList, looking for a specific element, and exhibiting the LinkedList. In the main function, a linked list (l) is instantiated, with elements being added at its commencement, conclusion, and at particular positions, followed by a search operation for each element. Ultimately, an element is removed from the beginning. The LinkedList is exhibited at each step to illustrate the impact of these actions on each element.
Key differences between a Static Queue and a Singly Linked List in C++
The variances between a singly linked list and a fixed queue regarding implementation, memory handling, functionalities, time complexity, adaptability, usage, additional costs, and implementation intricacy are succinctly outlined in the following table.
| Feature | Static Queue | Single Linked List |
|---|---|---|
| Memory Organization | Memory allocation is contiguous. | Memory allocation is non-contiguous. |
Size |
Size is fixed. | Size is dynamic. |
| Type of Information | A single type of information or data is stored. | Stores reference to next nodes and data. |
| Type of Data Structure | Utilizing arrays for implementation. | Utilizing pointers and nodes for implementation. |
| Access Method | Index Method | Reference Method |
| Insertion and Deletion | An element can be inserted or deleted at fixed ends (front and rear). | Anywhere in the ListList is where an element can be inserted or deleted. |
| Ordering | FIFO (First in First Out) First inserted element first deleted out. | Ordering can be in FIFO or LIFO. |
| Pointers | Two pointers (Front and Rear). | Single pointer (Head). |
