Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we have presented 2 different approaches to implement 2 Queue Data Structure using a single Array Data Structure.

### Table of content

- Definitions
- Algorithm

2.1. Method 1

2.2. Method 2: Optimized - Time & Space complexity
- A way of implementation

### 1. Definitions

*Standard Containers* are objects which stores collections of other objects. They are implemented using template classes so they could accept any kind of data type and they need a way to manage the space allocated for them and a way to access them, directly using an index, or through iterators which represent reference objects with similar properties of pointers.

Ex. deque, list

Any container should implement at least these functions:

- empty
- size
- front
- back
- push_back
- pop_front

*Queues* are containers adaptors based on FIFO (Firs In First Out) rule of accessing elements, meaning we insert elements at one head and remove them from the other head. They are dynamic in size.

```
template <class T, class Container = deque<T> > class queue;
```

*Containers adaptors* are based on standard containers to access their members through them, meaning they encapsulate a standard container called the *underlying container* and implement its methods.

*Arrays* are standard containers that uses a strict linear sequence to access their elements, so they are also called *sequence containers*. The size of them is given as a template parameter and it is allocated at compilation, so they are fixed in size.

```
template < class T, size_t N > class array;
```

Note: Do not confuse them with the ordinary arrays used when you declare it with [].

There are major differences between *arrays* objects and *ordinary arrays* since arrays are user defined objects with a totally different declaration syntax, structure representation and member functions whilst ordinary arrays are simple a storage of elements (of any type, standard or user defined) in a sequence.

Ex. of declarations:

```
array<int,3> a1 = {1,2,3}; //array container
int a2[3] = {1,2,3}; //ordinary array
```

For simplicity of this article we are going to use the ordinary arrays.

### 2. Algorithm

As we could see from definitions, arrays are fixed and queues are dynamic in size, so we must find a way to split the array in such away that both queues will share the same space keeping the FIFO rule.

**Method 1**

The common approach is to split the array into 2 halves, and use the indexes to manipulate elements inside the queues.

This method it is useful if you have more than 2 queues, for k queues you might split the array into k parts.

*push* pseudo code

```
push(element)
if array[headQueue] is empty
array[headQueue] <- elem;
headQueue <- headQueue - 1
else Queue is full
```

*pop* pseudo code

```
pop()
if ( array[headQueue] is not empty )
temp = array[headQueue] ;
for each element on the left side of array[queueSize]
move all the elements to the right with 1 position
else Queue is empty
return temp;
```

## Method 2: Optimized

As you might already thought you can store elements from the both queues by using the starting point of the both heads of the array and not count the size of them. As long as there is space in the array fill in the elements from one stack or another, so they might not be equal in length as the previous method.

Since the array has only 2 heads, this method can be applied only for 2 queues.

*push* pseudo code

```
push(element)
if array[headQueue] is empty
array[headQueue] <- elem;
headQueue <- headQueue + 1
else Queue is full
```

*pop* pseudo code

```
pop()
if ( array[0] is not empty )
temp = array[0] ;
for each element in array
move all the elements to the right (or left) with 1 position
else Queue is empty
return temp;
```

### 3. Time & Space complexity

**Method 1**

push method has O(1) complexity in time and O(n) in space.

pop method has O(n) complexity in time and space.

**Method 2**

push method has O(1) complexity in time and O(n) in space.

pop method has O(n) complexity in time in space.

### 4. A way of implementation

**Method 1**

```
#include <iostream>
using namespace std;
class Queue2Array
{
private:
int *v, sizeV, idxQ1, idxQ2;
public:
Queue2Array(int size)
{
if (size > 0)
{
v = new int[size];
sizeV = size;
idxQ1 = sizeV / 2 -1;
idxQ2 = sizeV -1;
}
}
void pushQ1(int elem)
{
if (v[idxQ1]==0 && idxQ1 >= 0 )
v[idxQ1--] = elem;
//else Queue 1 is full
}
int popQ1()
{
int temp;
if ( v[sizeV / 2 -1] )
{
temp = v[sizeV / 2 -1] ;
for (int i=sizeV / 2 -1; i > 0 ;i--) //move all the elements to the right
{
v[i] = v[i-1];
v[i-1] = 0;
}
}
//else Queue 1 is empty
return temp;
}
void pushQ2(int elem)
{
if (v[idxQ2]==0 && idxQ2 >= sizeV/2 )
v[idxQ2--] = elem;
//else Queue 2 is full
}
int popQ2()
{
int temp;
if ( v[sizeV-1] )
{
temp = v[sizeV-1] ;
for (int i=sizeV-1; i > sizeV/2 ;i--) //move all the elements to the right
{
v[i] = v[i-1];
v[i-1] = 0;
}
}
//else Queue 2 is empty
return temp;
}
void coutV()
{
for (int i=0;i<sizeV;i++)
cout<<"v["<<i<<"]="<<v[i]<<endl;
}
};
int main()
{
Queue2Array a(5);
a.pushQ1(11);
a.pushQ1(12);
a.pushQ1(13);
a.pushQ2(21);
a.pushQ2(22);
a.pushQ2(23);
a.coutV();
cout<<a.popQ1()<<endl;
a.coutV();
cout<<a.popQ1()<<endl;
a.coutV();
cout<<a.popQ1()<<endl;
a.coutV();
cout<<a.popQ2()<<endl;
a.coutV();
cout<<a.popQ2()<<endl;
a.coutV();
cout<<a.popQ2()<<endl;
a.coutV();
return 0;
}
```

**Step by step example**

**Method 2**

```
#include <iostream>
using namespace std;
class Queue2Array
{
private:
int *v, sizeV, idxQ1, idxQ2;
public:
Queue2Array(int size)
{
if (size > 0)
{
v = new int[size];
sizeV = size;
idxQ1 = 0;
idxQ2 = sizeV -1;
}
}
void pushQ1(int elem)
{
if (v[idxQ1]==0 && idxQ1 <= idxQ2 )
v[idxQ1++] = elem;
//else Queue 1 is full
}
int popQ1()
{
int temp;
if ( v[0] )
{
temp = v[0] ;
if(idxQ1 > 1)
for (int i=0; i+1 < idxQ1 ;i++) //move all the elements to the left
{
v[i] = v[i+1];
v[i+1] = 0;
}
else
v[0] = 0;
idxQ1--;
}
//else Queue 1 is empty
return temp;
}
void pushQ2(int elem)
{
if (v[idxQ2]==0 && idxQ2 >= idxQ1 )
v[idxQ2--] = elem;
//else Queue 2 is full
}
int popQ2()
{
int temp;
if ( v[sizeV-1] )
{
temp = v[sizeV-1] ;
if(idxQ2 < sizeV-2)
for (int i=sizeV-1; i-1 > idxQ2 ;i--) //move all the elements to the right
{
v[i] = v[i-1];
v[i-1] = 0;
}
else
v[sizeV-1] = 0;
idxQ2++;
}
//else Queue 2 is empty
return temp;
}
void coutV()
{
for (int i=0;i<sizeV;i++)
cout<<"v["<<i<<"]="<<v[i]<<endl;
}
};
int main()
{
Queue2Array a(5);
a.pushQ1(11);
a.pushQ1(12);
a.pushQ1(13);
a.pushQ2(21);
a.pushQ2(22);
a.pushQ2(23);
a.coutV();
cout<<a.popQ1()<<endl;
a.coutV();
a.pushQ2(23);
a.coutV();
return 0;
}
```

**Step by step example**

With this article at OpenGenus, you must have the complete idea of how to implement 2 Queues in a single Array.