เนื้อหา

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

Stack และ Queue ทั้งคู่เป็นโครงสร้างข้อมูลที่ไม่ใช่แบบดั้งเดิม ความแตกต่างที่สำคัญระหว่างสแต็กและคิวคือสแต็กที่ใช้วิธี LIFO (เข้าก่อนออกก่อน) เพื่อเข้าถึงและเพิ่มองค์ประกอบข้อมูลในขณะที่คิวใช้วิธี FIFO (เข้าก่อนออกก่อน) เพื่อเข้าถึงและเพิ่มองค์ประกอบข้อมูล

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

สแต็คและคิวเป็นโครงสร้างข้อมูลที่ใช้สำหรับการจัดเก็บองค์ประกอบข้อมูลและขึ้นอยู่กับความเป็นจริงในโลกที่เทียบเท่า ตัวอย่างเช่นสแต็กเป็นสแต็กของซีดีที่คุณสามารถนำออกและใส่ในซีดีผ่านด้านบนของสแต็คของซีดี ในทำนองเดียวกันคิวเป็นคิวสำหรับตั๋วโรงละครที่บุคคลที่ยืนอยู่ในสถานที่แรกคือด้านหน้าของคิวจะได้รับการเสิร์ฟก่อนและคนใหม่ที่มาถึงจะปรากฏที่ด้านหลังของคิว (ท้ายสุดของคิว)

1. แผนภูมิเปรียบเทียบ
2. คำนิยาม
3. ความแตกต่างที่สำคัญ
4. การดำเนินงาน
5. การดำเนินงาน
6. การประยุกต์ใช้งาน
7. ข้อสรุป

แผนภูมิเปรียบเทียบ

พื้นฐานสำหรับการเปรียบเทียบ	กอง	คิว
หลักการทำงาน	LIFO (เข้าก่อนออกก่อน)	FIFO (เข้าก่อนออกก่อน)
โครงสร้าง	ปลายเดียวกันใช้สำหรับแทรกและลบองค์ประกอบ	ปลายด้านหนึ่งใช้สำหรับการแทรกเช่นปลายด้านหลังและปลายอีกด้านใช้สำหรับการลบองค์ประกอบเช่นปลายด้านหน้า
จำนวนพอยน์เตอร์ที่ใช้	หนึ่ง	สอง (ในกรณีคิวง่าย)
ประกอบกิจการดำเนินการ	กดและป๊อป	enqueue และ dequeue
การตรวจสภาพที่ว่างเปล่า	บน == -1	ด้านหน้า == -1 || ด้านหน้า == ด้านหลัง + 1
การตรวจสภาพสมบูรณ์	== สูงสุด - 1	ด้านหลัง == สูงสุด - 1
สายพันธุ์	มันไม่มีตัวแปร	มันมีตัวแปรเช่นคิววงกลม, ลำดับความสำคัญ, คิวสิ้นสุดลงสองเท่า
การดำเนินงาน	ที่เรียบง่าย	ค่อนข้างซับซ้อน

ความหมายของสแต็ค

สแต็คเป็นโครงสร้างข้อมูลเชิงเส้นที่ไม่ใช่แบบดั้งเดิม มันเป็นรายการสั่งซื้อที่มีการเพิ่มรายการใหม่และองค์ประกอบที่มีอยู่จะถูกลบออกจากปลายด้านเดียวเท่านั้นที่เรียกว่าเป็นด้านบนของสแต็ค (TOS) เมื่อการลบและการแทรกในสแต็กเสร็จสิ้นจากด้านบนของสแต็คองค์ประกอบสุดท้ายที่เพิ่มเข้ามาจะเป็นรายการแรกที่จะถูกลบออกจากสแต็ก นี่คือเหตุผลที่สแต็กถูกเรียกว่ารายการประเภท Last-in-First-out (LIFO)

โปรดทราบว่าองค์ประกอบที่เข้าถึงบ่อยในสแต็กเป็นองค์ประกอบสูงสุดในขณะที่องค์ประกอบสุดท้ายที่มีอยู่ในด้านล่างของสแต็ก

ตัวอย่าง

บางท่านอาจกินขนมปังกรอบ (หรือ Poppins) หากคุณสันนิษฐานว่ามีเพียงด้านเดียวที่ถูกฉีกขาดและบิสกิตจะถูกนำออกไปทีละคน นี่คือสิ่งที่เรียกว่า popping และในทำนองเดียวกันหากคุณต้องการเก็บบิสกิตบางอย่างในเวลาต่อมาคุณจะนำพวกเขากลับเข้าไปในกลุ่มผ่านปลายฉีกขาดเดียวกันที่เรียกว่าการผลัก

คำจำกัดความของคิว

คิวเป็นโครงสร้างข้อมูลเชิงเส้นมาในหมวดหมู่ของประเภทที่ไม่ใช่ดั้งเดิม มันคือชุดขององค์ประกอบประเภทที่คล้ายกัน การเพิ่มองค์ประกอบใหม่จะเกิดขึ้นที่ปลายด้านหนึ่งที่เรียกว่าปลายด้านหลัง ในทำนองเดียวกันการลบองค์ประกอบที่มีอยู่จะเกิดขึ้นที่ปลายอีกด้านหนึ่งเรียกว่า Front-end และจะเป็นรายการประเภท First in first out (FIFO) ตามหลักเหตุผล

