Класс стека предоставляет интерфейс для очень специализированного контейнера. Стек - это контейнер LIFO, который имеет минимальное количество функций-членов, которые вы можете использовать для работы с данными, хранящимися в стеке. Есть несколько областей информатики и компьютерного программирования, в которых стеки играют заметную роль. В этой статье мы обсудим, как использовать стеки в программировании на C ++, и продемонстрируем некоторые приложения, в которых используются стеки.
Обзор стека
Стек - это контейнер, в который все данные входят и выходят из верхней части контейнера. Вы можете выполнять три основные операции со стеком: 1) поместить новые данные в стек; 2) вытолкнуть верхний элемент данных из стека; и 3) просмотреть верх стека.
Если вы хотите придумать следствие из реальной жизни, подумайте о подносах в кафетерии. Когда клиент входит в кафетерий и получает поднос, он снимает поднос с вершины стопки. Когда посудомоечная машина чистит лоток и кладет его обратно, он оказывается поверх стопки лотков. Когда вы смотрите на стопку лотков, вы можете полностью увидеть только верхний лоток.
Как я упоминал ранее, стек считается контейнером «последним вошел - первым ушел», потому что последний элемент, помещенный на вершину стека, является первым элементом, выталкиваемым из вершины стека.
Объявление стеков
Заголовочный файл для класса стека:
#include <stack>
Класс stack является классом-шаблоном, поэтому вы должны предоставить тип данных с объявлением, как в этих примерах:
stack<int> numbers; stack<string> people; stack<double> ratios; stack<char> operators;
Вы не можете инициализировать стек с помощью списка инициализаторов, и вы не можете указать начальную емкость в качестве аргумента конструктора, как вы можете с другими контейнерами.
Добавление данных в стек и просмотр вершины стека
Есть только один способ добавить данные в стек - функция push. Функция push берет элемент и сохраняет его наверху стека. Верх стека также является единственным элементом, к которому вы можете получить доступ в стеке. В классе есть функция для проверки вершины стека - функция top.
Вот короткая программа, которая помещает некоторые данные в стек, а затем исследует верхнюю часть стека:
#include <iostream>
#include <stack>
using namespace std;
int main()
{
stack<int> numbers;
numbers.push(2);
numbers.push(4);
numbers.push(8);
cout << "top of stack: " << numbers.top() << endl; // 8
return 0;
}
Результат этой программы:
top of stack: 8
Удаление данных из стека
Данные удаляются из стека функцией pop. Эта функция может удалить только элемент наверху стека. Как я упоминал ранее, никакие другие элементы в стеке недоступны, кроме элемента наверху.
Вот пример извлечения данных из стека с проверкой вершины стека после каждого извлечения:
int main()
{
stack<int> numbers;
numbers.push(2);
numbers.push(4);
numbers.push(8);
cout << "top of stack: " << numbers.top() << endl;
// top of stack: 8
numbers.pop();
cout << "top of stack: " << numbers.top() << endl;
// top of stack: 4
numbers.pop();
cout << "top of stack: " << numbers.top() << endl;
// top of stack: 2
numbers.pop();
cout << "top of stack: " << numbers.top() << endl;
// this line does not execute
return 0;
}
Последний оператор cout не выполняется, потому что я пытался вытолкнуть пустой стек. Вы можете использовать функцию empty, которая позволяет узнать, пуст ли стек или в нем все еще есть данные. Давайте изменим приведенную выше программу, чтобы использовать функцию empty:
int main()
{
stack<int> numbers;
numbers.push(2);
numbers.push(4);
numbers.push(8);
while (!numbers.empty()) {
cout << "top of stack: " << numbers.top() << endl;
numbers.pop();
}
return 0;
}
Еще одна функция, которую вы можете использовать, чтобы определить, когда стек пуст, - это функция size. Эта функция возвращает количество элементов в стеке. Вот как с его помощью не выскакивать пустая стопка:
int main()
{
stack<int> numbers;
numbers.push(2);
numbers.push(4);
numbers.push(8);
while (numbers.size() > 0) {
cout << "top of stack: " << numbers.top() << endl;
numbers.pop();
}
return 0;
}
Некоторые приложения стека
Стеки можно использовать для обслуживания нескольких интересных алгоритмов и приложений. Вот несколько из них.
Преобразование десятичных чисел в двоичные
Первый алгоритм, который я расскажу, - это алгоритм преобразования числа с основанием 10 (десятичного) в число с основанием 2 (двоичное). Вот алгоритм, где n - десятичное число, а B - основание (2):
0. Начать с пустой стопкой.
1. Получите крайнюю правую цифру числа n на n% Б. Поместите результат в стек.
2. Заменить n на n / B.
3. Повторяйте шаги 1 и 2 до n = 0.
4. Извлеките и распечатайте цифры из стека, в результате чего получится двоичное число.
Вот программа, реализующая этот алгоритм:
int main()
{
stack<int> binDigits;
int decNumber;
cout << "Enter a decimal number: ";
cin >> decNumber;
int number = decNumber;
const int BASE = 2;
int digit;
while (decNumber > 0) {
digit = decNumber % BASE;
binDigits.push(digit);
decNumber /= BASE;
}
string binNumber = "";
while (!binDigits.empty()) {
binNumber += to_string(binDigits.top());
binDigits.pop();
}
cout << number << " is " << binNumber
<< " in binary." << endl;
return 0;
}
Вот один из запусков этой программы:
Enter a decimal number: 53 53 is 110101 in binary.
В поисках палиндромов
Слово является палиндромом, если его можно писать одинаково вперед и назад. Слова радар и гоночный автомобиль являются примерами палиндромов. Мы можем использовать стек, чтобы определить, является ли слово палиндромом, помещая каждую букву слова в стек. Затем мы можем сформировать обратное слово, вставив стек в другое слово, пока стек не станет пустым. Если исходное слово и слово, образованное из стопки, равны, то слово является палиндромом.
Вот программа, которая проверяет, является ли слово палиндромом:
int main()
{
stack<char> letters;
string word;
cout << "Enter a word to check: ";
cin >> word;
for (unsigned i = 0; i < word.size(); i++) {
letters.push(word[i]);
}
string revWord = "";
while (!letters.empty()) {
revWord += letters.top();
letters.pop();
}
if (revWord == word) {
cout << word << " is a palindrome." << endl;
}
else {
cout << word << " is not a palindrome." << endl;
}
return 0;
}
Вот несколько запусков программы:
Enter a word to check: radar radar is a palindrome. Enter a word to check: racecar racecar is a palindrome. Enter a word to check: railcar railcar is not a palindrome.
Арифметические операторы, которые мы привыкли писать, записываются в инфиксном формате, например: (9.0 / 5.0) * 100 + 32.0. Однако мы должны использовать круглые скобки, чтобы указать правильный порядок операций, если мы не можем напрямую полагаться на нормальный порядок операций. С другой стороны, выражения Postfix можно писать без скобок, и при этом сохраняется надлежащий порядок операций.
Давайте создадим простой преобразователь инфикса в постфикс, который работает с арифметическими операторами, не содержащими круглых скобок, например a + b * c. Для этого преобразователя мы будем помещать арифметические операторы в стек в зависимости от их приоритета и помещать идентификаторы в оператор постфикса.
Вот программа:
#include <iostream>
#include <stack>
using namespace std;
int getPrecedence(char op) {
if (op == '+' || op == '-') {
return 1;
}
else if (op == '*' || op == '/') {
return 2;
}
else if (op == '^') {
return 3;
}
else {
return 0;
}
}
bool isOp(char ch) {
if (ch == '+' || ch == '-' || ch == '*' ||
ch == '/' || ch == '^') {
return true;
}
return false;
}
int main()
{
stack<char> s;
string infix = "a+b*c";
string postfix = "";
char ch;
for (unsigned i = 0; i < infix.size(); i++) {
ch = infix[i];
if (isOp(ch)) {
if (s.empty()) {
s.push(ch);
}
else if (getPrecedence(ch) >= getPrecedence(s.top())) {
s.push(ch);
}
}
else {
postfix += ch;
}
}
if (!s.empty()) {
while (!s.empty()) {
postfix += s.top();
s.pop();
}
}
cout << infix << endl;
cout << postfix << endl;
return 0;
}
Отличным расширением этой программы было бы добавление проверки скобок, чтобы вы могли преобразовывать даже более сложные выражения. Если вы сделаете это расширение, я хотел бы увидеть вашу программу.
Использование стеков
Я только что показал вам три примера использования стеков для решения задач программирования. В более технической информатике стеки используются для управления функциями (см. Стек вызовов), управления памятью (см. Выделение памяти на основе стека), а также в алгоритмах для поиска с возвратом (см. Отслеживание с возвратом) и для создания многих других алгоритмов. более эффективным.
Благодарим за прочтение этой статьи. Отправляйте комментарии и предложения по электронной почте.
