Data structure and algorithm Queue แบบฝึกหัด

Data structure and algorithm Queue แบบฝึกหัด

ขอส่งงานที่สามนะครับ

1. จงอธิบายถึงสิ่งที่เหมือนกัน และสิ่งที่แตกต่างกันระหว่าง สแตก กับ คิว

สิ่งที่ สแตก กับ คิวเหมือนกันคือ สแตก กับ คิว จะมีคำสั่งที่นำค่าเข้าและนำออก โดยสแตกจะเรียกคำสั่งนำเข้าว่า push และนำออกเรียกว่า pop ส่วนคิวจะเรียกคำสั่งนำเข้าว่า enqueue และนำออกเรียกว่า dequeue ข้อแตกต่างคือ สแตกจะเป็นแบบ Last In First Out(LIFO) ส่วนคิวเป็นแบบ First In First Out(FIFO)

• Last In First Out(LIFO) หมายความว่าสิ่งที่ถูกแทรกเข้ามาล่าสุดจะถูกลบออกก่อน
• First In First Out(FIFO) หมายความว่าอะไรที่เข้าไปก่อน ก็จะออกก่อน

2. จงอธิบายถึงสิ่งที่เหมือนกัน และสิ่งที่แตกต่างกันระหว่าง คิวเส้นตรง กับ คิววงกลม

คิวทั่งสองแบบมีความเหมือนกันเกือบ 100% คือสามารถเพิ่มลบข้อมูลได้เหมือนกัน แต่เมื่อสแตกแบบเส้นตรงมีค่า rear (ท้าย) เท่ากับความจุของคิวแล้วและถึงจะมีตำแหน่งว่างเพราะลบค่าออกไปแล้วก็ตาม ก็จะไม่สามารถเพิ่มค่าเข้าไปได้อีก ส่วนคิวแบบวงกลมนั้นจะสามรถเพิ่มค่าเข้าไปได้จนกว่าคิว เหมือนเอาหัวหางของคิวมาต่อกันเป็นวงกลม

3. จงเขียนแผนภาพการดำเนินการตามขั้นตอนซึ่งมีข้อมูลในคิววงกลมดังนี้

4	0	- 5	10	NULL

1. deq (Q,x)

   NULL	0	- 5	10	NULL

2. enq (Q,2)

   NULL	0	- 5	10	2

3. deq (Q,x)

   NULL	NULL	- 5	10	2

4. deq (Q,x)

   NULL	NULL	NULL	10	2

5. enq (Q,-3)

   NULL	NULL	NULL	10	2

6. deq (Q,x)

   NULL	NULL	NULL	NULL	2

4. คิวขนาด 7 ค่ามีรายการต่อไปนี้

 front = 2 , rear = 5
 Queue[] = {null, null, "ขนุน”, “ส้มโอ”,”แตงโม”, “ฝรั่ง”, null}

จงแสงดผลของคิวแบบวงกลม โดยมีค่าเริ่มต้นตำแหน่งที่ 0 รวมทั้ง front และ rear เมื่อมีการกระทำต่อไปนี้

ก. เพิ่ม “มะม่วง”

front = 2 , rear = 6
Queue[] =  {null, null, "ขนุน”, “ส้มโอ”,”แตงโม”, “ฝรั่ง”, “มะม่วง”}

ข. นำ 2 รายการออกจากคิว

front = 4 , rear = 6
Queue[] =  {null, null, null, null,”แตงโม”, “ฝรั่ง”, “มะม่วง”}

ค. เพิ่ม “ทุเรียน”

front = 4 , rear = 0
Queue[] =  {“ทุเรียน”, null, null, null,”แตงโม”, “ฝรั่ง”, “มะม่วง”}

ง.เพิ่ม “องุ่น”

front = 4 , rear = 1
Queue[] =  {“ทุเรียน”, “องุ่น”, null, null,”แตงโม”, “ฝรั่ง”, “มะม่วง”}

จ. นำ 2 รายการออกจากคิว

front = 6 , rear = 1
Queue[] =  {“ทุเรียน”, “องุ่น”, null, null,null, null, “มะม่วง”}

ฉ. เพิ่ม “ละมุด”

front = 6 , rear = 2
Queue[] =  {“ทุเรียน”, “องุ่น”, “ละมุด”, null,null, null, “มะม่วง”}