Stack

Danh s¸ch tuyÕn tÝnh kiÓu ng¨n xÕp.

3.1. §Þnh nghÜa.

Ng¨n xÕp cßn gäi lµ STACK lµ mét danh s¸ch tuyÕn tÝnh trong ®ã phÐp bæ sung mét phÇn tö vµo ng¨n xÕp vµ phÐp lo¹i bá mét phÇn tö khái ng¨n xÕp lu«n lu«n thùc hiÖn ë mét ®Çu gäi lµ ®Ønh (top). Cã thÓ h×nh dung Stack nh­ c¬ cÊu cña mét hép chøa ®¹n sóng. ViÖc ®­a ®¹n vµo hép ®¹n hay lÊy ®¹n ra khái hép chØ ®­îc thùc hiÖn ë ®Çu hép. Viªn ®¹n míi n¹p n»m ë ®Ønh cßn viªn ®¹n n¹p ®Çu tiªn n»m ë ®¸y hép.

 

3.2. Cµi ®Æt ng¨n xÕp bëi m¶ng.

Gi¶ sö danh s¸ch ®­îc biÓu diÔn lµ mét ng¨n xÕp, cã ®é dµi tèi ®a lµ mét sè N nµo ®ã, c¸c phÇn tö cña ng¨n xÕp  cã kiÓu d÷ liÖu lµ Item. Item cã thÓ lµ c¸c kiÓu d÷ liÖu ®¬n, hoÆc c¸c kiÓu d÷ liÖu cã cÊu tróc, th«ng th­êng Item lµ b¶n ghi. Chóng ta biÓu diÔn ng¨n xÕp bëi mét b¶n ghi gåm 2 tr­êng. Tr­êng thø nhÊt lµ m¶ng c¸c Item, tr­êng thø 2 ghi chØ sè cña thµnh phÇn m¶ng l­u tr÷ phÇn tö cuèi cïng cña danh s¸ch. Chóng ta khai b¸o cÊu tróc d÷ liÖu biÓu diÔn ng¨n xÕp nh­ sau:

Const max = N ;

Type   Stack = Record

                        E : Array[1..max] Of Item ;

                        top : 0..max ;

            End ;

Var S : Stack ;

Víi c¸ch cµi ®Æt nµy, nÕu S.top = 0 th× S lµ ng¨n xÕp rçng, S.top = max th× S lµ ng¨n xÕp ®Çy.

H×nh 3.2. M¶ng biÓu diÔn ng¨n xÕp.

 VÝ dô: §o¹n ch­¬ng tr×nh.

Const max = 100;

Type   hoc_sinh = Record

                        ho_ten : string[25];

                        tuoi : integer;

            End;

            Stack = Record

                        E : Array[1..max] Of hoc_sinh;

                        top : 0..max;

            End;

Var S : Stack ;

Khai b¸o ng¨n xÕp S cã thÓ chøa tèi ®a 100 phÇn tö, mçi phÇn tö (Item) lµ mét b¶n ghi hoc_sinh gåm 2 tr­êng ho_ten vµ tuoi.

3.3. C¸c phÐp to¸n trªn ng¨n xÕp.

Gi¶ sö S lµ ng¨n xÕp c¸c phÇn tö cña nã cã kiÓu Item vµ X lµ mét phÇn tö cã cïng kiÓu víi c¸c phÇn tö cña ng¨n xÕp. Ta cã c¸c phÐp to¸n sau víi ng¨n xÕp S.

a. Khëi t¹o ng¨n xÕp rçng (ng¨n xÕp kh«ng chøa phÇn tö nµo).

procedure Initialize (var S : Stack);

begin

   S.top := 0;

end;

b. KiÓm tra ng¨n xÕp rçng.

function Empty ( S : Stack) : Boolean;

begin

   Empty := (S.top = 0);

end;

Hµm Empty nhËn gi¸ trÞ true nÕu S rçng vµ false nÕu S kh«ng rçng.

c. KiÓm tra ng¨n xÕp ®Çy.

function Full ( S : Stack) : Boolean;

begin

   Full := (S.top = max);

end;

Hµm Full nhËn gi¸ trÞ true nÕu S ®Çy vµ false nÕu kh«ng.

d. Thªm mét phÇn tö míi vµo ®Ønh ng¨n xÕp.

§Ó bæ sung phÇn tö X vµo ®Ønh cña ng¨n xÕp S, tr­íc hÕt ph¶i kiÓm tra xem S cã ®Çy kh«ng. NÕu S ®Çy th× viÖc bæ sung kh«ng thùc hiÖn ®­îc, ng­îc l¹i X ®­îc bæ sung vµo ®Ønh cña S.

procedure PUSH ( var S : Stack, X : Item);

begin

   with S do

               if  Full(S) then writeln(‘ Stack is full now’)

                        else begin

                           top := top + 1;

                           E[top] := X;

                        end;

