Структуры данных. Стек

Это краткий дополненный конспект части о стеке в книге Гид по Computer Science, Вильям Спрингер.

Основная информация

Стек — это структура данных типа LIFO (Last In, First Out — «последним пришел, первым ушел»). Элементы добавляются или удаляются только сверху. Полезны в операциях, где требуется ведение истории.

Можно реализовать на основе

• массива (отслеживая текущую длину стека) - ограничение на размер стека.
• односвязного списка (отслеживая head списка - помещать элемент в начало. Тогда извлекаемый элемент всегда будет первым в списке.) - нет ограничений по размеру.

Четыре основные операции, время O(1):

• push - поместить элемент в стек. Если размер стека ограничен и он заполнен, возникнет ошибка переполнения.
• pop - извлечь элемент из стека. Если стек пуст - ошибка обнуления.
• isEmpty - проверить, пуст ли стек
• size - получить количество элементов в стеке
• peek - просмотреть верхний элемент стека, но не удалять его. Равно извлечению верхнего элемента и его повторному помещению в стек.

Реализация в JavaScript

В JavaScript массив уже представляет собой стек. Он предоставляет такие методы как push и pop.

Интересно попробовать реализовать его с помощью связного списка.

Реализацию основывала на примере с этого сайта. Для своего я использую реализацию связного списка, которую приводила ранее.

1class Stack {
2	constructor() {
3	  this.linkedList = new LinkedList();
4	}
5	
6	isEmpty() {
7	  return !this.linkedList.head;
8	}
9	
10	peek() {
11	  if (this.isEmpty()) {
12		return null;
13	  }
14	  return this.linkedList.head.value;
15	}
16	
17	push(value) {
18	  this.linkedList.add(value);
19	}
20	
21	pop() {
22	  this.linkedList.remove();
23	}
24}

Пример использования

Типичным примером использования стека является проверка сбалансированности фигурных скобок. Рассмотрим язык, в котором скобки должны быть парными: каждой правой скобке (}) предшествует соответствующая левая скобка ({). Мы можем прочитать строку и каждый раз, когда встречается левая скобка, помещать ее в стек. Всегда, когда встречается правая скобка, мы будем извлекать левую скобку из стека. Если попытаться извлечь фигурную скобку из стека, но стек окажется пустым, это будет означать, что у правой фигурной скобки нет соответствующей левой скобки. Если в конце строки стек окажется не пустым, это будет означать, что считано больше левых скобок, чем правых. В противном случае все скобки в строке окажутся парными.

Я реализовала этот пример на JavaScript так:

1function checkCurlyBrackets(string) {
2	let stack = [];
3	let message = ``;
4
5	for (let i = 0; i <= string.length - 1; i++) {
6		if (string[i] === "{") {
7			stack.push(string[i]);
8		}
9
10		if (string[i] === "}") {
11			if (stack.length === 0) {
12				return (message = "Правая фигурная скобка не имеет пары.");
13			}
14
15			stack.pop();
16		}
17	}
18
19	if (stack.length > 0) {
20		message =
21			"Стэк не пуст. Левых фигурных скобок в строке больше, чем правых.";
22	} else {
23		message = "true";
24	}
25
26	return message;
27}
28
29const string1 = "This {} is a string {} with curly {} brackets:";
30const string2 = "This {} is a string } with curly {} brackets:";
31const string3 = "This {} is a string {} with curly { brackets:";
32
33console.log(checkCurlyBrackets(string1)); //true
34console.log(checkCurlyBrackets(string2)); //Правая фигурная скобка не имеет пары.
35console.log(checkCurlyBrackets(string3)); //Стэк не пуст. Левых фигурных скобок в строке больше, чем правых.