กองเข้า C++ STL พร้อมตัวอย่าง

โดย: เบนจามิน วอล์คเกอร์ เบนจามิน วอล์คเกอร์
Hours วันที่อัพเดท

std::stack คืออะไร?

สแต็กคือโครงสร้างข้อมูลที่ทำงานบนเทคนิค LIFO (Last In First Out) std::stack อนุญาตให้เพิ่มและลบองค์ประกอบได้จากด้านใดด้านหนึ่งเท่านั้น

ชั้น std::stack เป็นอะแดปเตอร์คอนเทนเนอร์ ออบเจ็กต์คอนเทนเนอร์เก็บข้อมูลประเภทข้อมูลที่คล้ายกัน คุณสามารถสร้างสแต็กจากคอนเทนเนอร์ลำดับต่างๆ ได้ หากไม่มีการระบุคอนเทนเนอร์ คอนเทนเนอร์ deque จะถูกใช้เป็นค่าเริ่มต้น อะแดปเตอร์คอนเทนเนอร์ไม่รองรับตัววนซ้ำ ดังนั้นจึงใช้จัดการข้อมูลไม่ได้

สแต็กไวยากรณ์

ในการสร้าง stack เราต้องรวม ไฟล์ส่วนหัวในโค้ดของเรา จากนั้นเราใช้ไวยากรณ์นี้เพื่อกำหนด std::stack:

template <class Type, class Container = deque<Type> > class stack;
  • ประเภท – เป็นประเภทขององค์ประกอบที่มีอยู่ใน std::stack มันอาจจะถูกต้องก็ได้ C++ หรือแม้กระทั่งประเภทที่ผู้ใช้กำหนด
  • ภาชนะ – เป็นประเภทของวัตถุคอนเทนเนอร์ต้นแบบ

ประเภทสมาชิก

ต่อไปนี้เป็นประเภทสมาชิกสแต็ก:

  • value_type- พารามิเตอร์เทมเพลตแรก T ซึ่งแสดงถึงประเภทองค์ประกอบ
  • container_type- พารามิเตอร์เทมเพลตที่สอง คอนเทนเนอร์ มันหมายถึงประเภทคอนเทนเนอร์พื้นฐาน
  • size_type- ประเภทอินทิกรัลที่ไม่ได้ลงนาม

Operaต่างๆ ใน ​​Stack

A C++ สแต็กรองรับการดำเนินการพื้นฐานต่อไปนี้:

  • ดัน - เพิ่ม/ดันรายการลงในสแต็ก
  • ป๊อป - ลบ / ป๊อปรายการออกจากสแต็ก
  • peek – ส่งคืนไอเท็มบนสุดของสแต็กโดยไม่ต้องลบออก
  • isFull – ตรวจสอบว่าสแต็กเต็มหรือไม่
  • isEmpty – ตรวจสอบว่าสแต็กว่างเปล่าหรือไม่

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

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

ขั้นตอน 1) ในตอนแรกเรามีสแต็คว่าง ด้านบนของสแต็กว่างถูกตั้งค่าเป็น -1

ขั้นตอน 2) ต่อไป เราได้ผลักองค์ประกอบ 5 เข้าไปในสแต็ก ด้านบนของสแต็กจะชี้ไปที่องค์ประกอบ 5

ขั้นตอน 3) ขั้นต่อไป เราได้ผลักองค์ประกอบ 50 เข้าไปในสแต็ก ส่วนบนของสแต็กจะเลื่อนและชี้ไปที่องค์ประกอบ 50

ขั้นตอน 4) จากนั้นเราได้ดำเนินการป๊อปเอาองค์ประกอบบนสุดออกจากสแต็ก องค์ประกอบ 50 จะถูกป๊อปออกจากสแต็ก ส่วนบนสุดของสแต็กจะชี้ไปที่องค์ประกอบ 5

กด() และป๊อป()

ฟังก์ชัน stack::push() จะเพิ่มรายการใหม่ที่ด้านบนของสแต็ก ขนาดสแต็กจะเพิ่มขึ้น 1 หลังจากการแทรก ฟังก์ชันใช้ไวยากรณ์นี้:

