Читать книгу Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию - Гейл Макдауэлл - Страница 31

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

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

Стек использует порядок LIFO (последним вошел, первым вышел). Стек подобен

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

1 class Stack {

2 Node top;

3

4 Object pop() {

5 if (top!= null) {

6 Node item = top.data;

7 top = top.next;

8 return item;

9 }

10 return null;

11 }

12

13 void push(Object item) {

14 Node t = new Node(item);

15 t.next = top;

16 top = t;

17 }

18

19 Object peek() {

20 return top.data;

21 } 22 }

Реализация очереди

Очередь использует порядок FIFO (первым вошел, первым вышел). Элементы удаляются из очереди в том же порядке, в котором были добавлены.

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

1 class Queue {

2 Node first, last;

3

4 void enqueue(Object item) {

5 if (!first) {

6 last = new Node(item);

7 first = last;

8 } else {

9 last.next = new Node(item);

10 last = last.next;

11 }

12 }

13

14 Node dequeue(Node n) {

15 if (first!= null) {

16 Object item = first.data;

17 first = first.next;

18 return item;

19 }

20 return null;

21 }

22 }

Вопросы собеседования

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

3.2. Как реализовать стек, в котором кроме стандартных функций push и pop будет использоваться функция min, возвращающая минимальный элемент? Оценка времени работы функций push, pop и min – O(1).

3.3. Представьте стопку тарелок. Если стопка слишком высокая, она может развалиться. В реальной жизни, когда высота стопки превысила бы некоторое значение, мы начали бы складывать тарелки в новую стопку. Реализуйте структуру данных SetOfStacks, имитирующую реальную ситуацию. Структура SetOfStack должна состоять из нескольких стеков, новый стек создается, как только предыдущий достигнет порогового значения. Методы SetOfStacks. push() и SetOfStacks.pop() должны работать с общим стеком (со всей структурой) и должны возвращать те же значения, как если бы у нас был один большой стек.

Дополнительно

Реализуйте функцию popAt(int index), которая осуществляет операцию pop в указанный под-стек.

3.4. В задаче про Ханойскую башню задействованы 3 башни и Nдисков разных размеров, которые нужно переместить, (больший диск нельзя класть на меньший). Имеются следующие ограничения:

1) за один раз можно переместить только один диск;

2) диски перемещаются только с вершины одной башни на другую башню;

3) диск можно положить только поверх большего диска.

Напишите программу перемещения дисков (с первой башни на последнюю) с использованием стеков.

3.5. Создайте класс MyQueue, который реализует очередь с использованием двух стеков.

3.6. Напишите программу сортировки стека по возрастанию. Можно использовать дополнительные стеки для хранения элементов, но нельзя копировать элементы в другие структуры данных (например, в массив). Стек поддерживает следующие операции: push, pop, peek, isEmpty.

3.7. В приюте для животных есть только собаки и кошки, а работа осуществляется в порядке очереди. Люди должны каждый раз забирать «самое старое» (по времени пребывания в питомнике) животное, но могут выбрать кошку или собаку (животное в любом случае будет «самым старым»). Нельзя выбрать любое понравившееся животное. Создайте структуру данных, обслуживающую эту систему и реализующую операции enqueue, dequeueAny, dequeueDog и dequeueCat. Вы должны использовать встроенную структуру данных LinkedList.

Дополнительные вопросы: связные списки (2.7), математика и вероятность (10.7).