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 ถูกดึงออกไป
สิ้นสุด
จะพบว่า ไม่มีเล่มใดที่ซ้ำกัน ในเรียงอยู่ในชั้นนี้ หลังจากผ่านกระบวนการเสร็จแล้วครับ
ไม่มีความคิดเห็น:
แสดงความคิดเห็น
น้ำใจเล็กน้อยๆก็แค่คำว่า ขอบคุณ...