UNIT IV

Queues: Introduction to Queues, Representation of Queues-using Arrays and using Linked list,
Implementation of Queues-using Arrays and using Linked list, Application of Queues-Circular
Queues, Deques, Priority Queues, Multiple Queues.
Queues:
1. Introduction to Queues
• A queue is a linear data structure, in which elements are inserted at one end called ‘rare’ and
deleted from one end called ‘front’.
• A queue is a FIFO (First In First Out) data structure where first entered element is removed
out first.
• A good example of a queue is any queue of consumers for a resource where the consumer
that came first is served first.

2. Representation of Queues
Queues are represented in two ways. They are:
1. Array Representation
2. Linked list Representation
1. Array Representation:
• Queues can be easily represented using linear arrays
• Every queue has front and rear variables that point to the position from where deletions and
insertions can be done, respectively.
• Initially, the value of front and queue is -1 which represents an empty queue.
• Array representation of a queue containing 5 elements along with the respective values of
front and rear, is shown in the following figure.
 Array Representation of Queue

Operation on Queues
We have two types of operations on Queues. They are:
1. Insertion
2. Deletion
1. Insertion:

• FRONT = 0 and REAR = 5. Suppose we want to add another element with value 45, then
REAR would be incremented by 1 and the value would be stored at the position pointed by
REAR.
• Now FRONT = 0 and REAR = 6. Every time a new element has to be added, we repeat the
same procedure.
• Before inserting an element in a queue, we must check for overflow conditions. An
overflow will occur when we try to insert an element into a queue that is already full.
• When REAR = MAX – 1, where MAX is the size of the queue, we have an overflow
condition. We taken MAX – 1 because the index starts from 0.

Algorithm To Insert An Element In A Queue

Step 1: IF REAR = MAX-1

Write OVERFLOW Goto Step 4
[END OF IF]
Step 2: IF FRONT = -1 And REAR = -1
SET FRONT = REAR =
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: SET QUEUE[REAR] = NUM
Step 4: EXIT
// c program to implementation insert an element in a Queue

void insert (int queue[], int max, int front, int rear, int item)
{
if (rear + 1 == max)
{
printf("overflow");
}
else
{
if(front == -1 && rear == -1)
{
front = 0;
rear = 0;
}
else
{
rear = rear + 1;
}
queue[rear]=item;
} }

2. Deletion:

Queue after Deletion of an Element

• If we want to delete an element from the queue, then the value of FRONT will be
incremented. Deletions are done from only this end of the queue.
• Before deleting an element from a queue, we must check for underflow conditions. It
occurs when we try to delete an element from a queue that is already empty.
• If FRONT = –1 and REAR = –1, it means there is no element in the queue.

Algorithm to Delete an Element from a Queue

Step 1: IF FRONT = -1 OR FRONT > REAR
Write UNDERFLOW
ELSE
SET FRONT = FRONT + 1
[END OF IF]
Step 2: EXIT

// c program to implementation delete an element in a Queue

int delete (int queue[], int max, int front, int rear)
{
int y;
if (front == -1 || front > rear)
{
printf("underflow");
}
else
{
y = queue[front];
if(front == rear)
{
front = rear = -1;
else
front = front + 1;
}
return y;
}
}
2. Linked List Representation
• If Queue is a very small one or its maximum size is known in advance, then the array
implementation of the queue gives an efficient implementation. But if the array size cannot
be determined in advance, the other alternative, i.e., the linked representation is used.
• In a linked queue, every element has two parts, one that stores the data and another that
stores the address of the next element. The START pointer of the linked list is used as
FRONT. Here, we will also use another pointer called REAR, which will store the address
of the last element in the queue.
• All insertions will be done at the rear end and all the deletions will be done at the front
end. If FRONT = REAR = NULL, then it indicates that the queue is empty.

Linked Queue
Operation on Linked Queues
• A queue has two basic operations:
1. Insert
 2. Delete.
• The insert operation adds an element to the end of the queue, and the delete operation removes
an element from the front or the start of the queue.
• There is another operation peek which returns the value of the first element of the queue.
1. INSERT OPERATION:
• The insert operation is used to insert an element into a queue. The new element is added as
the last element of the queue.

