หลักการใช้งานคิว Java
คำว่า "คิว" คือสิ่งที่ชาวอังกฤษเรียกว่า "คิว" "เพดานอินไลน์" ในสหราชอาณาจักรหมายถึงการยืนอยู่แถว ในวิทยาศาสตร์คอมพิวเตอร์คิวเป็นโครงสร้างข้อมูลซึ่งเป็นเหมือนสแต็กยกเว้นว่ารายการข้อมูลแรกที่แทรกในคิวจะถูกลบออกก่อนและในสแต็กรายการข้อมูลสุดท้ายที่แทรกจะถูกลบออกก่อน คิวทำงานเหมือนแถวของผู้คนที่ยืนอยู่หน้าโรงภาพยนตร์: คนแรกที่เข้ามาในเครือจะมาถึงหัวของทีมเพื่อซื้อตั๋ว คนสุดท้ายที่เข้าคิวสามารถซื้อตั๋วได้
คิวยังใช้เป็นเครื่องมือสำหรับโปรแกรมเมอร์เช่นสแต็ค นอกจากนี้ยังสามารถใช้เพื่อจำลองสภาพแวดล้อมในโลกแห่งความเป็นจริงเช่นการจำลองผู้คนที่รออยู่ในธนาคารเครื่องบินที่รอการถอดหรือแพ็คเก็ตบนอินเทอร์เน็ตกำลังรอการส่ง
ในระบบปฏิบัติการคอมพิวเตอร์คิวต่าง ๆ กำลังทำงานอย่างเงียบ ๆ งานพิมพ์กำลังรอการพิมพ์ในคิวการพิมพ์ เมื่อพิมพ์บนคีย์บอร์ดนอกจากนี้ยังมีคิวที่เก็บการพิมพ์ ในทำนองเดียวกันหากคีย์ถูกแตะด้วยตัวประมวลผลคำและคอมพิวเตอร์จะต้องทำอย่างอื่นชั่วคราวเนื้อหาที่ถูกเคาะจะไม่หายไปและจะรอในคิวจนกว่าตัวประมวลผลคำมีเวลาอ่าน คิวใช้เพื่อให้แน่ใจว่าลำดับการพิมพ์จะไม่เปลี่ยนแปลงเมื่อประมวลผล
การดำเนินการขั้นพื้นฐานของคิว
การดำเนินการพื้นฐานสองประการของคิวกำลังแทรก (แทรก) รายการข้อมูลนั่นคือวางรายการข้อมูลหนึ่งรายการลงในหางของคิวและอีกรายการหนึ่งกำลังลบ (ลบ) รายการข้อมูลนั่นคือลบรายการข้อมูลที่หัวของทีม สิ่งนี้คล้ายกับคนรักภาพยนตร์ที่เข้าคิวจนถึงจุดสิ้นสุดของบรรทัดเมื่อพวกเขาเข้าคิวเพื่อซื้อตั๋วจากนั้นมาถึงหัวของบรรทัดแล้วออกจากคิว
การตั้งชื่อวิธีการสำหรับการแทรกและลบรายการข้อมูลในสแต็กเป็นมาตรฐานมากเรียกว่า push และ pop วิธีการคิวยังไม่ได้รับการตั้งชื่อตามมาตรฐาน "แทรก" สามารถเรียกได้ว่าใส่เพิ่มหรือ enque ในขณะที่ "ลบ" สามารถเรียกได้ว่าลบรับหรือ deque ส่วนท้ายของรายการข้อมูลการแทรกสามารถเรียกกลับหางหรือปลาย หัวหน้าทีมที่ลบรายการข้อมูลสามารถเรียกได้ว่า Head แทรกลบด้านหน้าและด้านหลังจะถูกนำมาใช้ด้านล่าง
แทรกแทรกค่าลงในหางของคิวและหางของลูกศรคิวจะถูกเพิ่มลงเพื่อชี้ไปที่รายการข้อมูลใหม่
หลังจากลบรายการข้อมูลแล้วหัวหน้าทีมจะถูกเพิ่มโดยหนึ่ง โดยปกติเมื่อใช้คิวรายการข้อมูลที่ถูกลบจะถูกบันทึกไว้ในหน่วยความจำ แต่ไม่สามารถเข้าถึงได้เนื่องจากหัวของคิวถูกย้ายไปยังตำแหน่งถัดไป
รายการข้อมูลในคิวไม่เหมือนกรณีในสแต็กไม่ได้เริ่มต้นที่ 0 ตัวห้อยของอาร์เรย์เสมอไป หลังจากลบรายการข้อมูลบางส่วนตัวชี้ส่วนหัวชี้ไปยังตำแหน่งตัวห้อยสูงกว่า
การดำเนินการดูส่งคืนค่าของรายการข้อมูลส่วนหัว แต่ไม่ลบรายการข้อมูลออกจากทีม
หากคุณต้องการลบรายการข้อมูลออกจากคิวเปล่าหรือแทรกรายการข้อมูลลงในคิวเต็มรูปแบบแอปพลิเคชันจะแจ้งข้อความแสดงข้อผิดพลาด
ลูปคิว
เมื่อรายการข้อมูลใหม่ถูกแทรกเข้าไปในคิวลูกศรด้านหลังที่หัวของทีมจะเลื่อนขึ้นไปยังตำแหน่งขนาดใหญ่ของตัวห้อยอาร์เรย์ เมื่อลบรายการข้อมูลหางของตัวชี้ด้านหน้าคิวก็จะเลื่อนขึ้นไป การออกแบบนี้อาจตรงกันข้ามกับการสังเกตโดยตรงของผู้คนเพราะเมื่อผู้คนเข้าแถวสำหรับตั๋วภาพยนตร์คิวจะเดินไปข้างหน้าเสมอและหลังจากบุคคลที่อยู่ข้างหน้าพวกเขาซื้อตั๋วและออกจากคิวคนอื่น ๆ ก็ก้าวไปข้างหน้า หลังจากลบรายการข้อมูลในคิวในคอมพิวเตอร์คุณสามารถย้ายรายการข้อมูลอื่น ๆ ทั้งหมดไปข้างหน้าได้ แต่นี่ก็มีประสิทธิภาพมาก แต่เราเก็บรายการข้อมูลทั้งหมดไว้ในตำแหน่งเดียวกันผ่านการเคลื่อนไหวของหัวและหางพอยน์เตอร์ของคิว
ปัญหาเกี่ยวกับการออกแบบนี้คือตัวชี้หางจะย้ายไปยังจุดสิ้นสุดของอาร์เรย์อย่างรวดเร็ว แม้ว่าจะมีหน่วยรายการข้อมูลที่ว่างเปล่าที่จุดเริ่มต้นของอาร์เรย์ซึ่งเป็นที่ตั้งของรายการข้อมูลที่ถูกลบ แต่เนื่องจากตัวชี้หางไม่สามารถเลื่อนไปข้างหลังได้อีกต่อไปรายการข้อมูลใหม่จึงไม่สามารถแทรกได้ ฉันควรทำอย่างไร?
การรักษา
เพื่อหลีกเลี่ยงปัญหาของคิวที่ไม่พอใจ แต่ไม่สามารถแทรกรายการข้อมูลใหม่ได้ตัวชี้ศีรษะและหางสามารถห่อกลับไปที่จุดเริ่มต้นของอาร์เรย์ นี่คือคิวลูป (บางครั้งก็เรียกว่า "แหวนบัฟเฟอร์")
กระบวนการห่อตัวชี้: แทรกรายการข้อมูลเพียงพอลงในคิวเพื่อให้ตัวชี้หางชี้ไปที่ปลายสายของอาร์เรย์ ลบรายการข้อมูลอีกสองสามรายการที่ปลายด้านหน้าของอาร์เรย์ ตอนนี้แทรกรายการข้อมูลใหม่ คุณจะเห็นว่าตัวชี้หางจะถูกย้อนกลับจากจุดสิ้นสุดไปยังตำแหน่งเริ่มต้น รายการข้อมูลใหม่จะถูกแทรกลงในตำแหน่งนี้
แทรกรายการข้อมูลเพิ่มเติม ตัวชี้หางขยับขึ้นไปตามที่คาดไว้ โปรดทราบว่าหลังจากตัวชี้หางกลับมาอีกครั้งตอนนี้อยู่ใต้ตัวชี้หัวซึ่งจะกลับตำแหน่งเริ่มต้น สิ่งนี้สามารถเรียกได้ว่า "ลำดับที่เสีย": รายการข้อมูลในคิวมีอยู่ในสองลำดับที่แตกต่างกันในอาร์เรย์
หลังจากลบรายการข้อมูลที่เพียงพอแล้วหัวหน้าทีมก็พันรอบ ในเวลานี้ตัวชี้คิวกลับไปที่สถานะตำแหน่งที่รันไทม์เริ่มต้นและตัวชี้หัวอยู่ด้านล่างตัวชี้หาง รายการข้อมูลจะถูกกู้คืนไปยังลำดับต่อเนื่องเดียว
รหัส Java สำหรับคิว
โปรแกรม queue.java สร้างคลาสคิวซึ่งมีการแทรก (), ลบ (), peek (), isempty () และขนาด () วิธีการ
แพ็คเกจสแต็กและคิว;
คิวคลาส {ส่วนตัว int maxsize; ยาวส่วนตัว [] quearray; ด้านหน้าส่วนตัว ด้านหลัง int ส่วนตัว; NITEMS INT ส่วนตัว; คิวสาธารณะ (int s) {maxSize = s; quearray = ใหม่ยาว [maxsize]; ด้านหน้า = 0; ด้านหลัง = -1; nitems = 0; } การแทรกโมฆะสาธารณะ (ยาว j) {ถ้า (ด้านหลัง == maxSize-1) ด้านหลัง = -1; quearray [++ ด้านหลัง] = j; NITEMS ++; } สาธารณะยาวลบ () {temp ยาว = quearray [front ++]; if (front == maxSize) front = 0; NITEMS-; กลับอุณหภูมิ; } สาธารณะยาว peekfront () {return quearray [front]; } บูลีนสาธารณะ isempty () {return (nitems == 0); } บูลีนสาธารณะ iffull () {return (nitems == maxsize); } ขนาด int สาธารณะ () {return nitems; -คลาสคิวที่ดำเนินการโดยโปรแกรมไม่เพียง แต่มีด้านหน้า (หัว) และด้านหลัง (หัวของทีม) แต่ยังรวมถึงจำนวนรายการข้อมูลปัจจุบันในคิว: nitems
ข้อกำหนดเบื้องต้นสำหรับการทำงานของ วิธีการแทรก () คือคิวไม่พอใจ วิธีนี้ไม่ได้แสดงใน Main () แต่ควรใช้วิธีการแทรก () ก่อนและควรเรียกวิธี Isfull () หลังจากกลับเท็จ (วิธีการทั่วไปเพิ่มเติมคือการเพิ่มการตัดสินลงในวิธีการแทรก () เพื่อตรวจสอบว่าคิวเต็มหรือไม่หากรายการข้อมูลถูกแทรกลงในคิวเต็มรูปแบบจะถูกโยนข้อยกเว้น)
โดยทั่วไปการดำเนินการแทรกคือการเพิ่มด้านหลัง (ตัวชี้หางทีม) และแทรกข้อมูลใหม่ที่ตำแหน่งที่ชี้ไปที่ตัวชี้หาง อย่างไรก็ตามเมื่อตัวชี้ด้านหลังชี้ไปที่ด้านบนของอาร์เรย์เช่นตำแหน่ง MaxSize-1 จะต้องถูกแผลกลับไปที่ด้านล่างของอาร์เรย์ก่อนที่จะแทรกรายการข้อมูล การดำเนินการที่คดเคี้ยวตั้งค่าด้านหลังเป็น -1 ดังนั้นเมื่อเพิ่มด้านหลัง 1 จะเท่ากับ 0 ซึ่งเป็นค่าตัวห้อยที่ด้านล่างของอาร์เรย์และในที่สุดก็ถูกเพิ่ม nitem
ข้อกำหนดเบื้องต้นสำหรับการทำงานของ วิธีการลบ () คือคิวไม่ว่างเปล่า ก่อนที่จะเรียกวิธีการนี้คุณควรเรียกใช้วิธี isEmpty () เพื่อให้แน่ใจว่าคิวไม่ว่างเปล่าหรือเพิ่มกลไกการตรวจสอบข้อผิดพลาดนี้ลงในวิธีการลบ ()
การดำเนินการ ลบ จะได้รับค่าของรายการข้อมูลส่วนหัวจากตัวชี้ด้านหน้าเสมอจากนั้นเพิ่มด้านหน้า อย่างไรก็ตามหากคุณทำเช่นนั้นค่าของด้านหน้าเกินด้านบนของอาร์เรย์ด้านหน้าจะต้องกลับไปที่ตำแหน่งที่ตัวห้อยของอาร์เรย์คือ 0 ในขณะที่ทำการทดสอบนี้ค่าคืนจะถูกเก็บไว้ชั่วคราว ในที่สุด Nitem ก็ลดลงหนึ่ง
วิธี PEEK () นั้นง่ายและเข้าใจง่าย: มันส่งคืนค่าของรายการข้อมูลที่ชี้ไปที่ตัวชี้ด้านหน้า การใช้คิวบางอย่างยังอนุญาตให้ดูค่าของรายการข้อมูลคิว end; ตัวอย่างเช่นวิธีการเหล่านี้สามารถเรียกได้ว่า peekfront (), peekrear () หรือเพียงแค่ด้านหน้า () และด้านหลัง ()
การใช้ วิธี isempty (), isfull () และขนาด () ทั้งหมดนั้นขึ้นอยู่กับฟิลด์ NITEMS ซึ่งส่งคืนว่า nitems เท่ากับ 0 ไม่ว่าจะเท่ากับ maxsize หรือคืนค่าของตัวเอง
การรวมฟิลด์การนับรายการข้อมูล NITEMS ในคลาสคิวจะเพิ่มการดำเนินการพิเศษเล็กน้อยในวิธีการแทรก () และลบ () เนื่องจากวิธีการแทรก () และลบ () ต้องเพิ่มและลดค่าของตัวแปรนี้ตามลำดับ นี่อาจไม่ใช่ค่าใช้จ่ายเพิ่มเติม แต่ถ้าคุณจัดการกับการแทรกและการดำเนินการจำนวนมากสิ่งนี้อาจส่งผลกระทบต่อประสิทธิภาพ
เนื่องจากการใช้คิวบางอย่างไม่ใช้ฟิลด์ของการนับรายการข้อมูล แต่ใช้ด้านหน้าและด้านหลังเพื่อคำนวณว่าคิวว่างเปล่าหรือเต็มและจำนวนรายการข้อมูล หากคุณทำเช่นนี้ isempty (), iffull () และขนาด () รูทีนจะค่อนข้างซับซ้อนเพราะดังที่ได้กล่าวไว้ก่อนหน้านี้ลำดับของรายการข้อมูลจะถูกยุบเป็นสองส่วนหรือส่วนต่อเนื่อง
และปัญหาแปลก ๆ เกิดขึ้น เมื่อคิวเต็มตัวพอยน์เตอร์ด้านหน้าและด้านหลังจะอยู่ในตำแหน่งที่แน่นอน แต่เมื่อคิวว่างเปล่าความสัมพันธ์ตำแหน่งเดียวกันอาจปรากฏขึ้น ดังนั้นในเวลาเดียวกันคิวอาจดูเหมือนจะเต็มหรือว่างเปล่า วิธีการแก้ปัญหานี้คือ: ทำให้ความจุอาเรย์เป็นหนึ่งมากกว่าจำนวนข้อมูลคิวสูงสุดสูงสุด
ขอบคุณสำหรับการอ่านฉันหวังว่ามันจะช่วยคุณได้ ขอบคุณสำหรับการสนับสนุนเว็บไซต์นี้!