Thailand OI: คอมพิวเตอร์โอลิมปิก ประเทศไทย

สวัสดีครับทุกท่าน

เอนทรี่แรกของผมเอนทรี่นี้จะเป็นการขอแนะนำกระบวนการทำงานเกี่ยวกับโครงสร้างข้อมูล (Data Structure) พื้นฐานรูปแบบหนึ่ง ที่เรียกกันว่า stack และ queue ครับ

ทั้งนี้ Stack และ Queue เป็นโครงสร้างข้อมูลที่คล้ายๆกัน ทำให้มักจะมีการกล่าวถึงควบคู่กันไปเสมอๆ ก่อนอื่น มาเริ่มกันที่ความหมายของทั้งสองคำก่อนดีกว่า

Stack คืออะไร?

Stack คือโครงสร้างข้อมูลที่มีลักษณะเรียกกันว่า LiFo (Last in First out) หมายถึง การเข้าทีหลังและนำออกก่อน หรือ เข้าก่อนออกทีหลัง นั่นเองครับ ในการใช้ชีวิตประจำวันของเราเองก็มีกระบวนการในลักษณะเช่นเดียวกับ Stack อาทิเช่น กล่อง CD-R แฟ้มเอกสารแบบหนีบ รวมถึงการจัดเรียงของแนวตั้งทุกชนิด ทั้งนี้สังเกตว่าการจะหยิบออกต้องหยิบจากบน(อันที่ใส่ล่าสุด) ลงล่าง (อันที่ใส่ทีหลัง) เสมอๆ หรือก็คือลักษณะของ “กองซ้อน” นั่นเองครับ

Queue คืออะไร?

Queue คือโครงสร้างข้อมูลที่มีลักษณะเรียกกันว่า FiFo (First in First out) ซึ่งหมายถึงการเข้าก่อน ออกก่อนครับ ในชีวิตประจำวันของเรานั้นมักจะพบกระบวนการในลักษณะของ Queue อยู่เสมอๆ เช่น การต่อแถวคอย หรือการต่อคิว ซึ่งเป็นที่รู้กันอยู่แล้วว่า ผู้ที่มาก่อนก็ย่อมได้รับสิทธิการบริการก่อนนั่นเอง

การทำงานของ Stack and Queue

Stack นั้นจะมีการทำงานที่เรียกกันว่า push สำหรับการเพิ่มค่าเข้าไปในชุดข้อมูลด้านบน และ pop แทนการนำข้อมูลบนสุดออกมา ยกตัวอย่างเช่น

มีชุดข้อมูล A ประกอบด้วย [1,2,3,8,4,7]

เมื่อ push [a] เข้าไป จะได้ชุดข้อมูล A ประกอบด้วย [1,2,3,8,4,7,a] และเมื่อทำการ pop จะได้ค่า [a] ออกมาและทำให้ A กลับไปเป็น [1,2,3,8,4,7] เหมือนเดิมครับ

เพื่อให้เห็นภาพกระบวนการที่ชัดเจนมากขึ้น จะขอยกตัวอย่างโจทย์พื้นฐานสำหรับการฝึกใช้เบื้องต้นสักข้อนึงนะครับ

ตั้งหนังสือ

นายหัวหอมเป็นสมาชิกชุมนุมห้องสมุดโรงเรียนแห่งหนึ่ง วันนี้เป็นเวรของเขาในการทำการเรียงหนังสือในหมวดหนังสือนวนิยาย แต่ทว่า เขาเกิดเบื่อ จึงชวนนายหอมหัวมาเล่นเกมส์เรียงหนังสือกับเขา โดยกติกาการเล่นมีอยู่ว่า

เริ่มต้น นายหัวหอมจะจัดเรียงหนังสือจำนวน n เล่ม ในแต่ละเล่มจะมีจำนวนหน้า i(j) หน้า หลังจากนั้นนายหัวหอมจะสามารถหยิบหนังสือออกหนึ่งเล่ม หรือนำหนังสือเล่มใหม่ใส่มาเพิ่มก็ได้ หลังจากนายหัวหอมพอใจแล้ว นายหอมหัวจะต้องตอบว่าหนังสือที่อยู่บนสุดมีจำนวนกี่หน้า

ตัวอย่าง

เริ่มต้น 210 247 132 154 256 131 741

push 175

pop

push 143

push 19

pop

pop

pop

pop

pop

pop

จะได้ว่า หนังสือเล่มที่อยู่บนสุดมีจำนวนทั้งสิ้น 132 หน้า

บางคนอาจมองไม่ออก งั้นเราลองมาดูลำดับเหตุการณ์กันก่อนนะครับ

เริ่มต้น {210,247,132,154,256,131,741}

push 175 {210,247,132,154,256,131,741,175} // 175 เพิ่มขึ้นจากทางด้านหลัง

