CoE KKU

คิว (queue) ก็เป็นลิสต์เช่นเดียวกันกับ stack เพียงแต่สำหรับคิวแล้ว การ insert เกิดขึ้นที่ด้านหนึ่งในขณะที่การ delete เกิดขึ้นที่อีกด้านหนึ่งของโครงสร้างคิว

การทำงานพื้นฐานของ queue คือ enqueue ซึ่งเป็นการบรรจุสมาชิกใหม่เข้าทางด้านท้าย (เรียกว่า rear), และ dequeue ซึ่งเป็นการลบ (deletes และให้ค่ากลับ) สมาชิกจากทางด้านหน้าของลิสต์ (เรียกว่า front) รูปที่ 3.53 แสดงโมเดลของคิว

เช่นเดียวกับ stacks คือการทำงานที่ใช้กับลิสต์ก็สามารถใช้ได้กับคิว และเราสามารถใช้ได้ทั้งในแบบ linked list และในแบบอะเรย์เพื่อใช้งาน queue ซึ่งใช้เวลา running times เป็น O(1) สำหรับทุกการทำงาน ในที่นี้จะกล่าวถึงเฉพาะการใช้อะเรย์สำหรับคิวเท่านั้น

ในโครงสร้างข้อมูลของ queue ประกอบด้วยอะเรย์, theArray, และตำแหน่ง front และ back ซึ่งใช้แสดงตำแหน่งของหัวและตำแหน่งของท้ายของ queue และแสดงข้อมูลจำนวนสมาชิกที่อยู่ใน queue ด้วยค่าของ currentSize รูปข้างล่างนี้แสดงสถานะหนึ่งของคิว

เมื่อมีการนำสมาชิก x เข้าใน queue (คือ enqueue) เราจะเพิ่มค่า currentSize ขึ้น 1 จากนั้นก็จะกำหนดให้ค่า theArray[back] = x เมื่อจะนำสมาชิกออกจาก queue (คือ dequeue) จะมีการให้ค่ากลับเป็น theArray[front] และลดค่า currentSize ลง 1 และเพิ่มค่าให้แก่ front

ด้วยวิธีการที่กล่าวมานี้ หลังจากมีการ enqueue จำนวน 10 ครั้ง ทำให้ดูเหมือนว่าจะมีสมาชิกเต็มจำนวนในคิวแล้ว เนื่องจากค่า back จะอยู่ที่ตำแหน่งท้ายสุดของอะเรย์ อย่างไรก็ตาม ความจริงแล้วอาจจะมีจำนวนสมาชิกในคิวอยู่เพียงไม่กี่ค่าก็เป็นได้เนื่องจากอาจจะมีการ dequeue สมาชิกจำนวนหนึ่งออกไปจากคิวแล้ว ปกติแล้ว Queues จะมีขนาดไม่ใหญ่มากเช่นเดียวกันกับ stacks

ปัญหาดังที่กล่าวนี้สามารถแก้ไขได้ง่ายโดยเมื่อทั้ง front หรือ back มีค่าอยู่ที่ตำแหน่งสุดท้ายของอะเรย์ก็จะให้มีการม้วนกลับไปต้นอะเรย์ (เรียกการใช้งานอะเรย์ลักษณะนี้ว่า circular array implementation) กล่าวคือเมื่อ back หรือ front วิ่งไปจนสุดอะเรย์ก็จะถูกตั้งค่าตำแหน่งใหม่ให้เท่ากับตำแหน่งแรกของอะเรย์ ดังรูปข้างล่างนี้

Initial State

After enqueue(1)

After enqueue(3)

After dequeue which return 2

After dequeue which return 4

After dequeue which return 1

After dequeue which return 3 and Make the queue empty

คำสั่งการทำงานที่ต้องใช้ในการทำงานหมุนกลับก็มีเพียงเล็กน้อยเท่านั้นคือเพียงแต่ตั้งค่าให้กับ front และ back เป็นค่าตำแหน่งแรกของอะเรย์

