Queue
อาจารย์สุวิชยะ รัตตะรมย์
สำนักวิชาเทคโนโลยีสารสนเทศและการสื่อสาร
หัวข้อวันนี้
2
3
ลักษณะของคิวในชีวิตประจำวัน
ADT : Value Definition of Queue
4
ADT : Operation definition of Queue
5
Implementation : Accessing Queue
6
A
B
C
empty
empty
empty
front
rear
ข้อมูลออก
ข้อมูลเข้า
Implementation : enqueue , dequeue
7
8
D
C
B
A
Queue[4]
init(Queue)
enqueue(‘A’,Queue)
enqueue(‘B’,Queue)
X = dequeue(Queue)
enqueue(‘C’,Queue)
enqueue(‘D’,Queue)
Y = dequeue(Queue)
X = dequeue(Queue)
4
3
2
1
front = 0
1
1
2
2
2
3
4
rear = 0
1
2
2
3
4
4
4
Implementation of Queue �(static memory allocation)
9
10
#define MAXQUEUE 10 //กำหนดขนาดของคิว
typedef struct
{
int data[MAXQUEUE]; // กำหนดเป็นคิวของ int โดยใช้ array
int front; // กำหนด front index
int rear; // กำหนด rear index
} QUEUE;
QUEUE Q;
11
ต้องกำหนดค่าเริ่มต้นให้กับคิว
pseudo code ฟังก์ชัน queue_init()
12
function queue_init ( queue )
front = -1 ;
rear = -1 ;
end function
ปัญหาในการ implement queue
13
ปัญหา underflow ในสแตกและคิว
14
สแตกที่สร้างโดยอาร์เรย์ ขนาด 4 ช่อง
front=-1
rear=-1
คิวสร้างโดยอาร์เรย์ ขนาด 4 ช่อง
top=-1
pop
dequeue
ปัญหา overflow ในสแตกและคิว
15
1
4
5
2
7
สแตกที่สร้างโดยอาร์เรย์ ขนาด 4 ช่อง
C
B
A
D
front
rear
คิวสร้างโดยอาร์เรย์ ขนาด 4 ช่อง
top
push
D
enqueue
pseudo code ฟังก์ชัน enqueue()
function enqueue ( data , queue )
// ตรวจสอบว่าคิวเต็มหรือไม่
if rear == MAXQUEUE-1 then
message( “QUEUE FULL!!!” )
else
rear = rear + 1
queue[rear] = data
// ถ้า insert ลงในคิวว่าง
if front == -1 then
front = 0
end if
end if
end function
16
empty
empty
empty
empty
front = rear = -1
pseudo code ฟังก์ชัน dequeue()
function dequeue ( queue )
// ถ้าคิวว่าง
if front == -1 then
message( “QUEUE EMPTY!!!” )
else
return queue[front]
// ถ้าในคิวมีข้อมูลเพียงตัวเดียว
if front == rear then
front = rear = -1
else
front = front + 1
end if
end if
end function
17
empty
A
empty
empty
front
rear