stack.push(value)

ค่าคือรายการที่จะแทรกลงในสแต็ก

ฟังก์ชัน stack:: pop() จะลบองค์ประกอบด้านบนของสแต็ก นี่คือรายการใหม่ล่าสุดของสแต็ก ขนาดปึกจะลดลง 1 หลังจากการถอดออก นี่คือไวยากรณ์ของฟังก์ชัน:

stack.pop()

ฟังก์ชันไม่รับพารามิเตอร์

1 ตัวอย่าง:

#include <iostream> 
#include <stack> 
using namespace std;
int main() {
	stack<int> st;
	st.push(10);
	st.push(20);
	st.push(30);
	st.push(40);
	
         st.pop();
	st.pop();

	while (!st.empty()) {
		cout << ' ' << st.top();
		st.pop();
	}
}

Output:

กด() และป๊อป()

นี่คือภาพหน้าจอของรหัส:

กด() และป๊อป()

คำอธิบายรหัส:

  1. รวมไฟล์ส่วนหัว iostream ไว้ในโค้ดของเราเพื่อใช้ฟังก์ชันต่างๆ
  2. รวมไฟล์ส่วนหัวของสแต็กในโค้ดของเราเพื่อใช้ฟังก์ชันต่างๆ
  3. รวมเนมสเปซมาตรฐานไว้ในโค้ดของเราเพื่อใช้คลาสโดยไม่ต้องเรียกมัน
  4. เรียกใช้ฟังก์ชัน main() ควรเพิ่มตรรกะของโปรแกรมภายในฟังก์ชันนี้
  5. สร้าง stack st เพื่อเก็บค่าจำนวนเต็ม
  6. ใช้ฟังก์ชัน push() เพื่อแทรกค่า 10 ลงในสแต็ก
  7. ใช้ฟังก์ชัน push() เพื่อแทรกค่า 20 ลงในสแต็ก
  8. ใช้ฟังก์ชัน push() เพื่อแทรกค่า 30 ลงในสแต็ก
  9. ใช้ฟังก์ชัน push() เพื่อแทรกค่า 40 ลงในสแต็ก
  10. ใช้ฟังก์ชัน pop() เพื่อลบองค์ประกอบด้านบนออกจากสแต็ก ซึ่งก็คือ 40 องค์ประกอบด้านบนตอนนี้กลายเป็น 30
  11. ใช้ฟังก์ชัน pop() เพื่อลบองค์ประกอบด้านบนออกจากสแต็ก ซึ่งก็คือ 30 องค์ประกอบด้านบนตอนนี้กลายเป็น 20
  12. ใช้ลูป while และฟังก์ชัน empty() เพื่อตรวจสอบว่าสแต็กไม่ว่างหรือไม่ ! คือตัวดำเนินการ NOT
  13. การพิมพ์เนื้อหาปัจจุบันของสแต็กบนคอนโซล
  14. เรียกใช้ฟังก์ชัน pop() บนสแต็ก
  15. ส่วนท้ายของส่วน while ของ loop
  16. จุดสิ้นสุดของเนื้อหาฟังก์ชัน main()

ว่างเปล่า() ขนาด() ด้านบน()

สแต็คมีฟังก์ชันในตัวที่คุณสามารถใช้เพื่อเล่นกับสแต็กและค่าต่างๆ ของมัน ซึ่งรวมถึง:

  • Empty()- เช็คว่า Stack ว่างหรือไม่
  • size()- ส่งกลับขนาดของสแต็ก ซึ่งก็คือจำนวนองค์ประกอบในสแต็ก
  • top()- เข้าถึงองค์ประกอบสแต็กที่ด้านบน

บทความที่เกี่ยวข้อง

2 ตัวอย่าง:

