Декуе структура података

У овом упутству ћете научити шта је ред с двоструким завршетком (декуе). Такође ћете наћи радне примере различитих операција над декуеом на Ц, Ц ++, Јава и Питхон.

Декуе или Доубле Ендед Куеуе је врста реда у којем се уметање и уклањање елемената може извршити било са предње или са задње стране. Дакле, не следи ФИФО правило (Фирст Ин Фирст Оут).

Представљање Декуе-а

Врсте Декуе

  • Улаз ограничен у декуе-у
    У овом декуе-у улаз је ограничен на једном крају, али омогућава брисање на оба краја.
  • Излазни ограничени декуе
    У овом декуе-у излазни је ограничен на једном крају, али омогућава уметање на оба краја.

Операције на Декуе-у

Испод је примена декуе-а у кружном низу. У кружном низу, ако је низ пун, почињемо од почетка.

Али у линеарној имплементацији низа, ако је низ пун, више елемената не може бити уметнуто. У свакој од доле наведених операција, ако је низ пун, баца се „порука преливања“.

Пре извођења следећих операција, следе се ови кораци.

  1. Узми низ (декуе) величине н.
  2. Поставите два показивача на прву позицију и поставите front = -1и rear = 0.
Иницијализујте низ и показиваче за декуе

1. Уметните са предње стране

Ова операција додаје елемент са предње стране.

  1. Проверите положај предњег дела. Проверите положај предњег дела
  2. Ако front < 1, поново иницијализујте front = n-1(последњи индекс). Померите напред до краја
  3. У супротном, смањите фронт за 1.
  4. Додајте нови тастер 5 у array(front). Уметните елемент са предње стране

2. Уметните позади

Ова операција додаје елемент позади.

  1. Проверите да ли је низ пун. Проверите да ли је декуе пун
  2. Ако је капљица пуна, поново је иницијализирајте rear = 0.
  3. У супротном, повећати задњи за 1. Повећати задњи
  4. Додајте нови тастер 5 у array(rear). Уметните елемент позади

3. Избриши са предње стране

Операција брише елемент са предње стране.

  1. Проверите да ли је декуе празан. Проверите да ли је декуе празан
  2. Ако је декуе празан (тј. front = -1), Брисање се не може извршити ( услов ундерфлов ).
  3. Ако декуе има само један елемент (тј. front = rear), Поставите front = -1и rear = -1.
  4. Иначе ако је предња страна на крају (тј. front = n - 1), Поставите је према напред front = 0.
  5. Друго, front = front + 1. Повећајте предњи део

4. Избришите са задње стране

Ова операција брише елемент са задње стране.

  1. Проверите да ли је декуе празан. Проверите да ли је декуе празан
  2. Ако је декуе празан (тј. front = -1), Брисање се не може извршити ( услов ундерфлов ).
  3. Ако декуе има само један елемент (тј. front = rear), Подесите front = -1и rear = -1, у супротном, следите доленаведене кораке.
  4. Ако је задњи део напред (тј. rear = 0), Поставите га напред rear = n - 1.
  5. Друго, rear = rear - 1. Смањите задњи део

5. Означите Празно

Ова операција проверава да ли је декуе празан. Ако front = -1је декуе празан.

6. Означите Потпуно

Ова операција проверава да ли је декуе пун. Ако front = 0и rear = n - 1ИЛИ front = rear + 1, декуе је пун.

Имплементација Декуе-а у Питхон, Јава, Ц и Ц ++