• To insert an element with value 9, we first check if FRONT=NULL.

• If the queue is empty, we allocate memory for a new node, store the value in its data part and
NULL in its next part.
• The new node will then be called both FRONT and REAR.
• If FRONT!= NULL, then we will insert the new node at the rear end of the linked queue and
name this new node as rear.
• Thus the updated queue becomes as:

Linked after Inserting a New Node

Algorithm to Insert an Element in a Linked Queue:
Step 1: Allocate memory for the new node and name it as PTR
Step 2: SET PTR DATA = VAL
Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT NEXT = REAR NEXT = NULL
ELSE
SET REAR NEXT = PTR
SET REAR = PTR
SET REAR NEXT = NULL
[END OF IF]
Step 4: END
// c program to implementation insert an element in a Linked Queue

void insert(struct node *ptr, int item; )

{
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
return;
}
else
{
ptr -> data = item;
if(front == NULL)
{
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
else
{
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
}
}
}

2. DELETE OPERATION
• The delete operation is used to delete the element that is first inserted in a queue, i.e., the
element whose address is stored in FRONT.
• Before deleting the value, we must first check if FRONT=NULL, then the queue is empty
and no more deletions can be done.
• If we delete a value from a queue that is already empty, an underflow message is printed.
 • To delete an element, we first check if FRONT=NULL. If the condition is false, then we
delete the first node pointed by FRONT. The FRONT will now point to the second
element of the linked queue.
• Thus the updated queue becomes as:

Linked Queue after Deletion of an Element

Algorithm To Delete An Element From An Linked Queue

Step 1: IF FRONT = NULL

Write Underflow Go to Step5
[END OF IF]
Step 2: SET PTR = FRONT
Step 3: SET FRONT = FRONT -> NEXT

Step 4: FREE PTR

Step 5: END

// c program to implementation delete an element in a Linked Queue

void delete (struct node *ptr)

{
if(front == NULL)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
ptr = front;
front = front -> next;
free(ptr);
}
}
3. Implementation of Queues
Array implementation of queue:
• To implement a queue using array, create an array arr of size n and take two variables front
and rear both of which will be initialized to 0 which means the queue is currently empty.
• Element rear is the index upto which the elements are stored in the array and front is the index
of the first element of the array.
• Some of the implementation of queue operations are as follows:
1. Enqueue: Addition of an element to the queue.
2. Dequeue: Removal of an element from the queue.
3. Front: Get the front element from the queue
4. Display: Print all element of the queue.
C program to implement queue using array
#include<stdio.h>
#include<stdlib.h>
#define maxsize 5
void insert();
void delete();
void display();
int front = -1, rear = -1;
int queue[maxsize];
void main ()
{
int choice;
while(choice != 4)
{
printf("\n*************************Main Menu*****************************\n");
printf("\n========================================================\n");
printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");
printf("\nEnter your choice ?");
scanf("%d",&choice);
switch(choice)
{
case 1: insert();
break;
case 2: delete();
break;
case 3: display();
break;
case 4: exit(0);
break;
default: printf("\nEnter valid choice??\n");
}
}
}
void insert()
{
int item;
printf("\nEnter the element\n");
scanf("\n%d",&item);
if(rear == maxsize-1)
{
printf("\nOVERFLOW\n");
return;
}
if(front == -1 && rear == -1)
{
front = 0;
rear = 0;
}
else
{
rear = rear+1;
}
queue[rear] = item;
printf("\nValue inserted ");
}

void delete()
{
int item;
if (front == -1 || front > rear)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
item = queue[front];
if(front == rear)
{
front = -1;
rear = -1 ;
}
else
{
front = front + 1;
}
printf("\nvalue deleted ");
}
}
 void display()
{
int i;
if(rear == -1)
{
printf("\nEmpty queue\n");
}
else
{
printf("\nprinting values .....\n");
for(i=front;i<=rear;i++)
{
printf("\n%d\n",queue[i]);
}
}
}

Drawback of array implementation