end;

e. Lo¹i bá phÇn tö ë ®Ønh cña ng¨n xÕp.

ViÖc lo¹i bá chØ ®­îc thùc hiÖn nÕu S kh«ng rçng, gi¸ trÞ cña phÇn tö bÞ lo¹i bá ®­îc g¸n cho biÕn X.

procedure POP (var S : Stack; var X : Item);

begin

   with S do

               if  Empty(S) then write (‘Stack is empty now’)

                        else begin

                           X := E[top];

                           top := top – 1;

                        end;

end;

3.4. Xö lý víi nhiÒu ng¨n xÕp.

Cã nh÷ng tr­êng hîp cïng mét lóc ta ph¶i xö lý nhiÒu ng¨n xÕp trªn cïng mét kh«ng gian nhí. Nh­ vËy, cã thÓ x¶y ra t×nh tr¹ng mét ng¨n xÕp nµy ®· bÞ trµn trong khi kh«ng gian dù tr÷ cho ng¨n xÕp kh¸c vÉn cßn chç trèng (trµn côc bé). Lµm thÕ nµo ®Ó kh¾c phôc ®­îc t×nh tr¹ng nµy?

NÕu lµ hai ng¨n xÕp th× cã thÓ gi¶i quyÕt dÔ dµng. Ta kh«ng qui ®Þnh kÝch th­íc tèi ®a cho tõng ng¨n xÕp n÷a mµ kh«ng gian nhí dµnh ra sÏ ®­îc dïng chung. Ta ®Æt hai ng¨n xÕp ë hai ®Çu sao cho h­íng ph¸t triÓn cña chóng ng­îc nhau, nh­ h×nh d­íi ®©y.

H×nh 4.1: Hai ng¨n xÕp trªn mét kh«ng gian nhí

Nh­ vËy cã thÓ mét ng¨n xÕp nµy dïng lÊn sang qu¸ nöa kh«ng gian dù tr÷ nÕu nh­ ng¨n xÕp kia ch­a dïng ®Õn. Do ®ã hiÖn t­îng trµn chØ x¶y ra khi toµn bé kh«ng gian nhí dµnh cho chóng ®· ®­îc dïng hÕt.

Nh­ nÕu sè l­îng ng¨n xÕp tõ 3 trë lªn th× kh«ng thÓ lµm theo kiÓu nh­ vËy ®­îc, mµ ph¶i cã gi¶i ph¸p linh ho¹t h¬n n÷a. Ch¼ng h¹n cã 3 ng¨n xÕp, lóc ®Çu kh«ng gian nhí cã thÓ chia ®Òu cho c¶ 3, nh­ h×nh d­íi ®©y.

H×nh 4.2: Hai ng¨n xÕp trªn mét kh«ng gian nhí

Nh­ng nÕu cã mét ng¨n xÕp nµo ph¸t triÓn nhanh bÞ trµn tr­íc mµ ng¨n xÕp kh¸c vÉn cßn chç th× ph¶i dån chç cho nã b»ng c¸ch hoÆc ®Èy ng¨n xÕp ®øng sau nã sang bªn ph¶i hoÆc lïi chÝnh ng¨n xÕp ®ã sang tr¸i trong tr­êng hîp cã thÓ. Nh­ vËy th× ®¸y cña c¸c ng¨n xÕp ph¶i ®­îc phÐp di ®éng vµ dÜ nhiªn c¸c gi¶i thuËt bæ sung hoÆc lo¹i bá phÇn tö ®èi víi c¸c ng¨n xÕp ho¹t ®éng theo kiÓu nµy còng ph¶i thay ®æi.

3.5. Vµi vÝ dô vÒ øng dông cña ng¨n xÕp.

a. §æi c¬ sè.

Ta biÕt r»ng d÷ liÖu l­u tr÷ trong bé nhí cña m¸y tÝnh ®Òu ®­îc biÓu diÖn d­íi d¹ng m· nhÞ ph©n. Nh­ vËy c¸c sè xuÊt hiÖn trong ch­¬ng tr×nh ®Òu ph¶i chuyÓn ®æi tõ hÖ thËp ph©n sang hÖ nhÞ ph©n tr­íc khi thùc hiÖn c¸c phÐp xö lý.

Khi ®æi mét sè nguyªn tõ hÖ thËp ph©n sang hÖ nhÞ ph©n th× ng­êi ta dïng phÐp chia liªn tiÕp cho 2 vµ lÊy c¸c sè d­ (lµ c¸c ch÷ sè nhÞ ph©n) theo chiÒu ng­îc l¹i.

VÝ dô:

11010111

 