pop {210,247,132,154,256,131,741} // 175 ถูกเอาออกไป

push 143 {210,247,132,154,256,131,741,143} // 143 ถูกเพิ่มเข้ามา

push 19 {210,247,132,154,256,131,741,143,19} // 19 ถูกเพิ่มเข้ามา

pop {210,247,132,154,256,131,741,143} // 19 ถูกเอาออกไป

pop {210,247,132,154,256,131,741} // 143 ถูกเอาออกไป

pop {210,247,132,154,256,131} // 741 ถูกเอาออกไป

pop {210,247,132,154,256} // 131 ถูกเอาออกไป

pop {210,247,132,154} // 256 ถูกเอาออกไป

pop {210,247,132} // 154 ถูกเอาออกไป

สิ้นสุด

สุดท้าย จะได้เล่มที่อยู่บนสุด มีจำนวนทั้งสิ้น 132 หน้าตามที่ตอบไว้เบื้องต้นนั่นเอง

โจทย์เพิ่มเติม

หลังจากที่นายหอมหัวสามารถเอาชนะเกมส์นี้ได้อย่างง่ายดาย นายหัวหอมจึงอัพเกรดการเล่นขึ้น โดนมีกติกาที่เปลี่ยนไปดังนี้

“หลังจากทำการเรียงใหม่ตามใจชอบแล้ว นามหอมหัวจะต้องบอกจำนวนหน้าทั้งหมดของตั้งหนังสือทั้งหมดที่เหลืออยู่”

++

ในส่วนของ Queue หรือแถวคอยนั้น จะประกอบไปด้วยคำสั่งหลักๆคือ enqueue และ dequeue แทนที่ push และ pop ครับ อย่างเช่นว่า

มีชุดข้อมูล A = [1,8,7,6,3]

เมื่อทำการ enqueue [a] เข้าไปจะได้เป็น A = [1,8,7,6,3,a] และเมื่อทำการ dequeue นั้น จะได้ [1] ออกมาและทำให้ A = [8,7,6,3,a] ครับ

ลองมาดูโจทย์เบื้องต้นในส่วนของ Queue กันเลยดีกว่า

เรียงหนังสือ

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

ในชั้นหนังสือหนึ่งชั้น นายหอมหัวจะมีสิทธิในการเอาหนังสือที่อยู่หน้าสุดออกและเพิ่มหนังสือเล่มใหม่เข้าไปด้านหลัง โดยจะบอกแค่ว่า หนังสือแต่ละเล่มนั้นเป็นเล่มที่เท่าไรในนวนิยายมหากาพย์ โคนาน ซึ่งมีออกมาแล้วมากกว่า 60 เล่ม นายหัวหอมจะต้องตอบเพียงสั้นๆว่า ในชั้นหนังสือชั้นนั้นหลังจากผ่านกระบวนการแล้วยังมีเล่มที่ซ้ำกันอยู่หรือไม่

ตัวอย่าง

เริ่มต้น 1,2,7,2,4,6,8

enqueue 5

dequeue

dequeue

enqueue 1

enqueue 3

dequeue

ตอบ ไม่มีเล่มที่ซ้ำกัน

เริ่มต้น {1,2,7,2,4,6,8}

enqueue 5 {1,2,7,2,4,6,8,5} // 5 ถูกต่อเข้ามา

dequeue {2,7,2,4,6,8,5} // 1 ถูกหยิบออกไป

dequeue {7,2,4,6,8,5} // 2 ถูกหยิบออกไป

enqueue 1 {7,2,4,6,8,5,1} // 1 ถูกเพิ่มเข้ามา

enqueue 3 {7,2,4,6,8,5,1,3} // 3 ถูกเพิ่มเข้ามา

dequeue {2,4,6,8,5,1,3} // 7 ถูกดึงออกไป

สิ้นสุด

จะพบว่า ไม่มีเล่มใดที่ซ้ำกัน ในเรียงอยู่ในชั้นนี้ หลังจากผ่านกระบวนการเสร็จแล้วครับ

Stack and Queue กับการเขียนโปรแกรม

ในการทำโจทย์ทางคอมพิวเตอร์นั้น บางครั้งที่ Stack and Queue เข้ามามีบทบาทร่วมกับกระบวนการคิดอื่นๆ

ทั้งนี้ Stack and Queue ย่อมตั้งใช้ร่วมกับข้อมูลในรูปแบบที่เป็น Array หรือ Linked List

และนอกจากนี้ยังมี STL สำหรับ Stack และ Queue ไว้รองรับการใช้งานอยู่แล้วครับ

ซึ่งส่วนนี้จะขอกล่าวถึงต่อไปในตอนต่อไปนะครับ ^^

ถ้ามีใครสงสัยตรงจุดไหน ฝากคำถามไว้ทางคอมเมนท์ได้เลยนะครับ ’ w ‘