ตัวอย่าง

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

1. สแต็คติดตามกลไก LIFO บนมืออื่น ๆ คิวตามกลไก FIFO เพื่อเพิ่มและลบองค์ประกอบ
2. ในสแต็กปลายเดียวกันจะใช้ในการแทรกและลบองค์ประกอบ ในทางตรงกันข้ามปลายที่แตกต่างกันสองจะใช้ในคิวเพื่อแทรกและลบองค์ประกอบ
3. ในฐานะที่เป็นสแต็กมีปลายเปิดเดียวที่เป็นสาเหตุของการใช้ตัวชี้เดียวเพื่ออ้างอิงถึงด้านบนของสแต็ก แต่คิวใช้สองพอยน์เตอร์เพื่ออ้างอิงส่วนหน้าและส่วนท้ายของคิว
4. สแต็คดำเนินการสองอย่างที่เรียกว่าการพุชและป๊อปในขณะที่อยู่ในคิวมันจะเรียกว่าคิวและคิว
5. การใช้สแต็กนั้นง่ายกว่าในขณะที่การใช้คิวนั้นยุ่งยาก
6. คิวมีหลากหลายรูปแบบเช่นคิวแบบวงกลม, ลำดับความสำคัญ, คิวที่สิ้นสุดเป็นสองเท่า ฯลฯ ในทางกลับกันสแต็กไม่มีตัวแปร

การใช้งานสแต็ก

สแต็กสามารถใช้ได้สองวิธี:

1. การใช้งานแบบคงที่ ใช้อาร์เรย์เพื่อสร้างสแต็ก การใช้งานแบบสแตติกนั้นเป็นเทคนิคที่ไม่ต้องใช้ความพยายาม แต่ไม่ใช่วิธีการสร้างที่ยืดหยุ่นเนื่องจากการประกาศขนาดของสแต็กจะต้องทำในระหว่างการออกแบบโปรแกรมหลังจากนั้นขนาดไม่สามารถเปลี่ยนแปลงได้ นอกจากนี้การใช้งานแบบสแตติกไม่ได้มีประสิทธิภาพมากนักเกี่ยวกับการใช้หน่วยความจำ เนื่องจากอาร์เรย์ (สำหรับการนำสแต็กไปใช้) ถูกประกาศไว้ก่อนเริ่มการดำเนินการ (ณ เวลาออกแบบโปรแกรม) ตอนนี้ถ้าจำนวนขององค์ประกอบที่จะเรียงน้อยกว่าในสแต็คหน่วยความจำที่จัดสรรแบบคงที่จะสูญเปล่า ในทางกลับกันหากมีองค์ประกอบจำนวนมากที่จะถูกเก็บไว้ในสแต็คเราจะไม่สามารถเปลี่ยนขนาดของอาเรย์เพื่อเพิ่มความจุเพื่อให้สามารถรองรับองค์ประกอบใหม่ได้
2. การใช้งานแบบไดนามิก เรียกอีกอย่างว่าการเชื่อมโยงการแสดงรายการและใช้พอยน์เตอร์เพื่อใช้โครงสร้างข้อมูลประเภทสแต็ก

การใช้งานคิว

คิวสามารถนำมาใช้ได้สองวิธี:

1. การใช้งานแบบคงที่: หากคิวถูกนำมาใช้โดยใช้อาร์เรย์จำนวนองค์ประกอบที่แน่นอนที่เราต้องการเก็บไว้ในคิวจะต้องมั่นใจก่อนเพราะขนาดของอาร์เรย์จะต้องมีการประกาศในเวลาออกแบบหรือก่อนที่จะเริ่มการประมวลผล ในกรณีนี้การเริ่มต้นของอาเรย์จะกลายเป็นด้านหน้าของคิวและตำแหน่งสุดท้ายของอาเรย์จะทำหน้าที่เป็นด้านหลังของคิว ความสัมพันธ์ต่อไปนี้ให้องค์ประกอบทั้งหมดที่มีอยู่ในคิวเมื่อดำเนินการโดยใช้อาร์เรย์:
   ด้านหน้า - หลัง + 1
   หาก“ ด้านหลัง <ด้านหน้า” จะไม่มีองค์ประกอบอยู่ในคิวหรือคิวจะว่างเปล่าเสมอ
2. การใช้งานแบบไดนามิก: การใช้งานคิวโดยใช้พอยน์เตอร์ข้อเสียเปรียบหลักคือโหนดในการเชื่อมโยงการแทนใช้พื้นที่หน่วยความจำมากกว่าองค์ประกอบที่สอดคล้องกันในการแทนอาร์เรย์ เนื่องจากมีอย่างน้อยสองเขตข้อมูลในแต่ละโหนดหนึ่งสำหรับเขตข้อมูลและอื่น ๆ เพื่อเก็บที่อยู่ของโหนดต่อไปในขณะที่ในการเชื่อมโยงเป็นตัวแทนการเชื่อมโยงเฉพาะเขตข้อมูลที่มี ข้อดีของการใช้การเป็นตัวแทนที่เชื่อมโยงจะเห็นได้อย่างชัดเจนเมื่อจำเป็นต้องแทรกหรือลบองค์ประกอบที่อยู่ตรงกลางของกลุ่มองค์ประกอบอื่น ๆ

