Структура данных стека используется в информатике по-разному. В языках программирования вызовы функций реализуются с использованием стека для управления вызовом функции. В приложениях стеки используются для оценки числовых выражений и могут использоваться для преобразования чисел между различными основаниями, например, из десятичного в двоичное или из двоичного в шестнадцатеричное.
Стеки также не так уж сложно реализовать, потому что существует ограниченное количество операций, которые может выполнять стек. Три основных оператора: 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.
Я представил вам два примера того, как можно использовать стек для решения проблем. Если вас интересуют другие задачи, связанные со стеками, поищите в Интернете, как использовать стек для преобразования инфиксных арифметических уравнений в постфиксные уравнения или как использовать стек для балансировки символов в операторе, например круглые скобки, используемые в арифметике.
Спасибо за прочтение и, пожалуйста, ответьте на эту статью или напишите мне по электронной почте с вашими комментариями и предложениями.