The technique of creating a queue in array is easy, but there are some drawbacks of using this technique to
implement a queue.
1. Memory wastage: The space of the array, which is used to store queue elements, can never be
reused to store the elements of another elements because the elements can only be inserted at front
end and the value of front might be so high so that, all the space before that, can never be filled.

2. Deciding the array size:

 One of the most common problem with array implementation is the size of the array which
requires to be declared in advance.
 The queue can be extended at runtime depending upon the problem, the extension in the array
size is a time taking process and almost impossible to be performed at runtime since a lot of
reallocations take place.
  Due to this reason, we can declare the array large enough so that we can store queue elements
as enough as possible but the main problem with this declaration is that, most of the array slots
(nearly half) can never be reused. It will again lead to memory wastage

• Some of the implemention operations in queue using linked list are:

1. enQueue(): Inserting an element into the Queue
2. deQueue() - Deleting an Element from Queue
3. display() - Displaying the elements of Queue
C program to implement queue using linked list
#include<stdio.h>
#include<conio.h>
struct Node
{
int data;
struct Node *next;
}*front = NULL,*rear = NULL;
void insert(int);
void delete();
void display();
void main()
{
int choice, value;
clrscr();
printf("\n:: Queue Implementation using Linked List ::\n");
while(1){
printf("\n****** MENU ******\n");
printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("Enter the value to be insert: ");
scanf("%d", &value);
insert(value);
break;
case 2: delete(); break;
 case 3: display(); break;
case 4: exit(0);
default: printf("\nWrong selection!!! Please try again!!!\n");
}
}}
void insert(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode -> next = NULL;
if(front == NULL)
front = rear = newNode;
else
{
rear -> next = newNode;
rear = newNode;
}
printf("\nInsertion is Success!!!\n");
}
void delete()
{
if(front == NULL)
printf("\nQueue is Empty!!!\n");
else
{
struct Node *temp = front;
front = front -> next;
printf("\nDeleted element: %d\n", temp->data);
free(temp);
}
}
void display()
{
if(front == NULL)
printf("\nQueue is Empty!!!\n");
else
{
struct Node *temp = front;
while(temp->next != NULL){
printf("%d--->",temp->data);
temp = temp -> next;
}
printf("%d--->NULL\n",temp->data);
}}
Output:
4. APPLICATIONS OF QUEUES
A queue data structure can be classified into the following types:
1. Circular Queue 2. Deque 3. Priority Queue 4. Multiple Queues
1. CIRCULAR QUEUE:
 • In linear queues, we have discussed so far that insertions can be done only at one end called the
REAR and deletions are always done from the other end called the FRONT.

• Here, FRONT = 0 and REAR = 9.

• If you want to insert another value, it will not be possible because the queue is completely full.
There is no empty space where the value can be inserted.
• Consider two successive deletions are made.

• Here, front = 2 and REAR = 9.

• Suppose we want to insert a new element in the queue. Even though there is space available, the
overflow condition still exists because the condition rear = MAX – 1 still holds true. This is a
major drawback of a linear queue.
• To resolve this problem, we have two solutions. First, shift the elements to the left so that the
vacant space can be occupied and utilized efficiently. But this can be very time- consuming,
especially when the queue is quite large.
• The second option is to use a circular queue. In the circular queue, the first index comes right
after the last index.

• The circular queue will be full only when front = 0 and rear = Max – 1. A circular queue is
implemented in the same manner as a linear queue is implemented. It performs insertion and
deletion operations.
• For insertion, we have to check for the following three conditions:
1. If front = 0 and rear = MAX – 1, then the circular queue is full.

2. If rear != MAX – 1, then rear will be incremented and the value will be inserted
 3. If front != 0 and rear = MAX – 1, then it means that the queue is not full. So, set
rear = 0 and insert the new element there,

ALGORITHM TO INSERT AN ELEMENT IN CIRCULAR QUEUE

Step 1: IF FRONT = and Rear = MAX - 1
Write OVERFLOW
Goto step 4
[End OF IF]
STEP 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR =0
ELSE IF REAR = MAX - 1 and FRONT != 0 SET
REAR =0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: SET QUEUE [REAR] = VAL
Step 4: EXIT
• To delete an element, again we check for three conditions.
• If front = –1, then there are no elements in the queue. So, an underflow condition will be reported.

