+ cấu trúc dữ liệu :

1-định nghĩa :

Queue là một danh sách tuyến tính trong đó việc bổ xung một phần tử vào danh sách được thực hiện ở một đầu gọi là tail( lốisau), và việc lấy một phần tử ra khỏi danh sách được thực hiện ở một đầu gọi là head( lối trước ).

 Cơ chế hoạt động của Queue là cơ chế FIFO( firts in firts out), có nghĩa là phần tử nào được đưa vào trước sẽ được lấy ra trước và phần tử nào được đưa vào sau sẽ được lấy ra sau.

2-biểu diễn dữ liệu :

BIỂU DIỄN QUEUE BẰNG MẢNG

 Có thể dùng một véc tơ lưu trữ có n phần tử để lưu trữ Queue. Để truy nhập vào Queue ta phải dùng hai biến trỏ, tail để trỏ vào lối sau và head để trỏ vào lối trước

Nhược điểm: queue sau khi dử dụng 1 thời gian không sử dụng được nữa.

Khắc phục: để sử dụng lại queue mảng thì queue phải là queue vòng.

Queue vòng

+định nghĩa :

 Queue vòng là queue được biểu diễn bằng mảng mà phần tử cuối danh sách thay vì mang giá trị NULL sẽ trỏ tới phần tử đầu danh sách.

Biểu diễn bằng danh sách móc nối:

Mỗi phần tử đưa vào Queue sẽ có hai trường, một dùng để lưu trữ giá trị của phần tử, một để lưu trữ địa chỉ của phần tử tiếp theo. Đồng thời chúng ta đưa vào hai con trỏ, tail dùng để trỏ tới cuối hàng và head dùng để trỏ tới đầu hàng

3-các phép toán :

*Các phép toán khi queue được biểu diễn bằng mảng

Const int size=100;

Struct queue {

Int A[size];

Int f, r ; } ;

// Khởi tạo queue .

Void init(queue &q)

{ q.f=q.r=0 ; }

// Kiểm tra xem queue có rỗng không .

Int isempty(const queue &q)

{ return (q.f=q.r) ; }

// Kiểm tra xem queue có đầy không .

Int isfull(const queue &q)

{ return (q.r=size) ; }

// Đẩy 1 phần tử vào queue .

Void push(queue &q ; int d)

{ if(isfull(q))

{ cout <<"

queue is full !" ; return ; }

q.A[ q.r++]=d ;

}

// Lấy 1 phần tử ra khỏi queue .

Int pop(queue &q)

{ if( isempty(q))

{ cout <<"

queue is empty !" ; return 0 ; }

Return q.A[ q.f++] ;

}

*Các phép toán khi queue được biểu diễn bằng danh sách móc nối (FIFO)

Struct node

{ item data ; node *link ; } ;

Struct queue

{ node *f ; *r ; } ;

// Khởi tạo queue .

Void init(queue &q)

{ q.f=q.r=0 ; }

// Kiểm tra xem queue có rỗng không .

Int isempty(queue &q)

{ return (q.f==0) ; }

// Kiểm tra xem queue có đầy không .

Int isfull( )

{ node *p = new node ;

if(!p) return -1; delete p ; }

return 0 ;

// Đẩy 1 phần tử vào queue .

Void push(queue &q , item 1)

{ if(isfull())

{ cout<<"

queue is full !" return; }

Node *p=new node; p->data=d;

p=link=0;

if( q.f==0 )

{ q.f=q.r=p; return ;}

q.r->link=p; q.r=p; }

// Lấy 1 phần tử ra khỏi queue .

Item pop(queue &q)

{ node *p ;

if(isempty(q))

{ cout<<"

queue is empty !"; return 0;}

p=q.f; q.f=q*f->link; item d=p->data;

delete p; return d;

}

- tư tưởng :

- thủ tục :

- độ phức tạp thuật toán

+ Giải thuật :

1-tư tưởng :

2-thủ tục tổng quát

Ứng dụng

 Queue thường được thiết kế trong bộ vi xử lý , trong các chương trình quản lý tiến trình của hệ điều hành, cấp quyền ưu tiên cho các hoạt động đặc biệt .....

 Queue thương được sử dụng trong 1 số giải thuật đối với cây & đồ thị