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

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

Стек - это линейная структура данных, в которой элементы данных хранятся непрерывно. Он следует за порядком 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 of stack1: 
50
40
Elements of stack2: 
30
20
10

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

Конец

И вот мы подошли к концу: мы познакомились с основами стека, его встроенными методами и реализацией на C ++.

Надеюсь, вы поняли, о чем шла речь. Если вам понравилась эта статья, пожалуйста, оставьте аплодисменты.
Продолжайте кодировать и удачного программирования: -)