Saltar al contenido
Contact : alejandrasalcedo0288@gmail.com

Difference between linear and circular tail


A simple linear queue can be implemented in several ways, among which one of the types is a circular tail. The difference between the linear and the circular tail lies in the structural and performance factors. The essential difference between the linear tail and the circular tail is that the linear tail consumes more space than the circular tail, while the circular tail is designed to limit the memory waste of the linear tail.

The tail It can be described as a non-primitive linear data structure that follows the FIFO order in which data elements are inserted from one end (back) and removed from the other end (front end). The other variations of the queue are the circular queue, the double ending queue and the priority queue.

Comparative graph

Basis for comparison Linear circle Circular circle
BASICOrganize the data elements and instructions in sequential order one after another.Organize the data in the circular pattern where the last element is connected to the first element.
Task Execution OrderThe tasks are executed in the order they were placed before (FIFO).The order of execution of a task may change.
Insertion and disposalThe new item is added from the back and removed from the front.Insertion and removal can be done in any position.
ActingInefficientIt works better than the linear tail.

Linear tail definition

A linear tail It is rationally a list of first in get in, first out . It is called as linear because it resembles a straight line where the elements are placed one after the other. It contains a homogeneous collection of the elements in which new elements are added at one end and removed from another end. The concept of the queue can be understood by the example of a queue from the audience waiting outside the ticket counter to obtain the theater ticket. In this queue, the person joins at the end of the queue to take the ticket and the ticket is issued at the front of the queue.

There are several operations performed in the queue.

  • First, the queue is initialized to zero (that is, this cow).
  • Determine if the tail is vacant or not.
  • Determine if the tail is full or not.
  • Insertion of the new element from the back (Glue).
  • Deleting the element from the front end (Dequeue).

The queue can be implemented in two ways.

  • Aesthetically (using matrices)
  • Dynamically (using pointers)

The limitation of the linear queue is that it creates a scenario in which no new element can be added to the queue, even if the queue contains the empty spaces. This previous situation is illustrated in the figure below. Here, the backside points to the last index, while all the boxes are still empty, no new items can be added.

Definition of the circular tail

A circular tail It is a variant of the linear tail that exceeds the limitation of the linear tail. In the circular queue, the new element is added to the first position of the queue if the last one is occupied and there is space available. When it comes to a linear tail, the insertion can be done only from the rear and the removal from the front. In a complete queue after performing a series of successive deletions in the queue, a situation arises in which no new element can be added, even if the space available because the overflow condition (Rear = max – 1) still exists .

The circular tail connects the two ends through a pointer where the first element comes after the last element. It also tracks the front and rear by implementing an additional logic so you can track the items that will be inserted and removed. With this, the circular tail does not generate the overflow condition until the tail is full in real.

Some conditions followed by the circular tail:

  • Front should point to the first element.
  • The queue will be empty if Front = Rear.
  • When a new element is added, the queue is incremented by the value one (Posterior = Posterior + 1).
  • When an element is removed from the queue, the front is increased by one (Front = Front + 1).

Key differences between linear and circular tail

  1. The linear queue is an ordered list in which the data elements are organized in sequential order. On the contrary, the circular queue stores the data in a circular way.
  2. The linear queue follows the FIFO order to execute the task (the element added in the first position will be deleted in the first position). Conversely, in the circular queue, the order of operations performed on an item may change.
  3. The insertion and elimination of the elements is fixed in the linear tail, that is, the addition from the back and the elimination from the front. On the other hand, the circular tail is able to insert and remove the element from any point until it is unoccupied.
  4. The linear queue wastes memory space, while the circular queue makes space efficient.

Linear queue implementation.

The algorithm given below illustrates the addiction of elements in a queue: The queue needs three data variables, including an array to store the queue and another to store the initial front and rear position that is -1.

 inserte (elemento, cola, n, parte trasera) {si (parte trasera == n) luego imprima "cola de desbordamiento"; else {trasero = trasero + 1; queue (rear) = item; }} 

The algorithm given below illustrates the elimination of items in a queue:

 delete_circular (artculo, cola, parte trasera, parte delantera) {if (parte trasera == parte delantera) luego imprima "cola de flujo insuficiente"; else {front = front + 1; item = queue (front); }} 

Implementation of the circular tail.

An algorithm to interpret the addiction of the element in the circular tail:

 insert_circular (artculo, cola, trasero, delantero) {trasero = (trasero + 1) mod n; if (front == rear) luego imprima "la cola est llena"; else {queue (rear) = item; }} 

The algorithm explains the elimination of the element in the circular tail:

 delete_circular (item, queue, rear, front) {if (front == rear) luego print ("la cola est vaca"); else {front = front + 1; item = queue (front); }} 

Conclusion

The linear tail is inefficient in certain cases where the elements are required to move to the vacant spaces to perform the insertion operation. That is why it tends to waste storage space while the circular queue makes proper use of storage space, since the elements are added in any position if there is an empty space.

Rate this post