Стек на C++

Добро пожаловать, читатели, в этом блоге мы собираемся изучить основы стека и их реализацию кодирования. Встроенные функции и методы также будут кратко описаны. Итак, давайте погрузимся и начнем наше обучение стекам.

Что такое стек?

Стек - это линейная структура данных, имеющая элементы данных, хранящиеся непрерывным образом. Это следует за порядком LIFO, то есть последним в порядке поступления, когда элемент, который вставляется в конец, извлекается первым. Можно только нажать или вытолкнуть элемент сверху. Вы можете лучше понять стек, если сравнить его со стопкой книг.

Посмотрите на изображение выше, книга, помещенная последней в стопку, находится сверху стопки и может быть легко извлечена (удалена) из стопки. С другой стороны, книга, которая помещается первой в стопку, находится внизу и будет последней, которая будет выдвинута.
Это довольно простая структура данных, но с хорошими приложениями, и есть вещи, которые лучше всего сделать с помощью стека.

Приложения стека

Балансировка символов.
Преобразование инфикса в постфикс / префикс.
Повторить-отменить функции во многих местах.
Вперед и назад функция в веб-браузерах.
Используется в таких алгоритмах, как Ханойская башня, обход деревьев, проблема с запасами, проблема с гистограммой.
В графе алгоритмы, такие как топологическая сортировка и сильно связанные компоненты.

FLOW

Прежде чем перейти к реализации стека, мы сначала обсудим два наиболее встречающихся слова при выполнении операций со стеком:

Underflow

В состоянии недостаточного заполнения все элементы стека удаляются, т.е. в стеке нет элемента, а стек пуст. Если кто-то пытается удалить еще один элемент из этого пустого стека, возникшее условие называется недостаточным.
 

Overflow

В этом состоянии возникает состояние переполнения в стеке фиксированного размера, стек заполняется, т. Е. Все пространство занято, и если в стек вставляется еще один элемент, это невозможно, и стек переполняется из-за большего количества данных, чем может вместить.

Создание стека

Теперь посмотрим, как сделан стек. Я буду использовать класс вместо структуры, и я буду использовать вектор для реализации стека, поскольку это значительно упрощает нашу работу, и вы сами это увидите, если когда-нибудь пробовали реализовать стек с использованием простого массива. Если нет, просто посмотрите код, который вы поймете сами.

Мы использовали вектор v и объявили его закрытым, чтобы никто не мог получить к нему прямой доступ. мы создали методы, с помощью которых мы можем использовать стек доступа. Существует четыре основных стековых операции.

Push()

Push-операция предназначена для вставки в верхнюю часть стопки. Мы использовали метод push_back для вектора, чтобы добавить новый элемент в конец вектора стека, по-видимому, который является вершиной нашего стека. Теперь вы можете видеть, насколько проще стала наша работа с использованием вектора.

Pop()

Операция pop используется для выталкивания самого верхнего элемента стека. Для этого мы использовали метод pop_back вектора. Чтобы выскочить, мы сначала проверяем, является ли стек пустым или нет, если он не пустой, тогда элемент может быть извлечен, в противном случае выполняется условие недостаточного заполнения.

Top()

Top относится к верхнему элементу стека. Этот метод используется для получения элемента в верхней части стека. В реализации массива мы должны обновить значение top, и элемент в вершине индекса возвращается при вызове этого метода, но в нашем случае возврат последнего элемента вектора сделает нашу работу, и нам не нужно сохранять верхняя переменная или обновить ее. Опять же, использование вектора имеет явное преимущество.

isEmpty()

В этом методе мы проверяем, является ли стек пустым или нет, и он используется во всплывающей операции, чтобы избежать условия «недостаточного заполнения». Он возвращает результат bool для того, равен ли размер вектора нулю или нет.
Есть еще один метод, IsFull (). Он используется с массивом для проверки, заполнен ли стек или нет, но в случае вектора мы не определили какой-либо размер и, следовательно, не существует верхнего предела размера, например 10 или 10000. Вот почему мы не использовали его в нашей реализации.

Еще одна реализация

Есть другая реализация, использующая связанный список. Вершина стека представлена ​​заголовком, все вставки будут inserttion_at_head, и удаление также будет происходить из заголовка, условие недостаточного заполнения будет выполнено, если следующий узел указывает на NULL и не будет условия isFull.
Я бы посоветовал вам попробовать реализовать стек со связанным списком самостоятельно. Это очень помогло бы вам понять концепции, и это довольно просто, и я уже дал вам несколько советов, которых более чем достаточно.

Стек STL

Эти библиотеки имеют очень эффективно написанный код с лучшей сложностью пространства и времени. Чтобы использовать стек STL, вам нужно включить заголовок стека, после чего вы можете объявить стек любого типа данных, который вам нужен.

Теперь вы можете использовать все методы стека напрямую, без предварительного кодирования. Основные методы:
push → Вставляет элемент в верхнюю часть стека.
pop → Удаляет элемент в верхней части стека.
top → Top используется для доступа к верхнему элементу стека.
empty → проверяет, пуст ли нижележащий контейнер

#include <iostream>       
#include <stack>          
using namespace std;
int main (){
  stack<int> m;  for (int i=0; i<5; ++i) 
       m.push(i);           
  while (!m.empty()){       
     m.pop();              
  }  return 0;
}

Output:Element at top is 15
Popping out elements... 4 3 2 1 0

size → Возвращает количество элементов в стеке.

#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 of stack1: 
50
40
Elements of stack2: 
30
20
10

Вы сами можете понять, насколько проще STL делает нашу работу, и, как я уже говорил, это очень эффективно.

Конец

И вот, наконец, мы увидели основы стека, его встроенных методов и реализацию в C ++. Запишись на наши курсы по C++ и научись еще большему!)