#include <iostream> 
#include <stack>  
using namespace std;
void createStack(stack <int> mystack)
{
	stack <int> ms = mystack;
	while (!ms.empty())
	{
		cout << '\t' << ms.top();
		ms.pop();
	}
	cout << '\n';
}
int main()
{
	stack <int> st;
	st.push(32);
	st.push(21);
	st.push(39);
	st.push(89);
	st.push(25);

	cout << "The stack st is: ";
	createStack(st);
	cout << "\n st.size() : " << st.size();
	cout << "\n st.top() : " << st.top();
	cout << "\n st.pop() : ";
	st.pop();
	createStack(st);
	return 0;
}

Output:

ว่างเปล่า(),ขนาด(),ด้านบน()

นี่คือภาพหน้าจอของรหัส:

ว่างเปล่า(),ขนาด(),ด้านบน()

คำอธิบายรหัส:

  1. รวมไฟล์ส่วนหัว iostream ไว้ในโค้ดของเราเพื่อใช้ฟังก์ชันต่างๆ
  2. รวมไฟล์ส่วนหัวของสแต็กในโค้ดของเราเพื่อใช้ฟังก์ชันต่างๆ
  3. รวมเนมสเปซมาตรฐานไว้ในโปรแกรมของเราเพื่อใช้คลาสโดยไม่ต้องเรียกมัน
  4. สร้างฟังก์ชัน createStack ที่เราสามารถใช้สร้าง stack mystack ได้ สแต็กจะเก็บชุดของจำนวนเต็ม
  5. จุดเริ่มต้นของเนื้อความของฟังก์ชัน createStack
  6. สร้างอินสแตนซ์ของประเภทข้อมูล mystack และตั้งชื่อให้ว่า ms
  7. ใช้ฟังก์ชัน while loop และฟังก์ชัน Empty() เพื่อตรวจสอบว่าสแต็กว่างเปล่าหรือไม่
  8. จุดเริ่มต้นของส่วนเนื้อหาของ while loop
  9. ใช้ฟังก์ชัน top() เก็บไว้ที่ด้านบนของสแต็ก อักขระ \t จะสร้างแท็บใหม่
  10. ใช้ฟังก์ชัน pop() เพื่อลบองค์ประกอบที่ด้านบนของสแต็ก
  11. ส่วนท้ายของส่วน while ของ loop
  12. พิมพ์บรรทัดว่างบนคอนโซล
  13. ส่วนท้ายของฟังก์ชัน createStack
  14. เรียกใช้ฟังก์ชัน main() ควรเพิ่มตรรกะของโปรแกรมภายในเนื้อหาของฟังก์ชัน main()
  15. จุดเริ่มต้นของฟังก์ชัน main()
  16. สร้างวัตถุสแต็กเซนต์
  17. ใช้ฟังก์ชัน push() เพื่อแทรกองค์ประกอบ 32 ลงในสแต็ก
  18. ใช้ฟังก์ชัน push() เพื่อแทรกองค์ประกอบ 21 ลงในสแต็ก
  19. ใช้ฟังก์ชัน push() เพื่อแทรกองค์ประกอบ 39 ลงในสแต็ก
  20. ใช้ฟังก์ชัน push() เพื่อแทรกองค์ประกอบ 89 ลงในสแต็ก
  21. ใช้ฟังก์ชัน push() เพื่อแทรกองค์ประกอบ 25 ลงในสแต็ก
  22. พิมพ์ข้อความบนคอนโซล
  23. เรียกใช้ฟังก์ชัน createStack เพื่อดำเนินการแทรกลงในสแต็กตามข้างต้น
  24. พิมพ์ขนาดของสแต็กบนคอนโซลควบคู่ไปกับข้อความอื่นๆ
  25. พิมพ์องค์ประกอบที่ด้านบนของสแต็กบนคอนโซล
  26. พิมพ์ข้อความบนคอนโซล
  27. ลบองค์ประกอบที่ด้านบนของสแต็ก จากนั้นจะส่งคืนองค์ประกอบที่เหลืออยู่ในสแต็ก
  28. เรียกใช้ฟังก์ชัน createStack เพื่อดำเนินการข้างต้น
  29. โปรแกรมจะต้องคืนค่าเมื่อเสร็จสิ้นสำเร็จ
  30. ส่วนท้ายของฟังก์ชัน main()

