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

1

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

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

Подход 1. Фиксированное разделение

Можно разделить массив на три равные части и разрешить стекам развитие в пределах ограниченного пространства. Обратите внимание, что далее мы будем описывать границы диапазонов с помощью скобок: квадратные скобки [] означают, что граничные значения входят в диапазон, а круглые скобки — значения не входят.

• Стек 1: [0, n/3).
• Стек 2: [n/3, 2n/3).
• Стек 3: [2n/3, n].

Код для этого решения приведен ниже:

int stackSize = 100;
int[] buffer = new int [stackSize * 3];
int[] stackPointer = {0,0,0};	//указатели для отслеживания верхних элементов

void push(int stackNum, int value) throws Exception {
	/* Проверяем, есть ли пространство */
	if (stackPointer[stackNum] >= stackSize){
		throw new Exception("Недостаточно пространства.");
	}
	/* аходим индекс верхнего элемента массива + 1,
	* и увеличиваем указатель стека */
	int index = stackNum * stackSize + stakPointer[stackNum] + 1;
	stackPointer[stackNum]++;
	buffer[index] = valuse;
}

int pop(int stackNum) throws Exception {
	if (stackPointer[stackNum] == 0) {
		throw new Exception("Попытка использовать пустой стек");
	}
	int index = stackNum * stackSize + stackPointer[stackNum];
	stackPointer[stackNum]--;
	int value = buffer[index];
	buffer[index] = 0;
	return value;
}

int peek(int stackNum) {
	int index = stackNum * stackSize + stackPointer[stackNum];
	return buffer[index];
}

boolean isEmpty(int stackNum) {
	return stackPointer[stackNum] ==0;
}

Если у нас есть дополнительная информация о назначении стеков, можно модифицировать алгоритм. Например, если предполагается, что в стеке 1 будет больше элементов, чем в стеке 2, можно перераспределить пространство в пользу стека 1.

Подход 2. Гибкое разделение

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

Кроме того, можно создать массив таким образом, чтобы последний стек начинался в конце массива и заканчивался в начале, — «закольцевать» массив.

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

/* StackData - простой класс, который хранит набор данных о каждом стеке
* Коласс не содержит элементы стека! */
public class stackData{
	public int start;
	public int pointer;
	public int size = 0;
	public int capacity;
	public stackData(int _start, int _capacity){
		start = _start;
		pointer = _start -1;
		capacity = _capacity;
	}
	
	public boolean isWithinStack(int index, int total_size){
		if(start + capacity <= total_size) { // нормальный размер
			if(start <= index && index <= start + capacity) {
				return true;
			} else {
				return false;
			}
		} else {	// стек отсекается вокруг начала массива
			int shifted_index = index + total_size;
			if (start <= shifted_index &&
			shifted_index <= start + capacity){
				return true;
			} else {
				return false;
			}
		}
	}
}

public class Question B {
	static int number_of_stack = 3;
	static int default_size = 4;
	static int total_size = default_size * number_of_stack;
	static StackData [] stacks = {new StackData(0, default_size),
	new StackData(default_size, default_size),
	new StackData(default_size * 2, default_size)};
static int [] buffer = new int [total_size];

public static void main(String [] args) throw Exception {
	push(0,10);
	push(1,20);
	push(2,30);
	int v = pop(0);
	...
}

public static int nextElement(int index) {
	if (index + 1 == total_size) return 0;
	else return index + 1;
}

public static int previousElement(int index) {
if (index ==0) return total_size - 1;
	else return index - 1;
}

public static void shift(int stackNum) {
	StackData stack = stacks[stackNum];
	if (stack.size >= stack.capacity) {
		int nextStack = (stackNum + 1) % number_of_stacks;
		shift(nextStack); // выполняем сдвиг
		stack.capacity++;
	}
	
	//Сдвигаем элементы в обратном порядке
	for (int i = (stack.start + stack.capacity -1) %  total_size;
		stack.isWithinStack(i, total_size);
		i=previousElement(i)) {
			buffer[i] = buffer[previousElement(i)];
		}
	
		buffer[stack.start] = 0;
		stack.start = nextElement(stack.start); //перемещаем начало стека
		stack.pointer = nextElement(stack.pointer); // перемещаем указатель
		stack.capacity--; // устанавливаем оригинальный размер
	}

	/* Расширяем стек, сдвигаем остальные стеки */
	public static void expand(int stackNum) {
		shift((stackNum + 1) % number_of_stacks);
		stacks[stackNum].capacity++;
	}

	public static void push(int stackNum, int value)
	throws Exception {
		StackData stack = stacks[stackNum];
		/* Проверим, есть ли размер */
		if (stack.size >= stack.capacity) {
			if (numberOfElements() >= total_size) { // Totally full
				throw new Exception("Ндостаточно пространства.");
			} else {	// Нужно выполнить сдвиг
				expand(stackNum);
			}
		}
		/* Находим индекс верхнего элемента в массиве +1,
		* и увеличиваем указатель стека */
		stack.size++;
		stack.pointer = nextElement(stack.pointer);
		buffer[stack.pointer] = value;
	}
	public static int pop(int stackNum) throws Exception{
		StackData stack = stacks[stackNum];
		if (stack.size == 0) {
			throw new Exception("Попытка использовать пустой стек");
		}
		int value = buffer[stack.pointer];
		buffer[stack.pointer] = 0;
		stack.pointer = previousElement(stack.pointer);
		stack.size--;
		return value;
	}
	
	public static int peek(int stackNum) {
		StackData stack = stacks[stackNum];
		return buffer[stack.pointer];
	}
	
	public static boolean isEmpty(int stackNum) {
		StackData stack = stacks[stackNum];
		return stack.size == 0;
	}
}

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

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»

Что думаете?