Написать пост

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

Аватар Типичный программист

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

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

Подход 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-компанию»

Следите за новыми постами
Следите за новыми постами по любимым темам
7К открытий7К показов