emplace() และ สลับ()

นี่คือฟังก์ชันสแต็กแบบ inbuilt อื่นๆ:

  • emplace()- สร้าง จากนั้นแทรกองค์ประกอบใหม่ที่ด้านบนของสแต็ก
  • swap()- แลกเปลี่ยนเนื้อหาสแต็กกับเนื้อหาของสแต็กอื่น

3 ตัวอย่าง:

#include <iostream>    
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st1;
	stack<int> st2;

	st1.emplace(12);
	st1.emplace(19);

	st2.emplace(20);
	st2.emplace(23);

	st1.swap(st2);

	cout << "st1 = ";
	while (!st1.empty()) {
		cout << st1.top() << " ";
		st1.pop();
	}

	cout << endl << "st2 = ";
	while (!st2.empty()) {
		cout << st2.top() << " ";
		st2.pop();
	}
}

Output:

emplace()& สลับ()

นี่คือภาพหน้าจอของรหัส:

emplace()& สลับ()

คำอธิบายรหัส:

  1. รวมไฟล์ส่วนหัว iostream ไว้ในโค้ดของเราเพื่อใช้ฟังก์ชันต่างๆ
  2. รวมไฟล์ส่วนหัวของสแต็กในโค้ดของเราเพื่อใช้ฟังก์ชันต่างๆ
  3. รวมไฟล์ส่วนหัว cstdlib ไว้ในโค้ดของเราเพื่อใช้ฟังก์ชันต่างๆ
  4. รวมเนมสเปซมาตรฐานไว้ในโค้ดของเราเพื่อใช้คลาสโดยไม่ต้องเรียกมัน
  5. เรียกใช้ฟังก์ชัน main() ตรรกะของโปรแกรมจะถูกเพิ่มภายในเนื้อหาของฟังก์ชันนี้
  6. ประกาศสแต็กชื่อ st1 เพื่อเก็บค่าจำนวนเต็ม
  7. ประกาศสแต็กชื่อ st2 เพื่อเก็บค่าจำนวนเต็ม
  8. ใช้ฟังก์ชัน emplace() เพื่อแทรกจำนวนเต็ม 12 ลงในสแต็กชื่อ st1
  9. ใช้ฟังก์ชัน emplace() เพื่อแทรกจำนวนเต็ม 19 ลงในสแต็กชื่อ st1
  10. ใช้ฟังก์ชัน emplace() เพื่อแทรกจำนวนเต็ม 20 ลงในสแต็กชื่อ st2
  11. ใช้ฟังก์ชัน emplace() เพื่อแทรกจำนวนเต็ม 23 ลงในสแต็กชื่อ st2
  12. ใช้ฟังก์ชัน swap() เพื่อสลับเนื้อหาของสแต็กทั้งสอง st1 และ st2 เนื้อหาของสแต็ก st1 ควรถูกย้ายไปยังสแต็ก st2 เนื้อหาของสแต็ก st2 ควรถูกย้ายไปยังสแต็ก st1
  13. พิมพ์ข้อความบนคอนโซล
  14. ใช้คำสั่ง while และฟังก์ชัน Empty() เพื่อตรวจสอบว่าสแต็ก st1 ไม่ว่างเปล่าหรือไม่
  15. พิมพ์เนื้อหาของสแต็ก st1 บนคอนโซล ” ” จะเพิ่มช่องว่างระหว่างองค์ประกอบสแต็กเมื่อพิมพ์บนคอนโซล
  16. ดำเนินการฟังก์ชัน pop() บนสแต็ก st1 เพื่อลบองค์ประกอบด้านบน
  17. ส่วนท้ายของคำสั่ง while
  18. พิมพ์ข้อความบนคอนโซล จุดสิ้นสุดคือ a C++ คำสำคัญสำหรับบรรทัดสุดท้าย โดยจะเลื่อนเคอร์เซอร์ของเมาส์ไปที่บรรทัดถัดไปเพื่อเริ่มพิมพ์จากตรงนั้น
  19. ใช้คำสั่ง while และฟังก์ชัน Empty() เพื่อตรวจสอบว่าสแต็ก st2 ไม่ว่างเปล่าหรือไม่
  20. พิมพ์เนื้อหาของสแต็ก st2 บนคอนโซล ” ” จะเพิ่มช่องว่างระหว่างองค์ประกอบสแต็กเมื่อพิมพ์บนคอนโซล
  21. ดำเนินการฟังก์ชัน pop() บนสแต็ก st2 เพื่อลบองค์ประกอบด้านบน
  22. ส่วนท้ายของคำสั่ง while
  23. ส่วนท้ายของฟังก์ชัน main()