Питхон Јава Ц Ц ++ 
 # Deque implementaion in python class Deque: def __init__(self): self.items = () def isEmpty(self): return self.items == () def addRear(self, item): self.items.append(item) def addFront(self, item): self.items.insert(0, item) def removeFront(self): return self.items.pop() def removeRear(self): return self.items.pop(0) def size(self): return len(self.items) d = Deque() print(d.isEmpty()) d.addRear(8) d.addRear(5) d.addFront(7) d.addFront(10) print(d.size()) print(d.isEmpty()) d.addRear(11) print(d.removeRear()) print(d.removeFront()) d.addFront(55) d.addRear(45) print(d.items)
 // Deque implementation in Java class Deque ( static final int MAX = 100; int arr(); int front; int rear; int size; public Deque(int size) ( arr = new int(MAX); front = -1; rear = 0; this.size = size; ) boolean isFull() ( return ((front == 0 && rear == size - 1) || front == rear + 1); ) boolean isEmpty() ( return (front == -1); ) void insertfront(int key) ( if (isFull()) ( System.out.println("Overflow"); return; ) if (front == -1) ( front = 0; rear = 0; ) else if (front == 0) front = size - 1; else front = front - 1; arr(front) = key; ) void insertrear(int key) ( if (isFull()) ( System.out.println(" Overflow "); return; ) if (front == -1) ( front = 0; rear = 0; ) else if (rear == size - 1) rear = 0; else rear = rear + 1; arr(rear) = key; ) void deletefront() ( if (isEmpty()) ( System.out.println("Queue Underflow"); return; ) // Deque has only one element if (front == rear) ( front = -1; rear = -1; ) else if (front == size - 1) front = 0; else front = front + 1; ) void deleterear() ( if (isEmpty()) ( System.out.println(" Underflow"); return; ) if (front == rear) ( front = -1; rear = -1; ) else if (rear == 0) rear = size - 1; else rear = rear - 1; ) int getFront() ( if (isEmpty()) ( System.out.println(" Underflow"); return -1; ) return arr(front); ) int getRear() ( if (isEmpty() || rear < 0) ( System.out.println(" Underflow"); return -1; ) return arr(rear); ) public static void main(String() args) ( Deque dq = new Deque(4); System.out.println("Insert element at rear end : 12 "); dq.insertrear(12); System.out.println("insert element at rear end : 14 "); dq.insertrear(14); System.out.println("get rear element : " + dq.getRear()); dq.deleterear(); System.out.println("After delete rear element new rear become : " + dq.getRear()); System.out.println("inserting element at front end"); dq.insertfront(13); System.out.println("get front element: " + dq.getFront()); dq.deletefront(); System.out.println("After delete front element new front become : " + +dq.getFront()); ) )
 // Deque implementation in C #include #define MAX 10 void addFront(int *, int, int *, int *); void addRear(int *, int, int *, int *); int delFront(int *, int *, int *); int delRear(int *, int *, int *); void display(int *); int count(int *); int main() ( int arr(MAX); int front, rear, i, n; front = rear = -1; for (i = 0; i < MAX; i++) arr(i) = 0; addRear(arr, 5, &front, &rear); addFront(arr, 12, &front, &rear); addRear(arr, 11, &front, &rear); addFront(arr, 5, &front, &rear); addRear(arr, 6, &front, &rear); addFront(arr, 8, &front, &rear); printf("Elements in a deque: "); display(arr); i = delFront(arr, &front, &rear); printf("removed item: %d", i); printf("Elements in a deque after deletion: "); display(arr); addRear(arr, 16, &front, &rear); addRear(arr, 7, &front, &rear); printf("Elements in a deque after addition: "); display(arr); i = delRear(arr, &front, &rear); printf("removed item: %d", i); printf("Elements in a deque after deletion: "); display(arr); n = count(arr); printf("Total number of elements in deque: %d", n); ) void addFront(int *arr, int item, int *pfront, int *prear) ( int i, k, c; if (*pfront == 0 && *prear == MAX - 1) ( printf("Deque is full."); return; ) if (*pfront == -1) ( *pfront = *prear = 0; arr(*pfront) = item; return; ) if (*prear != MAX - 1) ( c = count(arr); k = *prear + 1; for (i = 1; i <= c; i++) ( arr(k) = arr(k - 1); k--; ) arr(k) = item; *pfront = k; (*prear)++; ) else ( (*pfront)--; arr(*pfront) = item; ) ) void addRear(int *arr, int item, int *pfront, int *prear) ( int i, k; if (*pfront == 0 && *prear == MAX - 1) ( printf("Deque is full."); return; ) if (*pfront == -1) ( *prear = *pfront = 0; arr(*prear) = item; return; ) if (*prear == MAX - 1) ( k = *pfront - 1; for (i = *pfront - 1; i < *prear; i++) ( k = i; if (k == MAX - 1) arr(k) = 0; else arr(k) = arr(i + 1); ) (*prear)--; (*pfront)--; ) (*prear)++; arr(*prear) = item; ) int delFront(int *arr, int *pfront, int *prear) ( int item; if (*pfront == -1) ( printf("Deque is empty."); return 0; ) item = arr(*pfront); arr(*pfront) = 0; if (*pfront == *prear) *pfront = *prear = -1; else (*pfront)++; return item; ) int delRear(int *arr, int *pfront, int *prear) ( int item; if (*pfront == -1) ( printf("Deque is empty."); return 0; ) item = arr(*prear); arr(*prear) = 0; (*prear)--; if (*prear == -1) *pfront = -1; return item; ) void display(int *arr) ( int i; printf(" front: "); for (i = 0; i < MAX; i++) printf(" %d", arr(i)); printf(" :rear"); ) int count(int *arr) ( int c = 0, i; for (i = 0; i < MAX; i++) ( if (arr(i) != 0) c++; ) return c; )
 // Deque implementation in C++ #include using namespace std; #define MAX 10 class Deque ( int arr(MAX); int front; int rear; int size; public: Deque(int size) ( front = -1; rear = 0; this->size = size; ) void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); bool isFull(); bool isEmpty(); int getFront(); int getRear(); ); bool Deque::isFull() ( return ((front == 0 && rear == size - 1) || front == rear + 1); ) bool Deque::isEmpty() ( return (front == -1); ) void Deque::insertfront(int key) ( if (isFull()) ( cout << "Overflow" << endl; return; ) if (front == -1) ( front = 0; rear = 0; ) else if (front == 0) front = size - 1; else front = front - 1; arr(front) = key; ) void Deque ::insertrear(int key) ( if (isFull()) ( cout << " Overflow " << endl; return; ) if (front == -1) ( front = 0; rear = 0; ) else if (rear == size - 1) rear = 0; else rear = rear + 1; arr(rear) = key; ) void Deque ::deletefront() ( if (isEmpty()) ( cout << "Queue Underflow" << endl; return; ) if (front == rear) ( front = -1; rear = -1; ) else if (front == size - 1) front = 0; else front = front + 1; ) void Deque::deleterear() ( if (isEmpty()) ( cout << " Underflow" << endl; return; ) if (front == rear) ( front = -1; rear = -1; ) else if (rear == 0) rear = size - 1; else rear = rear - 1; ) int Deque::getFront() ( if (isEmpty()) ( cout << " Underflow" << endl; return -1; ) return arr(front); ) int Deque::getRear() ( if (isEmpty() || rear < 0) ( cout << " Underflow" << endl; return -1; ) return arr(rear); ) int main() ( Deque dq(4); cout << "insert element at rear end "; dq.insertrear(5); dq.insertrear(11); cout << "rear element: " << dq.getRear() << endl; dq.deleterear(); cout << "after deletion of the rear element, the new rear element: " << dq.getRear() << endl; cout << "insert element at front end "; dq.insertfront(8); cout << "front element: " << dq.getFront() << endl; dq.deletefront(); cout << "after deletion of front element new front element: " << dq.getFront() << endl; )

Сложеност времена

Временска сложеност свих наведених операција је константна тј O(1).

Примене Декуе структуре података

  1. У операцијама поништавања софтвера.
  2. За чување историје у прегледачима.
  3. За примену и стекова и редова.

Занимљиви Чланци...