บัฟเฟอร์แบบวงกลมหรือคิวแบบวงกลมเป็นเวอร์ชันขั้นสูงของคิวปกติที่ดัชนีสุดท้ายและดัชนีส่วนท้ายเชื่อมต่อกันในโครงสร้างแบบวงกลม บัฟเฟอร์แบบวงกลมใน C ++ มีสองวิธี: enqueue() และ dequeue() เราดำเนินการบัฟเฟอร์แบบวงกลมหรือคิวแบบวงกลมตามวิธีการเหล่านี้
- เมธอด enqueue() จะตรวจสอบว่าบัฟเฟอร์เต็มหรือไม่ มิฉะนั้นให้ตรวจสอบว่าดัชนีสิ้นสุดเป็นอันสุดท้าย หากเป็นเช่นนั้น ให้ตั้งค่าส่วนท้ายเป็น 0 หากไม่ใช่ ให้เพิ่มค่าส่วนท้ายตามค่าที่ดัชนีนั้น
- ฟังก์ชัน dequeue() รับค่าจากดัชนีด้านหน้าในคิวแบบวงกลม หากคิวว่าง ข้อความจะแสดงคิวว่างนั้น มิฉะนั้นจะได้รับค่าสุดท้ายและลบออกจากคิว
โปรแกรมสำหรับใช้บัฟเฟอร์แบบวงกลมในภาษา C++
ตามสองวิธีที่กล่าวถึง เราใช้บัฟเฟอร์แบบวงกลมใน C++ ลองพิจารณาขั้นตอนทั้งหมดสำหรับการนำคิวแบบวงกลมไปใช้ในภาษา C++
#รวม
ใช้เนมสเปซมาตรฐาน;
โครงสร้าง MyQueue
{
ภายใน ศีรษะ , หาง ;
int Qsize;
ภายใน * นิวอาร์;
มายคิว ( หมายเลขภายใน ) {
ศีรษะ = หาง = -1 ;
Qsize = ขนาด;
NewArr = อินท์ใหม่ [ ส ] ;
}
ถือเป็นโมฆะในคิว ( วาลอินท์ ) ;
int deQueue ( ) ;
โมฆะการแสดงคิว ( ) ;
} ;
เริ่มต้นด้วยโค้ด ก่อนอื่นเราจะสร้างโครงสร้าง 'MyQueue' เพื่อเริ่มต้นตัวแปร head และ tail ตัวแปรส่วนหัวแสดงถึงดัชนีด้านหน้า และส่วนท้ายแสดงถึงดัชนีด้านหลังของอาร์เรย์ หลังจากนั้น ขนาดของคิวแบบวงกลมซึ่งแสดงด้วยตัวแปร 'Qsize' จะถูกกำหนด
จากนั้นเรากำหนดอาร์เรย์ที่จัดสรรแบบไดนามิกของ 'NewArr' ซึ่งจะเก็บค่าของคิวแบบวงกลม ต่อไป เราเรียก MyQueue() ซึ่งเป็น Constructor และส่งผ่านพารามิเตอร์ “sz” สำหรับขนาดคิวแบบวงกลม ภายในตัวสร้าง MyQueue() เรากำหนดค่า '-1' ให้กับพอยน์เตอร์ส่วนหัวและส่วนท้าย ค่าลบนี้บ่งชี้ว่าคิวว่างเปล่าในขณะนี้ ก้าวไปข้างหน้า เราจะกำหนดค่า 'sz' ที่แสดงถึงขนาดของคิวแบบวงกลม คิวแบบวงกลม “NewArr” ถูกตั้งค่าด้วยคีย์เวิร์ดใหม่เพื่อสร้างอาร์เรย์ของจำนวนเต็มภายในขนาด “sz” ที่ระบุ
จากนั้นเรากำหนดฟังก์ชัน enQueue() และ dequeue() enqueue() แทรกค่าลงในคิวแบบวงกลมที่กำหนดจากส่วนท้าย อย่างไรก็ตาม องค์ประกอบในส่วนหัวของคิวแบบวงกลมจะถูกกำจัดโดยฟังก์ชัน dequeue() ฟังก์ชันสมาชิก showQueue() จะแสดงค่าของคิวแบบวงกลม
ขั้นตอนที่ 1: สร้างฟังก์ชันเพื่อแทรกองค์ประกอบในบัฟเฟอร์แบบวงกลม
ในขั้นตอนก่อนหน้านี้ เราตั้งค่าคลาสที่สมาชิกส่วนตัวจะถูกเตรียมใช้งาน และฟังก์ชันสมาชิกส่วนตัวถูกตั้งค่าให้ใช้คิวแบบวงกลม ตอนนี้เราตั้งค่าฟังก์ชันเพื่อสร้างคิวแบบวงกลมและแทรกค่าภายในคิวแบบวงกลมโดยใช้อัลกอริทึม
เป็นโมฆะ MyQueue::enQueue ( วาลอินท์ ){
ถ้า ( ( ศีรษะ == 0 && หาง == ไซส์ Q- 1 ) || ( หาง == ( ศีรษะ - - 1 ) % ( ขนาดไซส์ - 1 ) ) )
{
ศาล << ' \n คิวเต็มแล้ว” ;
กลับ ;
}
อื่น ถ้า ( ศีรษะ == - == - 1 )
{
ศีรษะ = หาง = 0 ;
ใหม่อาร์ [ หาง ] = วาล;
}
อื่น ถ้า ( หาง == ไซส์ Q- 1 && ศีรษะ ! = 0 )
{
หาง = 0 ;
ใหม่อาร์ [ หาง ] = วาล;
}
อื่น {
หาง ++;
ใหม่อาร์ [ หาง ] = วาล;
}
}
ที่นี่เราเรียกฟังก์ชัน 'enqueue()' จากคลาส 'MyQueue' เพื่อแทรกองค์ประกอบในคิวแบบวงกลมหากคิวว่างเปล่าหรือน้อยเกินไป ฟังก์ชัน 'enqueue()' ถูกส่งผ่านด้วยพารามิเตอร์ 'val' และแทรกค่าจากส่วนท้ายของคิวแบบวงกลม เราตั้งค่าเงื่อนไข 'if-else' เพื่อแทรกค่าในคิวแบบวงกลมสำหรับสิ่งนี้ คำสั่ง “if” คำสั่งแรกซึ่งก็คือ “if ((head == 0 && tail == Qsize – 1) || (tail == (head – 1) % (Qsize – 1)))” ตรวจสอบสองเงื่อนไขว่า head อยู่ที่ตำแหน่งเริ่มต้นและส่วนท้ายอยู่ที่ตำแหน่งสิ้นสุดของคิวแบบวงกลม จากนั้นตรวจสอบว่าหางอยู่ในตำแหน่งเดียวที่ด้านหลังศีรษะหรือไม่ หากตรงตามเงื่อนไขใดๆ เหล่านี้ คิวจะไม่ว่างเปล่า และพร้อมท์จะสร้างข้อความ
ต่อไป เรามีเงื่อนไข 'else-if' ที่ระบุว่าคิวว่างเปล่าหรือไม่ หากเป็นเช่นนั้น ค่าจะถูกแทรกลงในคิว เนื่องจากส่วนหัวมีค่าเท่ากับ -1 นั่นแสดงว่าคิวว่างเปล่าและจำเป็นต้องแทรกค่าในคิวแบบวงกลม สำหรับสิ่งนี้ เราตั้งค่า head และ tail เท่ากับ 0 จากนั้น เราแทรกค่าจากตำแหน่ง tail ลงในคิวแบบวงกลม “NewArr”
จากนั้น เรามีเงื่อนไข 'else-if' ประการที่สาม ซึ่งจะตรวจสอบว่าส่วนท้ายอยู่ที่ตำแหน่งสุดท้ายของคิวหรือไม่ และส่วนหัวไม่ใช่ตำแหน่งเริ่มต้นของคิว เงื่อนไขนี้ใช้เมื่อหางถึงจุดสิ้นสุดและตำแหน่งเริ่มต้นยังคงมีที่ว่าง สำหรับสิ่งนี้ เราต้องตั้งค่าส่วนหัวเป็น 0 และเพิ่มองค์ประกอบจากตำแหน่งส่วนท้าย สุดท้ายนี้ หากไม่ตรงตามเงื่อนไขที่กำหนดทั้งหมด คิวจะไม่ว่างหรือเต็ม ในกรณีนี้ เราจะเพิ่มส่วนท้ายขึ้น 1 และเพิ่มค่าจากตำแหน่งส่วนท้ายใหม่
ขั้นตอนที่ 2: สร้างฟังก์ชันเพื่อลบองค์ประกอบออกจากบัฟเฟอร์แบบวงกลม
เราตั้งค่าโค้ดก่อนหน้าเพื่อสร้างและแทรกองค์ประกอบในคิวแบบวงกลมโดยใช้ฟังก์ชัน enqueue() ตอนนี้ เรากำหนดการนำไปใช้ในการลบองค์ประกอบออกจากบัฟเฟอร์แบบวงกลมถ้ามันล้น
int MyQueue::deQueue ( ){
ถ้า ( ศีรษะ == - == - 1 )
{
ศาล << ' \n คิวว่าง' ;
กลับ INT_MIN;
}
int MyData = NewArr [ ศีรษะ ] ;
ใหม่อาร์ [ ศีรษะ ] = -1 ;
ถ้า ( ศีรษะ == หาง )
{
ศีรษะ = -1 ;
หาง = -1 ;
}
อื่น ถ้า ( ศีรษะ == ไซส์ Q- 1 )
ศีรษะ = 0 ;
อื่น
ศีรษะ ++;
กลับ ข้อมูลของฉัน;
}
ในโค้ดที่กำหนด เราเรียกฟังก์ชัน dequeue() จากคลาส 'Myqueue' เพื่อลบองค์ประกอบออกจากดัชนีส่วนหัว ดังนั้นเราจึงมีคำสั่ง 'if' เพื่อตรวจสอบว่าคิวว่างหรือไม่ หัวถูกตั้งค่าด้วยค่า “-1” ที่แสดงถึงคิวว่าง ข้อความถูกสร้างขึ้นว่าคิวว่างเปล่า จากนั้นส่งคืน INT_MIN ซึ่งเป็นค่าต่ำสุดคงที่สำหรับ int คำสั่ง 'if' กำหนดว่าคิวว่างหรือไม่ สำหรับสิ่งนี้ เรากำหนดตัวแปร 'MyData' และตั้งค่าขององค์ประกอบที่ส่วนหัวของคิว จากนั้นเราตั้งค่าส่วนหัวไว้ที่ตำแหน่ง -1 ซึ่งบ่งชี้ว่าค่านี้ถูกลบออกจากคิว หลังจากนั้นเราตรวจสอบว่าหัวและหางเท่ากันหรือไม่ หากทั้งสองเท่ากัน เราจะกำหนดค่า '-1' ให้กับทั้งสอง ซึ่งแสดงถึงคิววงกลมที่ว่างเปล่า สุดท้ายนี้ เราจะตรวจสอบว่า dequeue() ทำงานหรือไม่ ถ้าส่วนหัวอยู่ที่ดัชนีสุดท้ายของคิว สำหรับสิ่งนี้ เราตั้งค่าด้วยค่า '0' ซึ่งจะวนรอบที่จุดเริ่มต้นของอาร์เรย์ หากไม่มีเงื่อนไขใดเป็นจริง ค่าของส่วนหัวจะเพิ่มขึ้นและส่งคืนองค์ประกอบที่แยกออกจากคิวแล้ว
ขั้นตอนที่ 3: สร้างฟังก์ชันเพื่อแสดงองค์ประกอบของบัฟเฟอร์แบบวงกลม
ในส่วนนี้ เราเรียกใช้ฟังก์ชัน showQueue() เพื่อแสดงองค์ประกอบของคิวแบบวงกลม “NewArr”
เป็นโมฆะ MyQueue::showQueue ( ){
ถ้า ( ศีรษะ == - == - 1 )
{
ศาล << ' \n คิวว่าง' ;
กลับ ;
}
ศาล << ' \n องค์ประกอบคิวแบบวงกลม: ' ;
ถ้า ( หาง > = ศีรษะ )
{
สำหรับ ( อินท์ ไอ = ศีรษะ ; ฉัน < = หาง ; ฉัน++ )
ศาล << ใหม่อาร์ [ ฉัน ] << ' ' ;
}
อื่น
{
สำหรับ ( อินท์ ไอ = ศีรษะ ; ฉัน < ขนาดคิวไซส์; ฉัน++ )
ศาล << ใหม่อาร์ [ ฉัน ] << ' ' ;
สำหรับ ( อินท์ ไอ = 0 ; ฉัน < = หาง ; ฉัน++ )
ศาล << ใหม่อาร์ [ ฉัน ] << ' ' ;
}
}
สถานะว่างของคิวได้รับการตรวจสอบก่อน การบ่งชี้ว่าคิวแบบวงกลมว่าง จะแสดงขึ้นหากคิวว่าง มิฉะนั้นฟังก์ชันจะแสดงองค์ประกอบของคิวแบบวงกลม สำหรับสิ่งนี้ เรากำหนดคำสั่ง 'if' โดยที่ส่วนท้ายมีค่ามากกว่าหรือเท่ากับส่วนหัว เงื่อนไขนี้ถูกตั้งค่าให้จัดการกรณีและปัญหาเมื่อคิวแบบวงกลมไม่เสร็จสมบูรณ์
ในกรณีนี้ เราใช้ลูป 'for' เพื่อวนซ้ำตั้งแต่หัวจรดท้ายและพิมพ์ค่าของคิวแบบวงกลม กรณีถัดไปคือที่คิวแบบวงกลมเสร็จสมบูรณ์ สำหรับสิ่งนี้ เราตรวจสอบโดยใช้เงื่อนไข “ถ้า” โดยที่หางน้อยกว่าหัว จากนั้น เราจำเป็นต้องใช้สองลูป โดยที่อันแรกวนซ้ำจากส่วนหัวไปยังจุดสิ้นสุดของคิว และอันที่สองวนซ้ำจากจุดเริ่มต้นของส่วนท้าย
ขั้นตอนที่ 4: สร้างฟังก์ชัน Main() ของโปรแกรม Circular Queue
สุดท้ายนี้ เราสร้างฟังก์ชัน main() ของโปรแกรมโดยที่เราแทรกจำนวนเต็มห้าตัวในคิวแบบวงกลมและแสดงจำนวนเต็มของคิว หลังจากนั้น เราจะแสดงจำนวนเต็มที่ถูกลบออกจากคิวแบบวงกลมโดยการเรียกใช้ฟังก์ชัน dequeue() หลังจากถอนคิวองค์ประกอบบางส่วนแล้ว เราจะเติมคิวอีกครั้งโดยการแทรกองค์ประกอบใหม่โดยใช้ฟังก์ชัน enqueue()
int หลัก ( ){
คิวของฉันนั้น ( 5 ) ;
// การแทรกองค์ประกอบ ใน คิวแบบวงกลม
que.enคิว ( สิบเอ็ด ) ;
que.enคิว ( 12 ) ;
que.enคิว ( 13 ) ;
que.enคิว ( 14 ) ;
que.enคิว ( สิบห้า ) ;
// มีองค์ประกอบการแสดงผลอยู่ ใน คิวแบบวงกลม
que.showQueue ( ) ;
// การลบองค์ประกอบออกจากคิวแบบวงกลม
ศาล << ' \n องค์ประกอบที่ถูกลบ = ' << que.deQueue ( ) ;
ศาล << ' \n องค์ประกอบที่ถูกลบ = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enคิว ( 16 ) ;
que.enคิว ( 17 ) ;
que.enคิว ( 18 ) ;
que.showQueue ( ) ;
กลับ 0 ;
}
เอาท์พุท:
ผลลัพธ์ของการนำคิวแบบวงกลมไปใช้จะแสดงบนหน้าจอพร้อมท์ C++
บทสรุป
โดยสรุป หัวข้อบัฟเฟอร์แบบวงกลมได้รับการอธิบายอย่างลึกซึ้งในบทความนี้ เราสร้างบัฟเฟอร์แบบวงกลมก่อน จากนั้นอธิบายวิธีการลบออกจากคิวแบบวงกลม จากนั้นจึงแสดงองค์ประกอบของแบบวงกลมใน C++