Натрупвайте C++ STL с пример

по: Бенджамин Уокър Бенджамин Уокър
Hours Обновено

⚡ Умно обобщение

Натрупвайте C++ STL имплементира LIFO контейнерен адаптер, който добавя и премахва елементи от един край, обвиващping основен контейнер за последователности, като например deque, vector или list, за управление на подредени данни.

  • 🔘 Принципът LIFO: std::stack следва реда „Последен влязъл, първи излязъл“, така че най-скорошно изпратеният елемент винаги е първият премахнат.
  • 📦 Адаптер за контейнер: Стекът обгръща съществуващ контейнер за последователност и по подразбиране се отделя от опашката, когато не е предоставен тип контейнер.
  • ➕ Основни операции: Функциите push, pop и top съответно вмъкват елемент, премахват най-горния елемент и прочитат най-горния елемент.
  • 🔍 Държавни проверки: Функциите empty и size отчитат дали стекът съдържа елементи и колко от тях се съхраняват в момента.
  • 🔁 Допълнителни функции: Функциите emplace и swap изграждат елемент на място и разменят съдържанието на два стека.
  • 🤖 AI помощ: Асистенти за AI кодиране, като GitHub Copilot, генерират stack push, pop и traversal boilerplate от кратък коментар.
Прочетете повече

Натрупвайте C++ STL

Какво е std::stack?

Стекът е структура от данни, която работи въз основа на техниката LIFO (последен влязъл, първи излязъл). std::stack позволява добавяне и премахване на елементи само от единия край.

Класът std::stack е адаптер за контейнери. Обектите тип „контейнер“ съдържат данни от подобен тип. Можете да създадете стек от различни контейнери за последователности. Ако не е предоставен контейнер, по подразбиране ще се използва контейнерът deque. Адаптерите за контейнери не поддържат итератори, така че не могат да се използват за манипулиране на данни.

Синтаксис на стека

За да създадем стек, трябва да включим заглавен файл в нашия код. След това използваме този синтаксис, за да дефинираме std::stack:

template <class Type, class Container = deque<Type> > class stack;
  • Тип – е типът на елемента, съдържащ се в std::stack. Тя може да бъде всяка валидна C++ тип или дори дефиниран от потребителя тип.
  • Контейнер – е типът на основния контейнерен обект.

Видове членове

Ето типовете членове на стека:

  • тип_стойност– Първият параметър на шаблона, T. Той обозначава типовете елементи.
  • тип_контейнер– Вторият параметър на шаблона, Контейнер. Той обозначава типа на основния контейнер.
  • тип_размер– Тип беззнаково интегрално число.

Operaции в Stack

A C++ стекът поддържа следните основни операции:

  • тласък – Добавя/избутва елемент в стека.
  • поп – Премахва/изважда елемент от стека.
  • поглед – Връща най-горния елемент от стека, без да го премахва.
  • еПълно – Проверява дали стекът е пълен.
  • празно е – Проверява дали стекът е празен.

Реализация на стека

Следните стъпки показват как горната част на стека се измества, когато елементите се избутват и след това се изваждат:

Стъпка 1) Първоначално имаме празен стек. Върхът на празния стек е зададен на -1.

Стъпка 2) След това сме добавили елемент 5 в стека. Върхът на стека ще сочи към елемент 5.

Стъпка 3) След това сме добавили елемент 50 в стека. Върхът на стека се измества и сочи към елемент 50.

Стъпка 4) След това извършихме операция „изваждане“, премахвайки най-горния елемент от стека. Елемент 50 е изваден от стека. Върхът на стека вече сочи към елемент 5.

Реализация на стека

push() и pop()

Функцията 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();
	}
}

Изход:

push() и pop()

Ето екранна снимка на кода:

push() и pop()

Code Обяснение:

  1. Включете заглавния файл на iostream в нашия код, за да използвате неговите функции.
  2. Включете заглавния файл на стека в нашия код, за да използвате неговите функции.
  3. Включете пространството от имена std в нашия код, за да използвате неговите класове, без да го извиквате.
  4. Извикайте функцията main(). Логиката на програмата трябва да се добави в тази функция.
  5. Създайте стек st за съхраняване на цели числа.
  6. Използвайте функцията push(), за да вмъкнете стойността 10 в стека.
  7. Използвайте функцията push(), за да вмъкнете стойността 20 в стека.
  8. Използвайте функцията push(), за да вмъкнете стойността 30 в стека.
  9. Използвайте функцията push(), за да вмъкнете стойността 40 в стека.
  10. Използвайте функцията pop(), за да премахнете най-горния елемент от стека, тоест 40. Най-горният елемент сега става 30.
  11. Използвайте функцията pop(), за да премахнете най-горния елемент от стека, тоест 30. Най-горният елемент сега става 20.
  12. Използвайте цикъл while и функция empty(), за да проверите дали стекът НЕ е празен. The ! е операторът NOT.
  13. Отпечатване на текущото съдържание на стека на конзолата.
  14. Извикайте функцията pop() в стека.
  15. Край на тялото на цикъла while.
  16. Край на тялото на функцията main().
Не пропускайте:

празен(), размер(), топ()

