Răspuns: 024 Deque

[•pauldb]

A trebuit sa fac un subiect nou, deoarece celalalt era locked.   

Stiu ca intrebarea mea nu prea are legatura cu informatica, ci cu limba engleza, dar poate cineva sa-mi spuna cum se scrie corect cuvantul "deque"?

[•wefgef]

http://en.wikipedia.org/wiki/Deque

probabil ca asa cum ai scris tu 

[•greco]

Se scrie "deque" si se pronunta "deck".

[•CezarMocan]

Imi explicati si mie va rog cum se implementeaza un deque in Pascal?? 

[•stef2n]

Deque este o coada in care poti sa faci adaugari si stergeri la ambele capete. O poti implementa ca pe un vector V (sa zicem de dimensiune maxima NMAX), pe care retii 2 indici: start si end (capetele cozii). Vectorul va fi circular, adica elementului de indice NMAX-1 ii urmeaza cel de indice 0, iar elementul de indice 0 este precedat de cel de indice NMAX-1. Astfel,

1. pentru adaugare la stanga: V[--start]=x     // daca start=0, start devine NMAX-1
2. pentru adaugare la dreapta: V[++end]=x   // daca end=NMAX-1, end devine 0
3. pentru stergere la stanga: start++            // daca start=NMAX-1, start devine 0
4. pentru stergere la dreapta: end--              // daca end=0, end devine NMAX-1

Ca sa verifici daca deque-ul este vid sau nu, poti sa retii pentru start si end o valoare speciala (de ex. -1). Si de fiecare data cand trebuie sa faci o operatie din cele 4 de mai sus, faci o astfel de verificare.

O alta varianta de implementare ar fi cu liste dublu inlantuite, dar asta implica lucru cu pointeri si nu cred ca are rost sa te complici.

P.S. Explicatia nu e in Pascal, dar sper sa te descurci

[•CezarMocan]

Ma descurc, ca stiu cat de cat si sintaxa de C++  .  Mersi.   Si inca ceva daca se poate: cum ma poate ajuta un deque sa aflu maximu in O(1)?? 

[•devilkind]

cezar banuiesc ca vrei sa incerci problema mall . inainte incearca problema secventa de pe infoarena. Vei gasi pe topicul de pe forum al acestei probleme mai multe detalii.

[•CezarMocan]

Mda, ai dreptate  . Multumesc mult de hint . Oricum, nu e numa pt problema mall. Cred ca o sa ma ajute mult pe la concursuri  .

[•pauldb]

Merge Mall si fara deque-uri.