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

Стеки также не так уж сложно реализовать, потому что существует ограниченное количество операций, которые может выполнять стек. Три основных оператора: 1) размещение нового элемента в стеке; 2) извлечение верхнего элемента из стека; и 3) проверка элемента в верхней части стопки. Есть также несколько других служебных функций, которые вы можете реализовать, но для правильного использования стека все, что вам нужно, - это эти три операции.

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

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

Описание стеков

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

Одним из примеров является стопка бумаги, загруженная в принтер. Когда принтер хочет напечатать страницу, он берет лист бумаги сверху стопки бумаги и затем печатает на нем. Если вы хотите печатать на фирменных бланках или на бумаге, еще не загруженной в принтер, вам нужно поместить этот лист бумаги в верхнюю часть стопки.

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

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

Оказывается, этот дизайн также полезен для многих компьютерных приложений, о некоторых из которых я упоминал выше.

Дизайн классов стека

Моя реализация стека использует класс JavaScript, а не просто объект. Мне нравится абстракция классов JavaScript, и если вы решите перенести свою реализацию на другой язык, такой как C ++ или Java, дизайн JavaScript будет для вас более полезным, чем если бы вы реализовали стек с использованием прототипов JavaScript. Если вы не знакомы с классами JavaScript, вот статья, которую я написал, в которой подробно обсуждается, как создавать и использовать классы JavaScript.

Ключом к разработке эффективного класса стека является использование правильной базовой структуры данных для хранения элементов стека. Я буду использовать массив в качестве хранилища данных для моего класса стека. Массивы JavaScript имеют несколько хороших встроенных методов, которые упрощают работу с ними.

Операции со стеком реализованы как методы (функции) класса, которые могут быть вызваны из экземпляра Stack. Помимо push, pop и top, я также буду реализовывать метод size для определения количества элементов в стеке, метод empty для проверки наличия данных в экземпляре стека и метод clear для удаления всех содержимое стека.

Поскольку в стеке так мало операций, мы готовы перейти к реализации класса Stack.

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

Так же, как список операций со стеком короткий, код, необходимый для реализации класса Stack, также короткий. По иронии судьбы, первые два метода, push и pop, имеют идентично названные функции, используемые для одной и той же цели с массивами JavaScript. Вот определение класса Stack:

class Stack {
  constructor() { 
    this.dataStore = []
  }
  push(element) {
    this.dataStore.push(element)
  }
  pop() {
    this.dataStore.pop()
  }
  top() {
    return this.dataStore[this.dataStore.length-1]
  }
  size() {
    return this.dataStore.length;
  }
  empty() {
    if (this.dataStore.length == 0) {
      return true;
    }
    return false;
  }
  clear() {
    if (this.dataStore.length == 0) {
      return;
    }    
    while (this.dataStore.length > 0) {
      this.dataStore.pop();
    }
  }
}

Метод конструктора инициализирует базовую структуру хранения данных, массив dataStore.

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

Количество элементов в массиве - это размер стека, поэтому мы возвращаем длину массива как количество хранимых элементов стека.

Если в стеке 0 элементов (длина равна 0), то он пуст.

Стек очищается путем выталкивания всех элементов в массив.

Программа тестирования стека

Прежде чем продемонстрировать использование стека для решения некоторых полезных задач, я напишу небольшую программу для тестирования всех методов класса. Вот тестовая программа:

let myStack = new Stack();
myStack.push("Mike");
myStack.push("Terri");
myStack.push("Meredith");
putstr("Top of stack: ");
print(myStack.top());
putstr("Number of elements on the stack: ");
print(myStack.size());
if (!myStack.empty()) {
  myStack.clear();
}
putstr("Top of supposedly empty stack: ");
print(myStack.top());
myStack.clear();
putstr("Number of elements on the stack: ");
print(myStack.size());

А вот результат работы программы:

Top of stack: Meredith
Number of elements on the stack: 3
Top of supposedly empty stack: undefined
Number of elements on the stack: 0

Я закончил представлять класс Stack, поэтому давайте перейдем к использованию этого класса для решения некоторых проблем.

Преобразование десятичных чисел в двоичные

Стек можно использовать для преобразования чисел из одной базы в другую. Я продемонстрирую это, написав программу, которая преобразует десятичное число (основание 10) в двоичное число (основание 2). Алгоритм работает, сначала беря базовое число для преобразования по модулю основания и помещая это значение в стек. Затем вы делите число на основание, и это частное становится новым основным числом.

Чтобы получить преобразованное число, постройте строку, выталкивая стек до тех пор, пока в стеке не останется чисел.

Вот программа для преобразования десятичного числа в двоичное с использованием класса Stack:

let digits = new Stack();
const base = 2;
putstr("Enter the base number: ");
let decimal = readline();
putstr("Decimal number: ");
print(decimal);
while (decimal != 0) {
  let digit = decimal % base;
  digits.push(digit);
  decimal = parseInt(decimal / base);
}
let converted = "";
while (!digits.empty()) {
  converted += digits.top();
  digits.pop();
}
putstr("Binary number: ");
print(converted);

Вот результат пары запусков программы:

C:\js>js stack.js
Enter the base number: 123
Decimal number: 123
Binary number: 1111011
C:\js>js stack.js
Enter the base number: 1024
Decimal number: 1024
Binary number: 10000000000

В поисках палиндромов

В моем втором примере использования стека я продемонстрирую, как использовать стек, чтобы определить, является ли слово палиндромом. Палиндром - это слово, которое пишется одинаково вперед и назад. Например, гоночная машина - это палиндром; боб - палиндром; привет это не палиндром.

Мой любимый палиндром - это на самом деле предложение, которое становится палиндромом, когда вы убираете пробелы: человек план панамского канала.

Вероятно, вы быстро поймете, как можно использовать стек, чтобы определить, является ли слово палиндромом. Программа перемещается по строке, извлекая каждую букву и помещая ее в стек. Когда у вас закончились буквы, просмотрите стопку, вставляя каждую букву в новую строку. Если исходная строка и строка, построенная из стека, совпадают, слово является палиндромом.

Вот программа, которая использует стек, чтобы определить, является ли слово палиндромом:

let letters = new Stack();
putstr("Enter a word: ");
let originWord = readline();
putstr("Word: ");
print(originWord);
let stop = originWord.length;
for (let i = 0; i < stop; i++) {
  letters.push(originWord[i]);
}
let reversed = "";
while (!letters.empty()) {
  reversed += letters.top();
  letters.pop();
}
putstr("Reversed word: ");
print(reversed);
if (reversed == originWord) {
  print(originWord + " is a palindrome.");
}
else {
  print(originWord + " is not a palindrome.");
}

Вот результат пары запусков программы:

C:\js>js stack.js
Enter a word: racecar
Word: racecar
Reversed word: racecar
racecar is a palindrome.
C:\js>js stack.js
Enter a word: hello
Word: hello
Reversed word: olleh
hello is not a palindrome.
C:\js>js stack.js
Enter a word: amanaplanacanalpanama
Word: amanaplanacanalpanama
Reversed word: amanaplanacanalpanama
amanaplanacanalpanama is a palindrome.

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

Спасибо за прочтение и, пожалуйста, ответьте на эту статью или напишите мне по электронной почте с вашими комментариями и предложениями.