สแต็กใน STL

STL (Standard Template Library) มาพร้อมกับคลาสเทมเพลตที่มีให้ทั่วไป C++ โครงสร้างข้อมูล ดังนั้นจึงสามารถใช้สแต็กใน STL ได้เช่นกัน เราเพียงแค่รวมไลบรารีนี้ไว้ในโค้ดของเราและใช้เพื่อกำหนดสแต็ก

stack<T> st;

รูปแบบข้างต้นประกาศสแต็ก st ให้กับองค์ประกอบของชนิดข้อมูล T

4 ตัวอย่าง:

#include <iostream>      
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st;
	st.push(12);
	st.push(19);
	st.push(20);
	cout << st.top();   
	cout << st.size();  
}

Output:

สแต็กใน STL

นี่คือภาพหน้าจอของรหัส:

สแต็กใน STL

คำอธิบายรหัส:

  1. รวมไฟล์ส่วนหัว iostream ไว้ในโค้ดของเราเพื่อใช้ฟังก์ชันต่างๆ
  2. รวมไฟล์ส่วนหัวของสแต็กในโค้ดของเราเพื่อใช้ฟังก์ชันต่างๆ
  3. รวมไฟล์ส่วนหัว cstdlib ไว้ในโค้ดของเราเพื่อใช้ฟังก์ชันต่างๆ
  4. รวมเนมสเปซมาตรฐานไว้ในโค้ดของเราเพื่อใช้คลาสโดยไม่ต้องเรียกมัน
  5. เรียกใช้ฟังก์ชัน main() ควรเพิ่มตรรกะของโปรแกรมภายในเนื้อหาของฟังก์ชันนี้
  6. ประกาศ stack st เพื่อเก็บข้อมูลจำนวนเต็ม
  7. เพิ่มองค์ประกอบ 12 ลงในสแต็ก
  8. เพิ่มองค์ประกอบ 19 ลงในสแต็ก
  9. เพิ่มองค์ประกอบ 20 ลงในสแต็ก
  10. พิมพ์องค์ประกอบที่ด้านบนของสแต็กบนคอนโซล
  11. พิมพ์ขนาดของสแต็กบนคอนโซล
  12. ส่วนท้ายของฟังก์ชัน main()

สรุป

  • สแต็กคือโครงสร้างข้อมูลที่ทำงานตามเทคนิค LIFO (Last In first Out)
  • std::stack อนุญาตให้เพิ่มและลบรายการจากปลายด้านหนึ่งเท่านั้น
  • คลาส std::stack เป็นคอนเทนเนอร์อะแดปเตอร์ที่เก็บรายการประเภทข้อมูลที่คล้ายกัน
  • สามารถสร้างสแต็กได้จากคอนเทนเนอร์ลำดับต่างๆ
  • หากคุณไม่ได้ระบุคอนเทนเนอร์ คอนเทนเนอร์ deque จะถูกใช้เป็นค่าเริ่มต้น
  • ฟังก์ชัน push() ใช้สำหรับแทรกรายการลงในสแต็ก
  • ฟังก์ชัน pop() ใช้สำหรับลบรายการด้านบนออกจากขั้นตอน
  • ฟังก์ชัน Empty() ใช้สำหรับตรวจสอบว่าสแต็กว่างเปล่าหรือไม่