#pragma once
class Deq
{
protected:
int* mas; // динамически выделяемая память под дек
int left,right; // смещение от начала и конца дека
int size; // выделено памяти
int current_size; // текущее количество элементов
public:
Deq(int s = 100)
{
size = s;
mas = new int [size];
left = right = current_size = 0;
}
~Deq(void){};
int Size() const { return size; } // размер дека
int Left() const { return mas[left]; } // просмотреть слева
int Right() const { return mas[right]; } // просмотреть справа
bool Push_left(const int v) // вставка слева
{
if (left == right && !current_size) // пустой дек
{
mas[left] = v;
current_size = 1;
return true;
}
if (left-1 == right)
return false; // невозможно добавить элемент из-за переполнения
if (left-1 < 0)
{
if (right == size-1)
return false; // переполнение
left = size-1;
mas[left] = v;
current_size++;
return true; // ok
}
left--;
mas[left] = v;
current_size++;
return true;
}
bool Push_right(const int v) // вставка справа
{
if (left == right && !current_size) // пустой дек
{
mas[right] = v;
current_size = 1;
return true;
}
if (right+1 == left)
return false; // переполнение
if (right+1 == size)
{
if (left == 0)
return false; // переполнение
right = 0;
mas[0] = v;
current_size++;
return true; // успешно добавлено
}
right++;
mas[right] = v;
current_size++;
return true;
}
bool Pop_left(int* out) // извлечь слева
{
if (left == right)
{
if (current_size) // дек не пуст
{
*out = mas[right];
current_size = 0;
return true;
}
return false; // пустой дек
}
if (left+1 == size)
{
//if (right == 0)
// return false;
left=0;
*out = mas[size-1];
current_size--;
return true;
}
*out = mas[left];
left++;
current_size--;
return true;
}
bool Pop_right(int* out) // извлечь справа
{
if (left == right) // указатели совпали
{
if (current_size)
{
*out = mas[right];
current_size = 0;
return true;
}
return false; // пустой дек
}
if (right == 0)
{
//if (left == size-1)
// return false;
right = size-1;
*out = mas[0];
current_size--;
return true;
}
*out = mas[right];
right--;
current_size--;
return true;
}
};