Стек

рубрики: Структуры данных | Дата: 21 июня, 2026
Скачать обработку с примерами из статьи: professia1c_stack.epf
Платформа: 8.3; Тип формы: управляемая.

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

Сегодня мы рассмотрим такую структуру данных как стек. Стек — это структура данных, которая работает по принципу LIFO, то есть последним зашел, первым вышел. Если приводить аналогии из реального мира, то у меня в уме почему-то возникает консервы с кольцами ананаса. Их где-то на заводе сложили в банку одно за другим. А мы открываем банку и достаем их сверху. То, которое на заводе положили последним, мы достаем первым. Ну и понятно, что в отличие от банки с консервами, мы не обязаны сначала полностью заполнить стек, а потом полностью его опустошить. Операции помещения элементов в стек и извлечения из него могут следовать друг за другом в произвольном порядке.

Какие задачи решает стек

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

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

Существуют гораздо более сложные алгоритмы, которые требуют применения стека. В частности это работа с графами. Напомню, что граф — это такая структура, которая состоит из вершин и соединяющих их ребер. Всем хорошо известное ДеревоЗначений тоже можно рассматривать как граф. Так вот, стек может использоваться в алгоритмах работы с графами. Например, в DFS (Depth-First Search), то есть в алгоритме обхода графа в глубину.

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

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

Пример

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

&НаКлиенте
Перем Стек;

#Область ПредопределенныеПроцедурыФормы

&НаКлиенте
Процедура ПриОткрытии(Отказ)
	
	Стек = Новый Массив;
	
КонецПроцедуры

#КонецОбласти

#Область Стек

&НаКлиенте
Процедура ДобавитьВСтек(ЭлементСтека)

	Стек.Добавить(ЭлементСтека);

КонецПроцедуры

&НаКлиенте
Функция ИзвлечьИзСтека()

	Индекс = Стек.ВГраница();
	Если Индекс = -1 Тогда
		Возврат Неопределено;
	КонецЕсли;
	
	ВерхнийЭлемент = Стек[Индекс];
	Стек.Удалить(Индекс);
	
	Возврат ВерхнийЭлемент;
	
КонецФункции

#КонецОбласти

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

Теперь реализуем процедуру, которая будет непосредственно валидировать строку с использованием стека и его методов.

&НаКлиенте
Процедура ПроверитьСкобки()
	
	Стек.Очистить();

	Для Индекс = 1 По СтрДлина(СтрокаВалидации) Цикл
		
		Символ = Сред(СтрокаВалидации, Индекс, 1);
		
		Если Символ = "(" Тогда
			
			Стек.Добавить(Символ);
			
		ИначеЕсли Символ = ")" Тогда
			
			Если ИзвлечьИзСтека() = Неопределено Тогда
				
				ПоказатьОповещениеПользователя(
					"Ошибка: ", ,
					"Найдена закрывающая скобка без открывающей", ,
					СтатусОповещенияПользователя.Важное);
					
				Возврат;
				
			КонецЕсли;
			
		КонецЕсли;
		
	КонецЦикла;
	
	Если Стек.Количество() > 0 Тогда
		
		ПоказатьОповещениеПользователя(
			"Ошибка: ", ,
			"Есть открывающие скобки без закрывающих", ,
			СтатусОповещенияПользователя.Важное);
			
		Возврат;
		
	КонецЕсли;
	
	ПоказатьОповещениеПользователя(
		"Проверка пройдена: ", ,
		"Количество открывающих скобок соответствует количеству закрывающих", ,
		СтатусОповещенияПользователя.Информация);
	
КонецПроцедуры

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