Datastruktur: en kö har implementerats i cirkulär form

Permalänk
Medlem

Datastruktur: en kö har implementerats i cirkulär form

Hej!

Jag behöver hjälp med en fråga.

En kö har implementerats i cirkulär form, se figuren nedan.

[listo][li]| |U| F| K| L| A| | |[/li][/listo]

Rita figurer som visar köns läge steg för steg efter följande operationer:

1) Bokstäverna G och R har ställts i kön
2) tre bokstäver har tagits bort ur kön
3) D och P har ställts i kön

Jag vet att regler vid en kö är FiFo:first in first out
Tillägg görs vid svansen
radering görs vid huvudet

U är huvud pekaren och svans pekaren är i det tomma fältet efter A.

Jag vet inte alls hur man ska göra i denna uppgift. Ska bokstäverna vara i en cirkel.

Permalänk
Medlem

Det känns så tråkigt att hjälpa när frågeställaren anstränger sig noll procent. Men jag gör det ändå (sa någon björntjänst?).

I regel så kan du skapa sådana här köer genom att låta alla element i kön ha en referens till sin efterföljare. Sedan lagrar du en referens till svansen-elementet som representerar hela kön. Du kanske behöver skapa en struktur eller klass för att representera kö-objekt.

x Är det endast ett element i kön så refererar svansen sig själv.

x Ska du plocka ur det sista elementet så gör du endast

[näst_sista_element].next := [sista_element].next uppdatera ev. referens

Detta utesluter det gamla svansen ur cirkulärlistan.

x Ska du läga till ett objekt så gäller analogt

[nytt_element].next = [sista_element].next följt av [sista_elemnt].next := [nytt_element]

(I pseudo-kod eftersom du inte nämner ett specifikt språk)

Lycka till

Visa signatur

AMD 7700X (EK 240mm AIO) | ROG Strix B650E-F Gaming | Gigabyte RX 6800 XT 16GB OC | Kingston Fury 32GB DDR5 5600mhz | Kingston Fury Renegade M2 2TB | Alienware AW2723DF 280hz

Permalänk
Medlem

När jag ska skriva svar på frågorna så ska jag inte redovisa med pseudokod. Utan jag ska visa hur kön ser ut och var huvudpekaren och svanspekar ligger efter dessa operationer.

Permalänk