Ta thÊy trong c¸ch biÕn ®æi nµy c¸c sè ®­îc t¹o ra sau l¹i ®­îc hiÓn thÞ tr­íc. C¬ chÕ s¾p xÕp nµy chÝnh lµ c¬ chÕ ho¹t ®éng cña ng¨n xÕp. §Ó thùc hiÖn biÕn ®æi ta sÏ dïng mét ng¨n xÕp ®Ó l­u tr÷ c¸c sè d­ qua tõng phÐp chia: Khi thùc hiÖn phÐp chia th× n¹p sè d­ vµo ng¨n xÕp, sau ®ã lÊy chóng lÇn l­ît tõ ng¨n xÕp ra.

VÝ dô:

Sè: (26)₁₀ = (11010)₂ trong qu¸ tr×nh biÕn ®æi c¸c sè d­ lÇn l­ît sÏ lµ: (0 1 0 1 1).

H×nh 4.8

Ta khai b¸o cÊu tróc d÷ liÖu cho bµi to¸n nµy nh­ sau:

Const

max = 16; {thùc hiÖn ®æi sè nguyªn cã kÝch th­íc 2 byte}

Type

   Item  = 0..1; {Item lµ ch÷ sè nhÞ ph©n}

   Stack = Record

               E : Array[1..max] Of Item;

               top : 0..max;

            End;

Var S : Stack; { S lµ ng¨n xÕp chøa c¸c sè d­ qua c¸c phÐp chia trong qu¸ tr×nh chuyÓn ®æi}

Gi¶i thuËt sö dông ng¨n xÕp thùc hiÖn chuyÓn ®æi sè nguyªn d­¬ng N tõ hÖ c¬ sè 10 sang hÖ c¬ sè 2. Trong gi¶i thuËt nµy cã sö dông c¸c phÐp to¸n trªn ng¨n xÕp.

Procedure Chuyen_doi(N);

1 – While N <> 0 do

   R := N mod 2; {tÝnh sè d­ trong phÐp chia N cho 2}

   call PUSH(S, R);

   N := N div 2; {thay N b»ng th­¬ng cña phÐp chia N cho 2}

end

2 – write(‘ma nhi phan:’);

While not Empty(S) do

begin

   call POP(S, R);

   write(R);

end

end

b. §Þnh gi¸ biÓu thøc sè häc theo ký ph¸p nghÞch ®¶o Balan.

NhiÖm vô cña bé dÞch lµ t¹o ra c¸c chØ thÞ m¸y cÇn thiÕt ®Ó thùc hiÖn c¸c lÖnh cña ch­¬ng tr×nh nguån. Mét phÇn trong nhiÖm vô nµy lµ t¹o ra c¸c chØ thÞ ®Þnh gi¸ c¸c biÓu thøc sè häc. Ch¼ng h¹n c©u lÖnh g¸n X := A*B + C.

Bé dÞch ph¶i t¹o ra c¸c chØ thÞ m¸y t­¬ng øng nh­ sau:

1 – LOA A: T×m gi¸ trÞ cña A l­u tr÷ trong bé nhí vµ t¶i nã vµo thanh ghi.

2 – MUL B: T×m gi¸ trÞ cña B vµ nh©n nã víi gi¸ trÞ ®ang ë thanh ghi.

3 – ADD C: T×m gi¸ trÞ cña C vµ céng nã víi gi¸ trÞ trong thanh ghi.

4 – STO X: §­a gi¸ trÞ trong thanh ghi vµo l­u tr÷ ë vÞ trÝ t­¬ng øng cña X, trong bé nhí.

Trong c¸c ng«n ng÷ lËp tr×nh, biÓu thøc sè häc ®­îc viÕt nh­ d¹ng th«ng th­êng cña to¸n häc nghÜa lµ theo kÝ ph¸p trung tè (infix notation) mçi kÝ hiÖu cña phÐp to¸n hai ng«i ®­îc ®Æt gi÷a hai to¸n h¹ng, cã thÓ thªm dÊu ngoÆc.

Ch¼ng h¹n:    5*(7+3)

DÊu ngoÆc lµ cÇn thiÕt v× nÕu viÕt 5*7 + 3 th× theo qui ­íc vÒ thø tù ­u tiªn cña phÐp to¸n (mµ c¸c ng«n ng÷ lËp tr×nh ®Òu chÊp nhËn) th× biÓu thøc trªn nghÜa lµ lÊy 5 nh©n 7 ®­îc kÕt qu¶ céng víi 3.

Nhµ logic häc Balan Lukasiewicz ®· ®­a ra d¹ng biÓu thøc sè häc theo ký ph¸p hËu tè (postfix notation) vµ tiÒn tè (prefix notation) mµ ®­îc gäi lµ d¹ng ký ph¸p Balan.

ë d¹ng hËu tè c¸c to¸n tö ®i sau c¸c to¸n h¹ng. Nh­ biÓu thøc 5*(7+3) sÏ cã d¹ng: 5 7 3 - *