Стековете имат вградени функции, които можете да използвате, за да си поиграете със стека и неговите стойности. Те включват:

  • празно()– проверява дали стекът е празен или не.
  • размер ()– връща размера на стека, т.е. броя на елементите в него.
  • отгоре()– осъществява достъп до елемента на стека в горната част.

Пример 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;
}

Изход:

празен(), размер(), топ()

Ето екранна снимка на кода:

празен(), размер(), топ()

Code Обяснение:

  1. Включете заглавния файл на iostream в нашия код, за да използвате неговите функции.
  2. Включете заглавния файл на стека в нашия код, за да използвате неговите функции.
  3. Включете пространството от имена std в нашата програма, за да използвате неговите класове, без да го извиквате.
  4. Създайте функцията createStack, която можем да използваме за създаване на стека mystack. Стекът ще съдържа набор от цели числа.
  5. Началото на тялото на функцията createStack.
  6. Създайте екземпляр на типа данни mystack и му дайте името ms.
  7. Използвайте цикъла while и функцията empty(), за да проверите дали стекът е празен.
  8. Началото на тялото на цикъла while.
  9. Използвайте функцията top(), съхранена в горната част на стека. Символът \t ще създаде нов раздел.
  10. Използвайте функцията pop(), за да изтриете елемента в горната част на стека.
  11. Край на тялото на цикъла while.
  12. Отпечатайте празен ред на конзолата.
  13. Край на тялото на функцията createStack.
  14. Извикайте функцията main(). Логиката на програмата трябва да се добави в тялото на функцията main().
  15. Началото на тялото на функцията main().
  16. Създайте стеков обект st.
  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() и 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();
	}
}

Изход:

emplace() и swap()

Ето екранна снимка на кода:

emplace() и swap()

Code Обяснение:

  1. Включете заглавния файл на iostream в нашия код, за да използвате неговите функции.
  2. Включете заглавния файл на стека в нашия код, за да използвате неговите функции.
  3. Включете заглавния файл cstdlib в нашия код, за да използвате неговите функции.
  4. Включете пространството от имена std в нашия код, за да използвате неговите класове, без да го извиквате.
  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;

Горният синтаксис декларира стек към елементи от тип данни 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();  
}

Изход:

Стек в STL

Ето екранна снимка на кода:

Стек в STL

Code Обяснение:

  1. Включете заглавния файл на iostream в нашия код, за да използвате неговите функции.
  2. Включете заглавния файл на стека в нашия код, за да използвате неговите функции.
  3. Включете заглавния файл cstdlib в нашия код, за да използвате неговите функции.
  4. Включете пространството от имена std в нашия код, за да използвате неговите класове, без да го извиквате.
  5. Извикайте функцията main(). Логиката на програмата трябва да се добави в тялото на тази функция.
  6. Декларирайте стек st за съхраняване на целочислени данни.
  7. Добавете елемент 12 към стека.
  8. Добавете елемент 19 към стека.
  9. Добавете елемент 20 към стека.
  10. Отпечатайте елемента в горната част на стека на конзолата.
  11. Отпечатайте размера на стека на конзолата.
  12. Край на тялото на функцията main().

Въпроси и Отговори

Стекът следва реда „Последен влязъл, първи излязъл“, така че първо премахва най-скорошния елемент. Опашката следва реда „Първи влязъл, първи излязъл“, като първо премахва най-стария елемент. Всеки от тях е подходящ за различни нужди на обработката.

Да. std::stack приема всеки контейнер за последователности като втори аргумент на шаблона, например std::stack. >. Стандартният deque е подходящ за повечето случаи, докато vector може да подобри локалността на паметта, когато стекът расте предвидимо.

Както push, така и pop се изпълняват за константно време O(1), защото стекът докосва само най-горния си елемент. Базовият deque добавя елементи, без да измества съществуващите, така че производителността остава предвидима, независимо от размера на стека.

std::stack не предоставя итератори, така че цикъл, базиран на диапазон, няма да се компилира. За да прочетете всяка стойност, копирайте стека и извикайте многократно top() и pop() върху копието или изберете deque, когато е необходимо преминаване през стека.

Функцията pop() връща void по замисъл, разделяйки премахването от достъпа за безопасност при изключения. Четенето и премахването в една стъпка може да доведе до загуба на данни, ако копирането доведе до грешка, така че първо извиквате top(), а след това pop().

Не. std::stack не предлага вградена синхронизация, така че едновременните push и pop извиквания от множество нишки причиняват състезания за данни. Защитете споделения достъп с mutex или друг заключващ механизъм, преди да използвате един стек в различни нишки.

Да. Асистентите за кодиране с изкуствен интелект четат коментар или име на функция и генерират декларации на std::stack, цикли на изтегляне и изтегляне, както и логика за преминаване. RevПрегледът на генерираните гранични проверки, като например тестовете empty() преди pop(), остава важен за безопасните програми.

Да. Копилот на GitHub завършва извикванията на push, pop, top и empty(), докато пишете, и предлага опции за контейнери. Това е 2026 C++ Интелигентността на кода добавя разпознаваемост на символите, така че предложенията за стекове от множество файлове остават последователни.

Обобщете тази публикация с: