4. Danh s¸ch tuyÕn tÝnh kiÓu hµng ®îi – Queue.
4.1. §Þnh nghÜa.
Mét kiÓu d÷ liÖu trõu tîng quan träng kh¸c ®îc x©y dùng trªn c¬ së m« h×nh d÷ liÖu danh s¸ch tuyÕn tÝnh lµ hµng ®îi. Hµng ®îi lµ kiÓu danh s¸ch tuyÕn tÝnh trong ®ã, phÐp bæ sung mét phÇn tö vµo hµng ®îi ®îc thùc hiÖn ë mét ®Çu, gäi lµ lèi sau (rear) vµ phÐp lo¹i bá mét phÇn tö ®îc thùc hiÖn ë ®Çu kia, gäi lµ lèi tríc (front).
Nh vËy, c¬ cÊu cña hµng ®îi lµ vµo ë mét ®Çu, ra ë ®Çu kh¸c, phÇn tö vµo tríc th× ra tríc, phÇn tö vµo sau th× ra sau. Do ®ã, hµng ®îi cßn ®îc gäi lµ danh s¸ch kiÓu FIFO (First In First Out). Trong thùc tÕ ta còng thÊy cã nh÷ng h×nh ¶nh gièng hµng ®îi, ch¼ng h¹n, hµng ngêi chê mua vÐ tÇu, häc sinh xÕp hµng ®i vµo líp v.v...
4.2. Cµi ®Æt hµng ®îi bëi m¶ng.
Ta cã thÓ biÓu diÔn hµng bëi m¶ng víi viÖc sö dông hai chØ sè front ®Ó chØ vÞ trÝ ®Çu hµng (lèi tríc) vµ rear ®Ó chØ vÞ trÝ cuèi hµng (lèi sau). CÊu tróc d÷ liÖu hµng ®îi ®îc biÓu diÔn nh sau:
Const max = N ;
Type Queue = Record
front, rear : 0..max;
E : Array[1..max] Of Item;
End;
Var Q : Queue;
Trong c¸ch cµi ®Æt nµy, hµng ®îi Q lµ rçng nÕu Q.rear = 0, vµ hµng ®Çy nÕu Q.rear = max.
H×nh 4.1: M¶ng biÓu diÔn hµng ®îi
4.3. C¸c phÐp to¸n trªn hµng ®îi.
Gièng nh ng¨n xÕp, khi thùc hiÖn c¸c thao t¸c víi hµng ®îi ta kh«ng ®îc phÐp truy nhËp tïy tiÖn vµo c¸c phÇn tö cña hµng ®îi, mµ ph¶i sö dông c¸c phÐp to¸n ®· ®îc ®Þnh nghÜa trªn hµng ®îi. §ã lµ c¸c phÐp to¸n sau:
a. Khëi t¹o hµng ®îi rçng.
Procedure Initialize(Var Q : Queue);
Begin
With Q Do
begin
front := 1; rear := 0;
end;
End;
b. KiÓm tra hµng ®îi rçng.
Function Empty(Q : Queue) : Boolean;
Begin
Empty := (Q.rear = 0);
End;
c. KiÓm tra hµng ®îi ®Çy.
Function Full(Q : Queue) : Boolean;
Begin
Full := (Q.rear = max);
End;
d. Bæ sung mét míi vµo hµng ®îi.
Khi bæ sung mét phÇn tö míi vµo hµng ®îi cÇn kiÓm tra xem hµng cã ®Çy kh«ng, nÕu hµng cha ®Çy th× bæ sung phÇn tö míi vµo hµng, ngîc l¹i viÖc bæ sung kh«ng ®îc thùc hiÖn.
Procedure AddQ(Var Q : Queue; X : Item);
Begin
If Full(Q) Then
write(‘Hang day’)
Else
With Q Do
begin
rear := rear + 1;
E[rear] := X;
end;
End;
5. Lo¹i bá mét phÇn tö ra khái hµng ®îi.
Khi lo¹i bá mét phÇn tö cÇn ph¶i kiÓm tra xem hµng ®îi cã rçng kh«ng, nÕu hµng ®îi rçng th× kh«ng thÓ thùc hiÖn viÖc lo¹i bá, ngîc l¹i th× lo¹i bá phÇn tö ë ®Çu hµng, néi dung cña phÇn tö nµy ®îc lu trong biÕn X. Thªm n÷a, khi lo¹i bá, nÕu hµng chØ cã mét phÇn tö (nghÜa lµ hµng sÏ rçng sau khi lo¹i bá) th× cÇn khëi t¹o l¹i hµng.
Sau ®©y lµ thñ tôc thùc hiÖn viÖc lo¹i bá.
Procedure DeleteQ(Var Q : Queue; Var X : Item);
Begin
If Empty(Q) Then write(‘Hang rong’)
Else
With Q Do
begin
X := E[front];
if front = rear then
begin
front := 1; rear : = 0; {khëi t¹o l¹i hµng ®îi}
end
else front := front + 1;
end;
End;
3.2.3.4. Cµi ®Æt hµng ®îi bëi m¶ng vßng trßn.
Ph¬ng ph¸p cµi ®Æt hµng ®îi víi hai chØ sè nh trªn cã nhîc ®iÓm lín. NÕu phÐp lo¹i bá kh«ng thêng xuyªn lµm cho hµng rçng, th× c¸c chØ sè front vµ rear sÏ t¨ng liªn tôc vµ sÏ vît qu¸ cì cña m¶ng. Hµng sÏ trë thµnh ®Çy, mÆc dï c¸c vÞ trÝ trèng trong m¶ng cã thÓ vÉn cßn nhiÒu (do viÖc lo¹i bá c¸c phÇn tö ë ®Çu hµng).
§Ó kh¾c phôc nhîc ®iÓm trªn, ngêi ta ®a ra ph¬ng ph¸p cµi ®Æt hµng bëi m¶ng vßng trßn. §ã lµ mét m¶ng víi chØ sè ch¹y trong miÒn 1..max, víi mäi i = 1, 2, ..., max – 1, phÇn tö thø i cña m¶ng ®i tríc phÇn tö thø i + 1, cßn phÇn tö thø max ®i tríc phÇn tö ®Çu tiªn, tøc lµ c¸c phÇn tö cña m¶ng ®îc xÕp thµnh vßng trßn (xem h×nh díi).
Khi biÓu diÔn hµng bëi m¶ng vßng trßn, ®Ó biÕt khi nµo hµng ®Çy, khi nµo hµng rçng ta cÇn ®a thªm vµo biÕn count ®Ó ®Õm sè phÇn tö trong hµng. Chóng ta cã khai b¸o cÊu tróc d÷ liÖu sau:
Const max = N ;
Type Queue = Record
count : 0..max;
front, rear : 0..max;
E : Array[1..max] Of Item;
End;
Var Q : Queue;
Trong c¸ch cµi ®Æt nµy, hµng rçng khi Q.count = 0, hµng ®Çy khi Q.count = max.
Khi lµm viÖc víi m¶ng vßng trßn, cÇn lu ý r»ng, phÇn tö ®Çu tiªn cña m¶ng ®i sau phÇn tö thø max. Sau ®©y chóng ta sÏ viÕt c¸c thñ tôc bæ sung mét phÇn tö vµo hµng ®îi, vµ lo¹i bá mét phÇn tö khái hµng ®îi, c¸c thñ tôc kh¸c dµnh l¹i cho b¹n ®äc.
Procedure AddQ(Var Q : Queue; X : Item);
Begin
With Q Do
if count = max then write(‘Hang day’)
else begin
if rear = max then
rear := 1
else
rear := rear + 1;
E[rear] := X;
count := count + 1;
end;
End;
Procedure DeleteQ(Var Q : Queue; Var X : Item);
Begin
With Q Do
if count = 0 then write(‘hang rong’)
else begin
X := E[front];
if front = rear then
begin
front := 1; rear := 0;
end
else
if front = max then front := 1
else front := front + 1;
count := count – 1;
end;
End;
Hµng ®îi thêng dïng ®Ó thùc hiÖn c¸c “tuyÕn chê” (waiting lines) trong xö lý ®éng, ®Æc biÖt trong c¸c hÖ m« pháng (simulation), ®ã lµ c¸c hÖ m« h×nh ho¸ c¸c qu¸ tr×nh ®éng vµ ngêi ta dïng m« h×nh nµy ®Ó nghiªn cøu ho¹t ®éng cña c¸c qu¸ tr×nh Êy.
3.3. Danh s¸ch liªn kÕt.
Nh ®· nªu ë ch¬ng tríc, lu tr÷ kÕ tiÕp ®èi víi danh s¸ch tuyÕn tÝnh ®· béc lé râ nhîc ®iÓm trong trêng hîp thùc hiÖn thêng xuyªn c¸c phÐp bæ sung hoÆc lo¹i bá phÇn tö, trêng hîp xö lý ®ång thêi nhiÒu danh s¸ch v.v...
ViÖc sö dông con trá hoÆc mèi nèi ®Ó tæ chøc danh s¸ch tuyÕn tÝnh, mµ ta gäi lµ danh s¸ch liªn kÕt (hay cßn gäi lµ danh s¸ch mãc nèi), chÝnh lµ mét gi¶i ph¸p nh»m kh¾c phôc nhîc ®iÓm trªn. Sau ®©y ta xÐt tíi mét sè d¹ng danh s¸ch liªn kÕt.
.png "Stack")
