Hvordan implementere en kø ved hjelp av to stabler

En kø er en dynamisk datastruktur som du tilgang til data i et "først inn-først ut" prosess. En stabel er en dynamisk datastruktur som du tilgang til data i en "siste i-først ut" prosess. Hvis du implementerer en stabel, bare det siste elementet du plassert på stakken er tilgjengelig. Hvis du ønsker å få data på bunnen av stabelen (det første elementet du setter på stakken) så du behandler stabelen som en kø. For å gjøre dette, må du gjennomføre en andre stabel.

Bruksanvisning

To Stacks lik én kø

1 I en teksteditor, skrive koden for å implementere en stabel i henhold til prosedyrer og funksjoner som er tilgjengelige i programmeringsspråket du vil bruke. Ring denne bunken In_Stack. Plasser data på In_Stack. (Mange programmeringsspråk bruker kommandoen "push" for å legge til data i en stabel.) For eksempel, trykk på In_Stack følgende data i følgende rekkefølge, "A" og deretter "B" og deretter "C." "A" er den første på, og den er nederst i stabelen. Hvis du vil ha tilgang til det første elementet, så du behandler dataene som en kø.

2 Skriv inn koden for å implementere en ny bunke i henhold til prosedyrer og funksjoner som er tilgjengelige i programmeringsspråket du vil bruke. Ring denne bunken Out_Stack. (Mange programmeringsspråk bruker kommandoen "pop" å fjerne data til en stabel.)

3 Fjern hvert element fra In_Stack og plassere den på Out_Stack. I generelle termer, pop du et element av In_Stack, og skyv den på Out_Stack. Deretter kan du sjekke om In_Stack er tom. Hvis det ikke er tomt, så pop det neste elementet ut av In_Stack og skyv den på Out_Stack. Gjenta til In_Stack er tom. I vårt eksempel, pop du "C" off av In_Stack og skyv den på Out_Stack. Sjekk om In_Stack er tom. Pop "B" ut av In_Stack og skyv den på Out_Stack. Sjekk om In_Stack er tom. Pop "A" ut av In_Stack og skyv den på Out_Stack. Sjekk om In_Stack er tom.

4 Når In_Stack er tom, elementet som var på bunnen av In_Stack ( "A" i vårt eksempel) er på toppen av Out_Stack. Pop elementet av av Out_Stack, og du har slått stabelen i en kø. Din første elementet på stakken er nå det første elementet ut (FIFO).

Hint

• De fleste programmeringsspråk gir funksjoner for å behandle data i en matrise som enten en kø eller en stabel. Det vil si at du kan få tilgang til hver ende av rekken uansett hvilken ende du legger dataene. Hvis dataene er i en matrise, trenger du ikke å bekymre deg om å få tilgang til data som en kø eller en stabel. Men hvis dataene er i en dynamisk stack og du ønsker å behandle det som en kø, så du må implementere andre stabelen.