• If the queue is not empty and front = rear, then after deleting the element at the front the queue
becomes empty and so front and rear are set to –1.

• If the queue is not empty and front = MAX–1, then after deleting the element at the front,
front is set to 0.
 ALGORITHM TO DELETE AN ELEMENT IN CIRCULAR QUEUE
Step 1: IF FRONT = -1
Write UNDERFLOW
Goto Step 4
[END of IF]
Step 2: SET VAL = QUEUE [FRONT]
Step 3: IF FRONT = REAR
SET FRONT = REAR = -1 ELSE
IF FRONT = MAX -1
SET FRONT =0
ELSE
SET FRONT = FRONT + 1
[END OF IF]
[END OF IF]
Step 4: EXIT
C a program to implement a circular queue
#include <stdio.h>
#include <conio.h>
#define MAX 10
int queue[MAX];
int front= –1, rear= –1;
void insert(void);
int delete_element(void);
int peek(void);
void display(void);
int main()
{
int option, val;
clrscr();
do
{
printf("\n ***** MAIN MENU *****");
printf("\n 1. Insert an element"); printf("\n 2. Delete an element");
printf("\n 3. Peek");
printf("\n 4. Display the queue");
 printf("\n 5. EXIT");
printf("\n Enter your option : ");
scanf("%d", &option); switch(option)
{
case 1: insert(); break;
case 2: val = delete_element();
if(val!=–1)
printf("\n The number deleted is : %d", val); break;
case 3: val = peek();
if(val!=–1)
printf("\n The first value in queue is : %d", val); break;
case 4: display(); break;
}
}while(option!=5);
getch();
return 0;
}
void insert()
{
int num;
printf("\n Enter the number to be inserted in the queue : ");
scanf("%d", &num);
if(front==0 && rear==MAX–1)
printf("\n OVERFLOW");
else if(front==–1 && rear==–1)
{
front=rear=0;
queue[rear]=num;
}
else if(rear==MAX–1 && front!=0)
{
rear=0;
queue[rear]=num;
}
else
{
rear++; queue[rear]=num;
}
}
int delete_element()
{
int val;
if(front==–1 && rear==–1)
{
printf("\n UNDERFLOW"); return –1;
}
val = queue[front];
 if(front==rear)
front=rear=–1;
else
{
if(front==MAX–1)
front=0;
else
front++;
}
return val;
}
int peek()
{
if(front==–1 && rear==–1)
{
printf("\n QUEUE IS EMPTY");
return –1;
else
{
return queue[front];
}
}
void display()
{
int i;
printf("\n");
if (front ==–1 && rear= =–1)
printf ("\n QUEUE IS EMPTY");
else
{
if(front<rear)
{
for(i=front;i<=rear;i++)
printf("\t %d", queue[i]);
}
else
{
for(i=front;i<MAX;i++)
printf("\t %d", queue[i]);
for(i=0;i<=rear;i++)
printf("\t %d", queue[i]);
}
}
}
Output
***** MAIN MENU *****
 1. Insert an element
2. Delete an element
3. Peek
4. Display the queue
5. EXIT
Enter your option : 1
Enter the number to be inserted in the queue : 25
Enter your option : 2
The number deleted is : 25
Enter your option : 3
QUEUE IS EMPTY
Enter your option : 5

Applications:
1. Memory Management: The unused memory locations in the case of ordinary queues can be
utilized in circular queues.
2. Traffic system: In computer controlled traffic system, circular queues are used to switch on the
traffic lights one by one repeatedly as per the time set.
3. CPU Scheduling: Operating systems often maintain a queue of processes that are ready to execute
or that are waiting for a particular event to occur.
2. DEQUES:
• A deque is a list in which the elements can be inserted or deleted at either end.
• It is also known as a head-tail linked list because elements can be added to or removed from either
the front (head) or the back (tail) end.
• No element can be added and deleted from the middle.
• A deque is implemented using either a circular array or a circular doubly linked list.
• In a deque, two pointers are maintained, LEFT and RIGHT, which point to either end of the
deque.
• The elements in a deque extend from the LEFT end to the RIGHT end and since it is circular,
Dequeue[N–1] is followed by Dequeue[0].
 There are two variants of a double-ended queue. They include:
 Input restricted deque: In this dequeue, insertions can be done only at one of the ends,
while deletions can be done from both ends.
 Output restricted deque: In this dequeue, deletions can be done only at one of the ends,
while insertions can be done on both ends.
C program to implement input and output restricted deques.
#include <stdio.h>
#include <conio.h>
#define MAX 10 int
deque[MAX];
int left = –1, right = –1;
void input_deque(void);
void output_deque(void);
void insert_left(void);
void insert_right(void);
void delete_left(void);
void delete_right(void);
void display(void);
int main()
{
int option;
clrscr();
printf("\n *****MAIN MENU*****");
printf("\n 1.Input restricted deque");
printf("\n 2.Output restricted deque");
printf("Enter your option : ");
scanf("%d",&option);
switch(option)
{
case 1: input_deque();
break;
case 2: output_deque();
break;
}
return 0;
}
void input_deque()
{
int option;
do
 {
printf("\n INPUT RESTRICTED DEQUE");
printf("\n 1.Insert at right");
printf("\n 2.Delete from left");
printf("\n 3.Delete from right");
printf("\n 4.Display");
printf("\n 5.Quit");
printf("\n Enter your option : ");
scanf("%d",&option);
switch(option)
{
case 1: insert_right(); break;
case 2: delete_left(); break;
case 3: delete_right(); break;
case 4: display(); break;
}
}while(option!=5);
}
void output_deque()
{
int option;
do
{
printf("OUTPUT RESTRICTED DEQUE");
printf("\n 1.Insert at right");
printf("\n 2.Insert at left"); printf("\n 3.Delete from left");
printf("\n 4.Display");
printf("\n 5.Quit");
printf("\n Enter your option : ");
scanf("%d",&option);
switch(option)
{
case 1:insert_right();
break;
case 2: insert_left();
break;
case 3: delete_left();
break;
case 4: display(); break;
}
}while(option!=5);
}

void insert_right()
{
int val;
printf("\n Enter the value to be added:");
 scanf("%d", &val);
if((left == 0 && right == MAX–1) || (left == right+1))
{
printf("\n OVERFLOW");
return;
}
if (left == –1) /* if queue is initially empty */
{
left = 0;
right = 0;
}
else
{
if(right == MAX–1) /*right is at last position of queue */
right = 0;
else
right = right+1;
}
deque[right] = val ;
}

void insert_left()
{
int val;
printf("\n Enter the value to be added:");
scanf("%d", &val);
if((left == 0 && right == MAX–1) || (left == right+1))
{
printf("\n Overflow");
return;
}
if (left == –1)/*If queue is initially empty*/
{
left = 0;
right = 0;
}
else
{
if(left == 0)
left=MAX–1;
else
left=left–1;
}
deque[left] = val;
}
void delete_left()
{
 if (left == –1)
{
printf("\n UNDERFLOW");
return ;
}
printf("\n The deleted element is : %d", deque[left]);
if(left == right) /*Queue has only one element */
{
left = –1;
right = –1;
}
else
{
if(left == MAX–1)
left = 0;
else
left = left+1;
}
}

void delete_right()
{
if (left == –1)
{
printf("\n UNDERFLOW");
return ;
}
printf("\n The element deleted is : %d", deque[right]);
if(left == right) /*queue has only one element*/
{
left = –1;
right = –1;
}
else
{
if(right == 0)
right=MAX–1;
else
right=right–1;
}
}
void display()
{
int front = left, rear = right;
if(front == –1)
{
 printf("\n QUEUE IS EMPTY");
return;
}
printf("\n The elements of the queue are : ");
if(front <= rear )
{
while(front <= rear)
{
printf("%d",deque[front]);
front++;
}
}
else
{
while(front <= MAX–1)
{
printf("%d", deque[front]);
front++;
}
front = 0;
while(front <= rear)
{
printf("%d",deque[front]);
front++;
}
}
printf("\n");
}
Output
***** MAIN MENU *****
1.Input restricted deque
2.Output restricted deque
Enter your option : 1
INPUT RESTRICTED DEQUEUE
1.Insert at right
2.Delete from left
3.Delete from right
4.Display
5.Quit
Enter your option : 1
Enter the value to be added: 5
 Enter the value to be added: 10
Enter your option: 2
The deleted element is: 5
Enter your option: 5
3. PRIORITY QUEUES:
• A priority queue is a data structure in which each element is assigned a priority. The priority of
the element will be used to determine the order in which the elements will be processed.
• The general rules of processing the elements of a priority queue are
1. An element with higher priority is processed before an element with a lower priority.
2. Two elements with the same priority are processed on a first-come-first-served (FCFS) basis.
• When an element has to be removed from the queue, the one with the highest-priority is retrieved
first.
• In the computer memory, a priority queue can be represented using arrays or linked lists.
Linked Representation of a Priority Queue
• When a priority queue is implemented using a linked list, then every node of the list will
have three parts:
a) the information or data part,
b) the priority number of the element, and
c) the address of the next element.

