ความแตกต่างระหว่าง Stack และ Queue

• 2019

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

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

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

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

พื้นฐานสำหรับการเปรียบเทียบ	กอง	คิว
หลักการทำงาน	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 [5], top = -1;
void push()
{
int item;
if (top < 4)
{
printf ("Enter the number") ;
scan ("%d", & item) ;
top = top + 1;
stack [top] = item;
}
else
{
printf (" Stack is full");
}
}
2. POP : เมื่อองค์ประกอบถูกลบออกจากด้านบนของสแต็กจะเรียกว่าการดำเนินการ POP สแต็กจะลดลงหนึ่งหลังจากทุกการดำเนินการป๊อป หากไม่มีองค์ประกอบที่เหลืออยู่ในสแต็กและป๊อปถูกดำเนินการสิ่งนี้จะส่งผลให้เกิดเงื่อนไขการสแต็กซึ่งหมายความว่าสแต็กของคุณว่างเปล่า POP OPERATION - ฟังก์ชั่นใน C:
   การพิจารณาสแต็กถูกประกาศเป็น
   int stack [5], top = -1;
void pop()
{
int item;
if (top >= 4)
{
item = stack [top];
top = top - 1;
printf ("Number deleted is = %d", item) ;
}
else
{
printf (" Stack is empty");
}
}

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

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

1. การเข้าคิว : เพื่อแทรกองค์ประกอบในคิวฟังก์ชั่นการดำเนินการตามหน้าที่ใน C:
   คิวถูกประกาศเป็น
   int queue [5], Front = -1 and rear = -1;
void add ()
{
int item;
if ( rear < 4)
{
printf ("Enter the number") ;
scan ("%d", & item) ;
if (front == -1)
{
front =0 ;
rear =0 ;
}
else
{
rear = rear + 1;
}
queue [rear] = item ;
}
else
{
printf ("Queue is full") ;
}
}

2. Dequeue : ในการลบองค์ประกอบออกจากคิวฟังก์ชั่นการดำเนินการดึงข้อมูลใน C:
   คิวถูกประกาศเป็น
   int queue [5], Front = -1 and rear = -1;
void delete ()
{
int item;
if ( front ! = -1)
{
item = queue [ front ] ;
if (front == rear)
{
front =-1 ;
rear =-1 ;
}
else
{
front = front + 1;
printf ("Number deleted is = %d", item) ;
}
}
else
{
printf ("Queue is empty") ;
}
}

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

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

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

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

ข้อสรุป

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