Cßn ë d¹ng tiÒn tè th× c¸c to¸n tö sÏ ®i tr­íc c¸c to¸n h¹ng. Khi ®ã biÓu thøc 5*(7+3) cã d¹ng: * 5 - 7 3

¤ng còng kh¼ng ®Þnh r»ng ®èi víi c¸c d¹ng ký ph¸p nµy dÊu ngoÆc lµ kh«ng cÇn thiÕt.

NhiÒu bé dÞch khi ®Þnh gi¸ biÓu thøc sè häc th­êng thùc biÖn: tr­íc hÕt chuyÓn c¸c biÓu thøc d¹ng trung tè cã dÊu ngoÆc sang d¹ng hËu tè, sau ®ã míi t¹o c¸c chØ thÞ m¸y ®Ó ®Þnh gi¸ biÓu thøc ë d¹ng hËu tè. ViÖc biÕn ®æi tõ d¹ng trung tè sang d¹ng d¹ng hËu tè kh«ng khã kh¨n g×, cßn viÖc ®Þnh gi¸ theo d¹ng hËu tè th× dÔ dµng h¬n, “m¸y mãc” h¬n so víi d¹ng trung tè.

§Ó minh ho¹ ta xÐt ®Þnh gi¸ cña biÓu thøc sau:

1 5 + 8 4 1 - - *

t­¬ng øng víi biÓu thøc th«ng th­êng: (1 + 5) * ( 8 - (4 – 1))

BiÓu thøc nµy ®­îc ®äc tõ tr¸i sang ph¶i cho tíi khi t×m ra mét to¸n tö. Hai to¸n h¹ng ®­îc ®äc cuèi cïng, tr­íc to¸n tö nµy, sÏ ®­îc kÕt hîp víi nã. Trong vi dô cña chóng ta th× to¸n tö ®Çu tiªn ®­îc ®äc lµ + vµ hai to¸n h¹ng t­¬ng øng víi nã lµ 1 vµ 5, sau khi kÕt hîp biÓu thùc con nµy cã gi¸ trÞ lµ 6, thay vµo ta cã biÓu thøc rót gän:

6 8 4 1 - - *

L¹i ®äc tõ tr¸i sang ph¶i, to¸n tö tiÕp theo lµ - vµ ta x¸c ®Þnh ®­îc 2 to¸n h¹ng cña nã lµ 4 vµ 1. Thùc hiÖn phÐp to¸n ta cã d¹ng rót gän:

6 8 3 - *

L¹i tiÕp tôc ta ®i tíi:

6 5 *

vµ cuèi cïng thùc hiÖn phÐp to¸n * ta cã kÕt qu¶ lµ 30.

Ph­¬ng ph¸p ®Þnh gi¸ biÓu thøc hËu tè nh­ trªn ®ßi hái ph¶i l­ tr÷ c¸c to¸n h¹ng cho tíi khi mét to¸n tö d­îc ®äc, t¹i thêi ®iÓm nµy hai to¸n h¹ng cuèi cïng ph¶i ®­îc t×m ra vµ kÕt hîp víi to¸n tö nµy. Nh­ vËy ë ®©y ®· xuÊt hiÖn c¬ chÕ ho¹t ®éng “vµo sau ra tr­íc” nghÜa lµ ta sÏ ph¶i sö dông tíi ng¨n xÕp dÓ l­u tr÷ c¸c to¸n h¹ng. Cø mçi lÇn ®äc ®­îc mét to¸n tö th× hai gi¸ trÞ sÏ ®­îc lÊy ra tõ ng¨n xÕp ®Ó ¸p ®Æt to¸n tö ®ã lªn chóng vµ kÕt qu¶ l¹i ®­îc ®Èy vµo ng¨n xÕp.

Gi¶i thuËt sau ®©y thÓ hiÖn c¸c ý trªn.

Program Dinh_Gia;

{gi¶i thuËt nµy sö dông ng¨n xÕp S ®Ó l­u tr÷ c¸c to¸n h¹ng ®äc tõ biÓu thøc}

1 – Repeat

   §äc phÇn tö X tiÕp theo trong biÓu thøc;

   if X lµ to¸n h¹ng then call PUSH(S, X)

            else begin

               call POP(S, Y);

               call POP(S, Z);

{ t¸c ®éng to¸n tö X lªn hai to¸n h¹ng Y vµ Z råi g¸n cho biÕn W}

W := Y (X) Z;

               PUSH(S, W);

            end;

Until gÆp dÊu kÕt thóc biÓu thøc;

2- POP(S, R);

   write(R);

end.

Sau ®©y lµ h×nh ¶nh minh häa viÖc thùc hiÖn gi¶i thuËt nµy víi biÓu thøc:

1 5 + 8 4 1 - - *

H×nh 4.9