Подобно многим задачам, все зависит от того, как мы собираемся поддерживать эти стеки. Если нам нужно выделить определенное пространство для каждого стека, можно так и поступить. Но в этом случае один из стеков может исчерпать ресурсы, а другие будут практически пустыми.
Можно, конечно, использовать более гибкую систему разделения пространства, но это значительно усложняет задачу.
Подход 1. Фиксированное разделение
Можно разделить массив на три равные части и разрешить стекам развитие в пределах ограниченного пространства. Обратите внимание, что далее мы будем описывать границы диапазонов с помощью скобок: квадратные скобки [] означают, что граничные значения входят в диапазон, а круглые скобки — значения не входят.
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-компанию»
