С возвращением, читатели, в этом блоге мы познакомимся с основами стека и их реализацией кодирования. Также будут кратко описаны встроенные функции и методы. Итак, давайте углубимся и начнем наше путешествие по изучению стеков.
Что такое стек?
Стек - это линейная структура данных, в которой элементы данных хранятся непрерывно. Он следует за порядком LIFO, т. Е. Последним вошел - первым ушел, при котором элемент, вставленный в конце, выскакивает первым. Можно только толкать или выталкивать элемент сверху. Вы можете лучше понять стек, если сравните его со стопкой книг.
Взгляните на изображение выше, книга, помещенная последней в стопке, находится наверху стопки, и ее можно легко вынуть (удалить) из стопки. С другой стороны, книга, которая кладется первой в стопку, находится внизу и выскакивает из нее последней.
Это довольно простая структура данных, но есть хорошие приложения, и есть вещи, которые лучше всего можно сделать только с помощью стека.
Приложения стека
- Балансировка символов.
- Преобразование инфиксов в постфикс / префикс.
- Повторить-отменить функции во многих местах.
- Функция прямого и обратного просмотра в веб-браузерах.
- Используется в таких алгоритмах, как Ханойская башня, обход дерева, проблема диапазона запасов, проблема гистограммы.
- В алгоритмах графов, таких как топологическая сортировка и сильно связанные компоненты.
ПОТОК
Прежде чем перейти к реализации стека, мы сначала обсудим два наиболее часто встречающихся слова при выполнении операций над стеком:
Недополнение
В состоянии недостаточного заполнения все элементы стека удаляются, т.е. в стеке нет элемента и стек пуст. Если кто-то пытается удалить еще один элемент из этого пустого стека, возникшее состояние называется потерей значимости.
Переполнение
Условие переполнения возникает в стеке фиксированного размера в этом состоянии, стек заполняется, т.е. все пространство занято, и если еще один элемент вставляется в стек, это не может быть выполнено, и стек будет переполнен из-за большего количества данных чем он может удержать.
Строительный стек
Теперь посмотрим, как складывается стек. Я буду использовать класс вместо структуры, и я буду использовать вектор для реализации стека, поскольку это значительно упрощает нашу работу, и вы сами в этом убедитесь, если когда-либо пробовали реализовать стек с использованием простого массива. Если не просто увидеть код для этого, вы поймете сами.
class stack{ private: vector<int> v; public: void push(int data){ v.push_back(data); } bool isEmpty(){ return v.size() == 0; } int top(){ return v[v.size()-1]; } void pop(){ if(!isEmpty()){ v.pop_back(); } } };
Мы использовали вектор v и объявили его частным, чтобы никто не мог получить к нему прямой доступ. мы создали методы, с помощью которых мы можем использовать стек доступа. Есть четыре основных стековых операции.
толкать()
Операция выталкивания предназначена для вставки в верхнюю часть стека. Мы использовали метод push_back вектора, чтобы добавить новый элемент в конец вектора стека, который, по-видимому, является вершиной нашего стека. Теперь вы можете увидеть, насколько проще стала наша работа с вектором.
поп ()
Операция Pop используется для извлечения самого верхнего элемента стека. Для этого мы использовали метод вектора pop_back. Чтобы выскочить, мы сначала проверяем, пуст ли стек или нет, если он не пуст, то элемент может быть вытянут, в противном случае выполняется условие недостаточного заполнения.
Топ()
Верх относится к самому верхнему элементу стека. Этот метод используется для того, чтобы элемент находился наверху стека. В реализации массива мы должны обновить значение вершины, и при вызове этого метода возвращается элемент в вершине индекса, но в нашем случае возврат последнего элемента вектора выполнит нашу работу, и нам не нужно сохранять верхнюю переменную или обновить ее. Опять же, использование вектора имеет здесь явное преимущество.
пустой()
В этом методе мы проверяем, пуст ли стек или нет, и он используется в операции pop, чтобы избежать состояния «недостаточного заполнения». Он возвращает логический результат, определяющий, равен ли размер вектора нулю.
Есть еще один метод - IsFull (). Он используется с массивом, чтобы проверить, заполнен ли стек или нет, но в случае вектора мы не предопределили какой-либо размер и, следовательно, нет верхнего предела размера, такого как 10 или 10000. Вот почему мы не указали не использовал его в нашей реализации.
Другая реализация
Есть еще одна реализация, использующая связанный список. Вершина стека представлена заголовком, все вставки будут иметь тип insert_at_head, и удаление также будет происходить из заголовка, условие потери значимости будет выполнено, если следующий узел указывает на NULL и не будет условия isFull.
Я предлагаю вам попробовать реализовать стек со связным списком самостоятельно. Это очень поможет вам понять концепции, и это довольно просто, и я уже дал вам несколько советов, которых более чем достаточно.
Стек STL
Эти библиотеки имеют очень эффективно написанный код с лучшей пространственной и временной сложностью. Чтобы использовать STL стека, вам необходимо включить заголовок стека, после чего вы можете объявить стек любого типа данных, который вы хотите.
#include<stack> // To include stack library stack<int> s; // stack of integers.
Теперь вы можете использовать все методы стека напрямую, не кодируя их заранее. Основные методы:
push → Вставляет элемент вверху стопки.
pop → Удаляет элемент наверху стека.
top → Метод Top используется для доступа к верхнему элементу стека.
пусто → проверяет, пуст ли базовый контейнер
#include <iostream> #include <stack>
using namespace std; int main (){ stack<int> m;
for (int i=0; i<5; ++i) m.push(i); //Using Push operation to insert element
cout << "Element at top is " << m.top() << endl;
cout << "Popping out elements..."; while (!m.empty()){ //using empty method
cout <<' '<< mystack.top();//top to see the element at top m.pop(); //Using pop to pop out elements }
return 0; }
Output: Element at top is 15 Popping out elements... 4 3 2 1 0
размер → Возвращает количество элементов в стеке.
#include <iostream> #include <stack> using namespace std; int main (){
stack<int> m; cout << "size: " << m.size() << endl; for (int i=0; i<5; i++) m.push(i); cout << "size: " << m.size() << endl; return 0; }
Output: size: 0 size: 5
emplace → Создает элемент на месте наверху стека.
#include <iostream> #include <stack> #include <string>
using namespace std; int main (){
stack<string> m; m.emplace ("First sentence"); m.emplace ("Second sentence"); cout << "m contains: "<<endl; while (!m.empty()){ cout << m.top() << endl; m.pop(); } return 0; }
Output: mystack contains: Second sentence First sentence
swap → меняет местами содержимое стека.
#include <iostream> #include <stack>
using namespace std; int main (){
stack<int> stack1, stack2; stack1.push(10); stack1.push(20); stack1.push(30); stack2.push(40); stack2.push(50); stack1.swap(stack2); cout << "Elements of stack1: " << endl; while (!stack1.empty()){ cout << stack1.top() << endl; stack1.pop(); }
cout << "Elements of stack2: " << endl; while (!stack2.empty()){ cout << stack2.top() << endl; stack2.pop(); }
return 0; }
Output: Elements ofstack
1: 50 40 Elements ofstack
2: 30 20 10
Вы сами можете понять, насколько STL упрощает нашу работу и, как я уже говорил, они очень эффективны.
Конец
И вот мы подошли к концу: мы познакомились с основами стека, его встроенными методами и реализацией на C ++.
Надеюсь, вы поняли, о чем шла речь. Если вам понравилась эта статья, пожалуйста, оставьте аплодисменты.
Продолжайте кодировать и удачного программирования: -)