• Lower priority number means higher priority

• The priority queue in is a sorted priority queue having six elements.
• In the queue, we cannot make out whether A was inserted before E or whether E joined the
queue before D.
• Here, the element with a higher priority comes before the element with a lower priority.
• When two elements have the same priority the elements are arranged and processed on FCFS
principle. we can definitely say that C was inserted in the queue before D.
Insertion:
• When a new element has to be inserted in a priority queue, we have to traverse the entire list
until we find a node that has a priority lower than that of the new element.
• The new node is inserted before the node with the lower priority.
 • If there is an element that has the same priority as the new element, the new element is
inserted after that element.

• If we have to insert a new element with data = F and priority number = 4, then the element
will be inserted before D that has priority number 5, which is lower priority than that of
the new element.

• If we have a new element with data = F and priority number = 2, then the element will be
inserted after B, as both these elements have the same priority but the insertions are done
on FCFS.

Deletion:
• Deletion is a very simple process in this case. The first node of the list will be deleted and the
data of that node will be processed first.
Array Representation of a Priority Queue
• When arrays are used to implement a priority queue, then a separate queue for each priority
number is maintained.
• Each of these queues will be implemented using circular arrays or circular queues. Every
individual queue will have its own FRONT and REAR pointers.
• We use a two-dimensional array for this purpose where each queue will be allocated the same
amount of space.

Priority Queue Matrix

• FRONT[K] and REAR[K] contain the front and rear values of row K, where K is the
priority number.
 Insertion
• To insert a new element with priority K in the priority queue, add the element at the rear end
of row K, where K is the row number as well as the priority number of that element.
• For example, if w have to insert an element R with priority number 3,

Deletion
• To delete an element, we find the first nonempty queue and then process the front element of
the first non-empty queue.
• In our priority queue, the first non-empty queue is the one with priority number 1 and the front
element is A.
• A will be deleted and processed first.
Some of the applications of a priority queue are:
• Dijkstra's algorithm
• for implementing stack
• for load balancing and interrupt handling in an operating system
• for data compression in Huffman code
4. MULTIPLE QUEUES:
• When we implement a queue using an array, the size of the array must be known in advance.
• If the queue is allocated less space, then frequent overflow conditions will be encountered.
• To deal with this problem, the code will have to be modified to reallocate more space for
the array.
• In case we allocate a large amount of space for the queue, it will result in wastage of the
memory. Thus, there lie overflows.
• So a better solution to deal with this problem is to have multiple queues or to have more than
one queue in the same array of sufficient size.
 Multiple Queues
• In the above figure, an array Queue[n] is used to represent two queues, Queue A and Queue B.
• The value of n is such that the combined size of both the queues will never exceed n. queue A
will grow from left to right, whereas queue B will grow from right to left at the same time.
• We can use one dimensional array or multidimensional array to illustrate a multiple queue.
• A queue can also be used to represent n number of queues in the same array. That is, if we
have a QUEUE[n], then each queue I will be allocated an equal amount of space bounded by
indices b[i] and e[i].