HÀNG Đ IỢ
(Font: Courier New)
Cũng nh ngăn x p, hàng đ i là CTDL tuy n tính. Hàng đ iư ế ợ ế ợ
là m t danh sách các đ i t ng, m t đ u c a danh sách đ cộ ố ượ ộ ầ ủ ượ
xem là đ u hàng đ i, còn đ u kia c a danh sách đ c xem làầ ợ ầ ủ ượ
đuôi hàng đ i. V i hàng đ i, chúng ta ch có th xen m t đ iợ ớ ợ ỉ ể ộ ố
t ng m i vào đuôi hàng và lo i đ i t ng đ u hàng raượ ớ ạ ố ượ ở ầ
kh i hàng. Trong ch ng này chúng ta s nghiên c u cácỏ ươ ẽ ứ
ph ng pháp cài đ t hàng đ i và trình bày m t s ng d ngươ ặ ợ ộ ố ứ ụ
c a hàng đ i.ủ ợ
1, KI U D LI U TR U T NG HÀNG Đ IỂ Ữ Ệ Ừ ƯỢ Ợ
Trong m c này chúng ta s đ c t KDLTT hàng đ i. Chúngụ ẽ ặ ả ợ
ta có th xem m t hàng ng i đ ng x p hàng ch đ c ph c vể ộ ườ ứ ế ờ ượ ụ ụ
(ch ng h n, x p hàng ch mua vé tàu, x p hàng ch giao d chẳ ạ ế ờ ế ờ ị
ngân hàng, …) là m t hàng đ i, b i vì ng i ra kh i hàngở ộ ợ ở ườ ỏ
và đ c ph c v là ng i đ ng đ u hàng, còn ng i m i đ nượ ụ ụ ườ ứ ở ầ ườ ớ ế
s đ ng vào đuôi hàng.ẽ ứ
Hàng đ i là m t danh sách các đ i t ng d li u, m tợ ộ ố ượ ữ ệ ộ
trong hai đ u danh sách đ c xem là đ u hàng, còn đ u kiaầ ượ ầ ầ
là đuôi hàng. Ch ng h n, hàng đ i có th là danh sách cácẳ ạ ợ ể
ký t (a, b, c, d), trong đó a đ ng đ u hàng, còn d đ ngự ứ ở ầ ứ
đuôi hàng. Chúng ta có th th c hi n các phép toán sauở ể ự ệ
đây trên hàng đ i, trong các phép toán đó Q là m t hàngợ ộ
đ i, còn x là m t đ i t ng cùng ki u v i các đ i t ngợ ộ ố ượ ể ớ ố ượ
trong hàng Q.
1. Empty(Q). Hàm tr v true n u hàng Q r ng và falseả ề ế ỗ
n u không.ế
2. Enqueue(x, Q). Thêm đ i t ng x vào đuôi hàng Q.ố ượ
3. Dequeue(Q). Lo i đ i t ng đ ng đ u hàng Q.ạ ố ượ ứ ở ầ
4. GetHead(Q). Hàm tr v đ i t ng đ ng đ u hàng Q,ả ề ố ượ ứ ở ầ
còn hàng Q thì không thay đ i.ổ
Ví d .ụ
N u Q = (a, b, c, d) và a đ u hàng, d đuôi hàng, thìế ở ầ ở
khi th c hi n phép toán Enqueue(e, Q) ta nh n đ c Q = (a,ự ệ ậ ượ
b, c, d, e), v i e đ ng đuôi hàng, n u sau đó th c hi nớ ứ ở ế ự ệ
phép toán Dequeue(Q), ta s có Q = (b, c, d, e) và b trẽ ở
thành ph n t đ ng đ u hàng.ầ ử ứ ở ầ
V i các phép toán Enqueue và Dequeue xác đ nh nh trênớ ị ư
thì đ i t ng vào hàng tr c s ra kh i hàng tr c. Vì lýố ượ ướ ẽ ỏ ướ
do đó mà hàng đ i đ c g i là c u trúc d li u FIFO (vi tợ ượ ọ ấ ữ ệ ế
t t c a c m t First- In First- Out). Đi u này đ i l p v iắ ủ ụ ừ ề ố ậ ớ
ngăn x p, trong ngăn x p đ i t ng ra kh i ngăn x p là đ iế ế ố ượ ỏ ế ố
t ng sau cùng đ c đ t vào ngăn x p.ượ ượ ặ ế
Hàng đ i s đ c s d ng trong b t kỳ hoàn c nh nào màợ ẽ ượ ử ụ ấ ả
chúng ta c n x lý các đ i t ng theo trình t FIFO. Cu iầ ử ố ượ ự ố
ch ng này chúng ta s trình bày m t ng d ng c a hàng đ iươ ẽ ộ ứ ụ ủ ợ
trong mô ph ng m t h ph c v . Nh ng tr c h t chúng ta c nỏ ộ ệ ụ ụ ư ướ ế ầ
nghiên c u các ph ng pháp cài đ t hàng đ i. Cũng nh ngănứ ươ ặ ợ ư
x p, chúng ta có th cài đ t hàng đ i b i m ng ho c b iế ể ặ ợ ở ả ặ ở
DSLK.
2, CÀI Đ T HÀNG Đ I B I M NGẶ Ợ Ở Ả
Cũng nh ngăn x p, chúng ta có th cài đ t hàng đ i b iư ế ể ặ ợ ở
m ng. Song cài đ t hàng đ i b i m ng s ph c t p h n ngănả ặ ợ ở ả ẽ ứ ạ ơ
x p. Nh l i r ng, khi cài đ t danh sách (ho c ngăn x p)ế ớ ạ ằ ặ ặ ế
b i m ng thì các ph n t c a danh sách (ho c ngăn x p) sở ả ầ ử ủ ặ ế ẽ
đ c l u trong đo n đ u c a m ng, còn đo n sau c a m ng làượ ư ạ ầ ủ ả ạ ủ ả
không gian ch a s d ng đ n. Chúng ta có th làm nh thư ử ụ ế ể ư ế
v i hàng đ i đ c không? Câu tr l i là có, nh ng khôngớ ợ ượ ả ờ ư
hi u qu . Gi s chúng ta s d ng m ng element đ l u cácệ ả ả ử ử ụ ả ể ư
ph n t c a hàng đ i, các ph n t c a hàng đ i đ c l uầ ử ủ ợ ầ ử ủ ợ ượ ư
trong các thành ph n m ng element[0], element[1],…,ầ ả
element[k] nh trong hình 1a. V i cách này, ph n t đ uư ớ ầ ử ở ầ
hàng luôn luôn đ c l u trong thành ph n m ng element[0],ượ ư ầ ả
còn ph n t đuôi hàng đ c l u trong element[k], và do đóầ ử ở ượ ư
ngoài m ng element ta ch c n m t bi n tail ghi l i ch sả ỉ ầ ộ ế ạ ỉ ố
k. Đ thêm ph n t m i vào đuôi hàng, ta ch c n tăng ch sể ầ ử ớ ỉ ầ ỉ ố
tail lên 1 và đ t ph n t m i vào thành ph n m ngặ ầ ử ớ ầ ả
element[tail]. Song n u mu n lo i ph n t đ u hàng, chúngế ố ạ ầ ử ở ầ
ta c n chuy n lên trên m t v trí t t c các ph n t đ cầ ể ộ ị ấ ả ầ ử ượ
l u trong element[1],…, element[tail] và gi m ch s tail điư ả ỉ ố
1, và nh v y tiêu t n nhi u th i gian.ư ậ ố ề ờ
===========================================================
====
element
0 1 2 3 4
SIZE – 1
tail
(a)
element
0 1 2 3 4 5 6
SIZE – 1
head tail
(b)
6
7
5 0
8
4
9
3
2
1
0 SIZE – 1
head
tail
(c)
===========================================================
====
Hình 1: Các ph ng pháp cài đ t hàng đ iươ ặ ợ
b i m ngở ả
Đ kh c ph c nh c đi m c a ph ng pháp trên, chúng taể ắ ụ ượ ể ủ ươ
l u các ph n t c a hàng đ i trong m t đo n con c a m ng tư ầ ử ủ ợ ộ ạ ủ ả ừ
ch s đ u head t i ch s đuôi tail, t c là các ph n t c aỉ ố ầ ớ ỉ ố ứ ầ ử ủ
hàng đ i đ c l u trong các thành ph n m ng element[head],ợ ượ ư ầ ả
element[head + 1], … , element[tail], nh trong hình 7.1b.ư
V i cách cài đ t này, ngoài m ng element, chúng ta c n sớ ặ ả ầ ử
d ng hai bi n: bi n ch s đ u head và bi n ch s đuôiụ ế ế ỉ ố ầ ế ỉ ố
tail. Đ lo i ph n t đ u hàng chúng ta ch c n tăng chể ạ ầ ử ở ầ ỉ ầ ỉ
s head lên 1. Chúng ta có nh n xét răng, khi thêm ph n tố ậ ầ ử
m i vào đuôi hàng thì ch s tail tăng, khi lo i ph n t ớ ỉ ố ạ ầ ử ở
đ u hàng thì ch s head tăng, t i m t th i đi m nào đó hàngầ ỉ ố ớ ộ ờ ể
đ i s chi m đo n cu i c a m ng, t c là bi n tail nh n giáợ ẽ ế ạ ố ủ ả ứ ế ậ
tr SIZE – 1 ( SIZE là c c a m ng). Lúc đó ta không thị ỡ ủ ả ể
thêm ph n t m i vào đuôi hàng, m c d u không gian ch a sầ ử ớ ặ ầ ư ử
d ng trong m ng, đo n đ u c a m ng t ch s 0 t i head – 1,ụ ả ạ ầ ủ ả ừ ỉ ố ớ
có th còn r t l n! Đ gi i quy t v n đ này, chúng taể ấ ớ ể ả ế ấ ề
“cu n” m ng thành vòng tròn, nh đ c minh ho trong hìnhộ ả ư ượ ạ
7.1c. Trong m ng vòng tròn, chúng ta xem thành ph n ti pả ầ ế
theo thành ph n element[SIZE - 1] là thành ph n element[0].ầ ầ
V i m ng vòng tròn, khi thêm ph n t m i vào đuôi hàng, n uớ ả ầ ử ớ ế
ch s tail có giá tr là SIZE – 1, ta đ t tail = 0 và l uỉ ố ị ặ ư
ph n t m i trong thành ph n m ng element[0]. T ng t khiầ ử ớ ầ ả ươ ự
ph n t đ u hàng đ c l u trong element[SIZE - 1], thì đầ ử ở ầ ượ ư ể
lo i nó, ta ch c n đ t head = 0. Do đó, n u cài đ t hàngạ ỉ ầ ặ ế ặ
đ i b i m ng vòng tròn, thì phép toán thêm ph n t m i vàoợ ở ả ầ ử ớ
đuôi hàng không th c hi n đ c ch khi m ng th c s đ y, t cự ệ ượ ỉ ả ự ự ầ ứ
là khi trong m ng không còn thành ph n nào ch a s d ng.ả ầ ư ử ụ
Sau đây chúng ta s nghiên c u s cài đ t hàng đ i b iẽ ứ ự ặ ợ ở
m ng vòng tròn. KDLTT hàng đ i s đ c cài đ t b i l pả ợ ẽ ượ ặ ở ớ
Queue, đây là l p khuôn ph thu c tham bi n ki u Item,ớ ụ ộ ế ể
trong đó Item là ki u c a các ph n t trong hàng đ i. L pể ủ ầ ử ợ ớ
Queue ch a các bi n thành ph n nào? Các ph n t c a hàngứ ế ầ ầ ử ủ
đ i đ c l u trong m ng vòng tròn đ c c p phát đ ng, do đóợ ượ ư ả ượ ấ ộ
c n có bi n con tr element tr t i thành ph n đ u tiên c aầ ế ỏ ỏ ớ ầ ầ ủ
m ng đó, bi n size l u c c a m ng, bi n ch s đ u head vàả ế ư ỡ ủ ả ế ỉ ố ầ
bi n ch s đuôi tail. Ngoài các bi n trên, chúng ta thêmế ỉ ố ế
vào m t bi n length đ l u đ dài c a hàng đ i (t c là sộ ế ể ư ộ ủ ợ ứ ố
ph n t trong hàng đ i). L p Queue đ c đ nh nghĩa nh trongầ ử ợ ớ ượ ị ư
hình 7.2.
Code:
template <class Item>
class Queue
{
public :
Queue (int m = 1);
// Hàm ki n t o hàng đ i r ng v i dung l ng là m,ế ạ ợ ỗ ớ ượ
// m nguyên d ng (t c là c m ng đ ng là m).ươ ứ ỡ ả ộ
Queue (const Queue & Q) ;
// Hàm ki n t o copy.ế ạ
~ Queue( ) // Hàm hu .ỷ
{ delete [ ] element ; }
Queue & operator = (const Queue & Q); // Toán t gán.ử