รูปที่ 3.54 แสดงโครงร่างของคลาส queue รูปที่ 3.55 เป็น constructors และฟังก์ชัน makeEmpty ค่าเริ่มต้นของ back จะเป็นค่าที่ตามหลังค่า front อยู่ 1 รูปที่ 3.56 และ 3.57 เป็นฟังก์ชัน enqueue และ dequeue ตามลำดับ

// QueueAr class, Overflow thrown for enqueue on full queue
public class QueueAr 
{   public QueueAr( ) {/* Figure 3.55 */ }
    public QueueAr( int capacity ) {/* Figure 3.55 */ }
    public boolean isEmpty( ) { return currentSize == 0; }
    public boolean isFull( ) { return currentSize == theArray.length; }
    public void makeEmpty( ) {/* Figure 3.55 */ }
    public Object getFront( )   {   
      if( isEmpty( ) ) 
        return null;
		  return theArray[ front ];   
    }
 
    public Object dequeue( ) {/* Figure 3.57 */ }
    public void enqueue( Object x ) throws Overflow {/* Figure 3.56 */  }
 
    private int increment( int x ) {/* Figure 3.56 */ }
    private Object [ ] theArray;
    private int        currentSize;
    private int        front;
    private int        back;
    static final int DEFAULT_CAPACITY = 10;
}

รูปที่ 3.54 โครงร่างของคลาส queue

public QueueAr( )
{ this( DEFAULT_CAPACITY );     
}
 
public QueueAr( int capacity )
{ theArray = new Object[ capacity ];
  makeEmpty( );
}
 
public void makeEmpty( )
{ currentSize = 0;
  front = 0;
  back = -1;
}

รูปที่ 3.55 constructors และฟังก์ชัน makeEmpty

public void enqueue( Object x ) throws Overflow
{ if  ( isFull( ) )
    throw new Overflow( );
  back = increment( back );
  theArray[ back ] = x;
  currentSize++;
}
 
private int increment( int x )
{ if( ++x == theArray.length )
    x = 0;
  return x;
}

รูปที่ 3.56 ฟังก์ชัน enqueue

public Object dequeue( )
{ if ( isEmpty( ) )
    return null;
  currentSize--; 
  Object frontItem = theArray[ front ];
  theArray[ front ] = null;
  front = increment( front );
  return frontItem;
} 

รูปที่ 3.57 ฟังก์ชัน dequeue

มีอัลกอริทึมต่าง ๆ จำนวนมากที่ใช้โครงสร้างคิว ช่วยให้การทำงานเป็นไปอย่างมีประสิทธิภาพ โดยเฉพาะที่เกี่ยวข้องกับ graph theory ซึ่งจะกล่าวถึงในภายหน้า ในที่นี้จะแสดงตัวอย่างอย่างง่ายของการใช้คิว

ในการใช้งานเครื่องพิมพ์ของระบบที่เป็นเครือข่าย การจัดลำดับการให้บริการการพิมพ์ที่ล่งมายังเครื่องพิมพ์ก็เป็นไปตามลำดับของการ enqueue และ dequeue ที่กล่าวมาแล้ว คืองานพิมพ์ใหม่ที่ส่งมาจะถูกบรรจุลงท้ายลิสต์และงานที่จะพิมพ์ก็จะถูกนำมาจากหัวของลิสต์

ความจริงแล้วการดำเนินชีวิตประจำวันก็จะพบกับการทำงานแบบคิวอยู่เสมอ เช่นการเข้าแถวรอเพื่อซื้อตั๋วหรือเพื่อจ่ายเงินค่าสินค้าซึ่งลำดับการทำงานดังกล่าวนี้ที่เรียกว่า first-come first-served อีกตัวอย่างของการใช้คิวคือ การใช้บริการของเครื่อง server ในการทำงานแบบ file server ของระบบเครือข่ายคอมพิวเตอร์