การดำเนินงานในกอง

การดำเนินการพื้นฐานที่สามารถดำเนินการบนสแต็กมีดังนี้:

1. PUSH: เมื่อมีการเพิ่มองค์ประกอบใหม่ไปที่ด้านบนสุดของสแต็กจะเรียกว่าการดำเนินการ PUSH การผลักองค์ประกอบในสแต็กจะเรียกการเพิ่มองค์ประกอบเนื่องจากองค์ประกอบใหม่จะถูกแทรกที่ด้านบน หลังจากการกดแต่ละครั้งด้านบนจะเพิ่มขึ้นหนึ่งครั้ง ถ้าอาร์เรย์เต็มและไม่สามารถเพิ่มองค์ประกอบใหม่ได้มันจะเรียกว่าเงื่อนไข STACK-FULL หรือ STACK OVERFLOW PUSH OPERATION - ฟังก์ชันใน C:
   การพิจารณาสแต็กถูกประกาศเป็น
   int stack ด้านบน = -1;
โมฆะดัน ()
{
รายการ int;
ถ้า (top <4)
{
f ("ป้อนหมายเลข");
สแกน ("% d", & รายการ);
top = top + 1;
stack = item;
}
อื่น
{
f ("สแต็คเต็ม");
}
}
2. POP: เมื่อองค์ประกอบถูกลบออกจากด้านบนของสแต็กจะเรียกว่าการดำเนินการ POP สแต็กจะลดลงหนึ่งหลังจากทุกการดำเนินการป๊อป หากไม่มีองค์ประกอบที่เหลืออยู่ในสแต็กและป๊อปถูกดำเนินการสิ่งนี้จะส่งผลให้เกิดเงื่อนไขการสแต็คซึ่งหมายความว่าสแต็กของคุณว่างเปล่า การใช้งานแบบ POP - ฟังก์ชั่นใน C:
   การพิจารณาสแต็กถูกประกาศเป็น
   int stack ด้านบน = -1;
โมฆะป๊อป ()
{
รายการ int;
if (top> = 4)
{
ไอเท็ม = stack;
top = top - 1;
f ("หมายเลขถูกลบคือ =% d", รายการ);
}
อื่น
{
f ("สแต็กว่างเปล่า");
}
}

การดำเนินงานในคิว

การดำเนินการพื้นฐานที่สามารถดำเนินการกับคิวคือ:

1. Enqueue: ในการแทรกองค์ประกอบในคิวฟังก์ชั่นการดำเนินการดึงข้อมูลใน C:
   คิวถูกประกาศเป็น
   int queue, Front = -1 และ rear = -1;
เป็นโมฆะเพิ่ม ()
{
รายการ int;
ถ้า (หลัง <4)
{
f ("ป้อนหมายเลข");
สแกน ("% d", & รายการ);
ถ้า (front == -1)
{
front = 0;
ด้านหลัง = 0;
}
อื่น
{
ด้านหลัง = หลัง + 1;
}
คิว = รายการ;
}
อื่น
{
f ("คิวเต็ม");
}
}

2. dequeue: ในการลบองค์ประกอบออกจากคิวฟังก์ชั่นการดำเนินการตามขั้นตอนใน C:
   คิวถูกประกาศเป็น
   int queue, Front = -1 และ rear = -1;
เป็นโมฆะลบ ()
{
รายการ int;
if (front! = -1)
{
รายการ = คิว
if (front == rear)
{
ด้านหน้า = -1;
ด้านหลัง = -1;
}
อื่น
{
front = front + 1;
f ("หมายเลขถูกลบคือ =% d", รายการ);
}
}
อื่น
{
f ("คิวว่างเปล่า");
}
}

แอพพลิเคชั่นของ Stack

• แยกวิเคราะห์ในคอมไพเลอร์
• เครื่องเสมือน Java
• เลิกทำในโปรแกรมประมวลผลคำ
• ปุ่มย้อนกลับในเว็บเบราว์เซอร์
• ภาษา PostScript สำหรับ ers
• การใช้ฟังก์ชั่นการโทรในคอมไพเลอร์

การใช้งานของคิว

• บัฟเฟอร์ข้อมูล
• การถ่ายโอนข้อมูลแบบอะซิงโครนัส (ไฟล์ IO, ไพพ์, ซ็อกเก็ต)
• จัดสรรการร้องขอในทรัพยากรที่ใช้ร่วมกัน (เอ้อ, โปรเซสเซอร์)
• การวิเคราะห์การจราจร
• กำหนดจำนวนของพนักงานเก็บเงินที่จะมีที่ซูเปอร์มาร์เก็ต

ข้อสรุป

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