Иногда я сталкиваюсь с следующим вопросом интервью: Как реализовать 3 стека с одним массивом? Конечно, любое статическое распределение не является решением.
Как реализовать 3 стека с одним массивом?
Ответ 1
Пространство (не время). Вы могли:
1) Определите два стека, начиная с конечных точек массива и растущих в противоположных направлениях.
2) Определите третий стек как начинающийся в середине и растущий в любом направлении.
3) Переопределите опцию Push, так что, когда операция перезапишет другой стек, вы переместите весь средний стек в противоположном направлении перед нажатием.
Вам нужно сохранить верхнюю часть стека для первых двух стеков, а также начало и конец третьего стека в некоторой структуре.
Edit
Вышеприведенный пример. Перемещение выполняется с использованием политики разделения пространства, хотя другие стратегии могут быть выбраны в зависимости от вашей эвристики проблемы.
Изменить
Следуя предложению @ruslik, стек средний может быть реализован с использованием чередующейся последовательности для последующих нажатий. Результирующая структура стека будет выглядеть примерно так:
| Elem 6 | Elem 4 | Elem 2 | Elem 0 | Elem 1 | Elem 3 | Elem 5 |
В этом случае вам нужно будет сохранить число n элементов в среднем стеке и использовать функцию:
f[n_] := 1/4 ( (-1)^n (-1 + 2 n) + 1) + BS3
чтобы узнать следующий элемент массива, который будет использоваться для этого стека.
Хотя, вероятно, это приведет к меньшему смещению, реализация не является однородной для трех стеков, а неоднородность (вы знаете) приводит к особым случаям, большим ошибкам и трудностям для поддержания кода.
Ответ 2
Пока вы пытаетесь упорядочить все элементы из одного стека вместе на один "конец" массива, вам не хватает места для третьего стека.
Однако вы можете "пересечь" элементы стека. Элементы первого стека имеют индексы i * 3, элементы второго стека имеют индексы i * 3 + 1, элементы третьего стека находятся в индексе i * 3 + 2 (где i - целое число).
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
| A1 : B1 : C1 | A2 : B2 : C2 | : B3 | C3 | : B4 : | :
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
^ ^ ^
A´s top C´s top B´s top
Конечно, эта схема уходит в ненужное пространство, особенно когда стеки имеют неравные размеры. Вы можете создать произвольно сложные схемы, подобные описанным выше, но, не зная никаких ограничений для поставленного вопроса, я остановлюсь здесь.
Update:
Из-за комментариев ниже, которые имеют очень хорошую точку, следует добавить, что перемежение не требуется и может даже ухудшить производительность по сравнению с гораздо более простым макетом памяти, например следующим:
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
| A1 : A2 : : : | B1 : B2 : B3 : B4 : | C1 : C2 : C3 :
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
^ ^ ^
A´s top B´s top C´s top
то есть. предоставляя каждому стеку собственный непрерывный блок памяти. Если реальный вопрос заключается в том, как максимально использовать фиксированный объем памяти, чтобы не ограничивать каждый стек больше, чем необходимо, тогда мой ответ не будет очень полезен.
В этом случае я бы пошел с ответом @belisarius: один стек идет в "нижний" конец области памяти, растет "вверх"; другой стек переходит в "верхний" конец области памяти, растет "вниз", а один стек находится посередине, который растет в любом направлении, но может перемещаться, когда он становится слишком близко к одному из других стеков.
Ответ 3
Поддержание одной арены для всех трех стеков. Каждый элемент, вставленный в стек, имеет обратный указатель на его предыдущий элемент. В нижней части каждого стека есть указатель на NULL/None.
Арена поддерживает указатель на следующий элемент в свободном пространстве. Толкатель добавляет этот элемент в соответствующий стек и отмечает его как больше не в свободном пространстве. Поп удаляет элемент из соответствующего стека и добавляет его в свободный список.
Из этого эскиза элементам в стеках требуется обратный указатель и пространство для данных. Элементы в свободном пространстве нуждаются в двух указателях, поэтому свободное пространство реализуется как дважды связанный список.
Объект, содержащий три стека, должен содержать указатель на вершину каждого стека плюс указатель на главу свободного списка.
Эта структура данных использует все пространство и толкает и всплывает в постоянное время. Накладные расходы на один указатель для всех элементов данных в стеке, а свободные элементы списка используют максимум (два указателя, один указатель + один элемент).
Позже: код python выглядит примерно так. Обратите внимание на использование целых индексов в качестве указателей.
class StackContainer(object):
def __init__(self, stack_count=3, size=256):
self.stack_count = stack_count
self.stack_top = [None] * stack_count
self.size = size
# Create arena of doubly linked list
self.arena = [{'prev': x-1, 'next': x+1} for x in range(self.size)]
self.arena[0]['prev'] = None
self.arena[self.size-1]['next'] = None
self.arena_head = 0
def _allocate(self):
new_pos = self.arena_head
free = self.arena[new_pos]
next = free['next']
if next:
self.arena[next]['prev'] = None
self.arena_head = next
else:
self.arena_head = None
return new_pos
def _dump(self, stack_num):
assert 0 <= stack_num < self.stack_count
curr = self.stack_top[stack_num]
while curr is not None:
d = self.arena[curr]
print '\t', curr, d
curr = d['prev']
def _dump_all(self):
print '-' * 30
for i in range(self.stack_count):
print "Stack %d" % i
self._dump(i)
def _dump_arena(self):
print "Dump arena"
curr = self.arena_head
while curr is not None:
d = self.arena[curr]
print '\t', d
curr = d['next']
def push(self, stack_num, value):
assert 0 <= stack_num < self.stack_count
# Find space in arena for new value, update pointers
new_pos = self._allocate()
# Put value-to-push into a stack element
d = {'value': value, 'prev': self.stack_top[stack_num], 'pos': new_pos}
self.arena[new_pos] = d
self.stack_top[stack_num] = new_pos
def pop(self, stack_num):
assert 0 <= stack_num < self.stack_count
top = self.stack_top[stack_num]
d = self.arena[top]
assert d['pos'] == top
self.stack_top[stack_num] = d['prev']
arena_elem = {'prev': None, 'next': self.arena_head}
# Link the current head to the new head
head = self.arena[self.arena_head]
head['prev'] = top
# Set the curr_pos to be the new head
self.arena[top] = arena_elem
self.arena_head = top
return d['value']
if __name__ == '__main__':
sc = StackContainer(3, 10)
sc._dump_arena()
sc.push(0, 'First')
sc._dump_all()
sc.push(0, 'Second')
sc.push(0, 'Third')
sc._dump_all()
sc.push(1, 'Fourth')
sc._dump_all()
print sc.pop(0)
sc._dump_all()
print sc.pop(1)
sc._dump_all()
Ответ 4
Для простоты, если не очень эффективное использование памяти, вы можете [*] разделить массив на узлы списка, добавить их все в список свободных узлов, а затем реализовать свои стеки в качестве связанных списков, взяв узлы из бесплатного списка как требуется. Однако в этом подходе нет ничего особенного в этом вопросе.
[*] на низкоуровневом языке, где память может использоваться для хранения указателей или если элементы стека имеют тип, например int, который может представлять индекс в массив.
Ответ 5
У меня есть решение для этого вопроса. Следующая программа наилучшим образом использует массив (в моем случае - массив объектов StackNode). Дайте мне знать, если у вас есть какие-либо вопросы по этому поводу. [Это довольно поздно, поэтому я не стал документировать код - я знаю, я должен:)]
public class StackNode {
int value;
int prev;
StackNode(int value, int prev) {
this.value = value;
this.prev = prev;
}
}
public class StackMFromArray {
private StackNode[] stackNodes = null;
private static int CAPACITY = 10;
private int freeListTop = 0;
private int size = 0;
private int[] stackPointers = { -1, -1, -1 };
StackMFromArray() {
stackNodes = new StackNode[CAPACITY];
initFreeList();
}
private void initFreeList() {
for (int i = 0; i < CAPACITY; i++) {
stackNodes[i] = new StackNode(0, i + 1);
}
}
public void push(int stackNum, int value) throws Exception {
int freeIndex;
int currentStackTop = stackPointers[stackNum - 1];
freeIndex = getFreeNodeIndex();
StackNode n = stackNodes[freeIndex];
n.prev = currentStackTop;
n.value = value;
stackPointers[stackNum - 1] = freeIndex;
}
public StackNode pop(int stackNum) throws Exception {
int currentStackTop = stackPointers[stackNum - 1];
if (currentStackTop == -1) {
throw new Exception("UNDERFLOW");
}
StackNode temp = stackNodes[currentStackTop];
stackPointers[stackNum - 1] = temp.prev;
freeStackNode(currentStackTop);
return temp;
}
private int getFreeNodeIndex() throws Exception {
int temp = freeListTop;
if (size >= CAPACITY)
throw new Exception("OVERFLOW");
freeListTop = stackNodes[temp].prev;
size++;
return temp;
}
private void freeStackNode(int index) {
stackNodes[index].prev = freeListTop;
freeListTop = index;
size--;
}
public static void main(String args[]) {
// Test Driver
StackMFromArray mulStack = new StackMFromArray();
try {
mulStack.push(1, 11);
mulStack.push(1, 12);
mulStack.push(2, 21);
mulStack.push(3, 31);
mulStack.push(3, 32);
mulStack.push(2, 22);
mulStack.push(1, 13);
StackNode node = mulStack.pop(1);
node = mulStack.pop(1);
System.out.println(node.value);
mulStack.push(1, 13);
} catch (Exception e) {
e.printStackTrace();
}
}
}
Ответ 6
Вариант более раннего ответа: стек # 1 растет слева, а стек # 2 растет справа.
Стек № 3 находится в центре, но элементы растут поочередно влево и вправо. Если N является центральным индексом, стек растет как: N, N-1, N + 1, N-2, N + 2 и т.д. Простая функция преобразует индекс стека в индекс массива.
Ответ 7
Я думаю, вам следует разделить массив на 3 части, сделав голову первого стека на 0, головку второго стека на n/3, голову третьего стека на n-1.
чтобы реализовать операцию push:
- первый и второй стек делают я ++ и для третьего стека делают я -;
- Если вы столкнулись с тем, что первый стек не имеет места для сдвига, сдвиньте второй стек k/3 позиций вперед. Где k - количество позиций, оставшихся для заполнения массивом.
- Если вы столкнулись с тем, что второй стек не имеет места для сдвига, сдвиньте второй стек 2 * k/3 положения назад. Где k - количество позиций, оставшихся для заполнения массивом.
- Если вы столкнулись с тем, что у третьего стека нет места для сдвига, сдвиньте второй стек 2 * k/3 положения назад. Где k - количество позиций, оставшихся для заполнения массивом.
Мы сдвигаем k/3 и 2 * k/3, когда не осталось места, так что после сдвига среднего стека каждый стек имеет равное пространство для использования.
Ответ 8
Храните стек в области таким образом, когда первый стек переходит в индекс 0, затем 0 + 3 = 3, затем 3 + 3 = 6...; второй - в индексы 1, 1 + 3 = 4, 4 + 3 = 7...; третий - в индексы 2, 2 + 3 = 5, 5 + 3 = 8 Поэтому, если мы отметим первые элементы стека с a, как один с b, а там с c, получим: a1 b1 c1 a2 b2 c2 a3 b3 c3...
Там могут быть пробелы, но мы всегда знаем верхние индексы, которые хранятся в 3-элементном массиве topIndex.
Ответ 9
Есть много решений этой проблемы, уже упомянутых на этой странице. Основные вопросы, IMHO:
-
Сколько времени занимает каждая операция push/pop?
-
Сколько места используется? В частности, каково наименьшее количество элементов, которые могут быть перенесены на три стека, чтобы заставить структуру данных работать вне пространства?
Насколько я могу судить, каждое решение, уже размещенное на этой странице, может занять до линейного времени для push/pop или может закончиться пробелом с линейным количеством пробелов, все еще пустым.
В этом посте я буду ссылаться на решения, которые работают намного лучше, и я представлю простейший.
Чтобы более подробно описать пространство решений, я буду ссылаться на две функции структуры данных следующим образом:
Структура, которая берет O (f (n)) за амортизированное время, чтобы выполнить push/pop и не исчерпывает место, если три стека не удерживают хотя бы n-O (g (n)) элементы будут отнесены к как структуру (f, g). Меньшие f и g лучше. Каждая структура, уже размещенная на этой странице, имеет n для времени или пространства. Я продемонстрирую структуру (1, & radic; n).
Все это основано на:
-
Майкл Л. Фредман и Дебора Л. Голдсмит, "Три стека", в Journal of Algorithms, том 17, выпуск 1, июль 1994 г., стр. 45-70
- Более ранняя версия появилась на 29-м ежегодном симпозиуме по основам информатики (FOCS) в 1988 году.
-
Дебора Луиза Голдсмит Докторская диссертация из Калифорнийского университета в Сан-Диего, факультет электротехники/информатики в 1987 году, "Эффективное управление памятью для >= 3 стека"
Они показывают, хотя я не буду представлять структуру (log n/log S, S) для любого S. Это эквивалентно структуре (t, n 1/t) для любого т. Я покажу упрощенную версию, которая представляет собой структуру (1, & radic; n).
Разделите массив на блоки размера & Theta; (& radic; n). Блоки пронумерованы от 1 до & Theta; (& radic; n), а номер блока называется его "адресом". Адрес может быть сохранен в слоте массива вместо реального элемента. Элемент в данном блоке может ссылаться на число, меньшее O (& radic; n), и такое число называется индексом. Индекс также поместится в слот массива.
Первый блок будет зарезервирован для хранения адресов и индексов, и ни один другой блок не сохранит никаких адресов или индексов. Первый блок называется каталогом. Каждый блок без каталога будет либо пустым, либо содержать элементы только из одного из трех стеков; то есть ни один блок не будет иметь два элемента из разных стеков. Кроме того, каждый стек будет иметь не более одного блока, который будет частично заполнен - все остальные блоки, связанные со стеком, будут полностью заполнены или полностью пусты.
Пока существует пустой блок, в любой стек будет разрешена операция push. Поп-операции всегда разрешены. Когда операция push не работает, структура данных заполнена. В этот момент количество слотов, не содержащих элементов из одного из стеков, не более O (& radic; n): два частично заполненных блока из стеков, которые не были нажаты, и один блок каталогов.
Каждый блок упорядочен так, чтобы элементы, расположенные ближе к передней части блока (нижние индексы), были ближе к нижней части стека.
В каталоге:
-
Три адреса для блоков в верхней части трех стеков или 0, если в конкретном стеке еще нет блоков
-
Три индекса для элемента в верхней части трех стеков или 0, если еще нет элементов в определенном стеке.
-
Для каждого полного или частично полного блока адрес блока ниже его в том же стеке или 0, если он является самым низким блоком в стеке.
-
Адрес свободного блока, называемый лидирующим блоком, или 0, если свободных блоков
-
Для каждого свободного блока адрес другого свободного блока, или 0, если свободных блоков нет
Эти последние два представляют собой стек, хранящийся как отдельный список свободных блоков. То есть, следуя адресам свободных блоков, начиная с блока-лидера, выдается путь через все свободные блоки, заканчивающиеся на 0.
Чтобы вытащить элемент в стек, найдите его верхний блок и верхний элемент внутри этого блока, используя каталог. Если в этом блоке есть место, поместите туда элемент и верните его.
В противном случае поместите стек свободных блоков, изменив адрес блока-лидера на адрес следующего свободного блока в стеке свободных блоков. Измените адрес и индекс для стека как адрес только что выскоченного свободного блока и 1, соответственно. Добавьте элемент в только что появившийся блок с индексом 1 и верните.
Все операции занимают время O (1). Поп симметричен.
Ответ 10
Решение: Реализация двух стеков проста. Первый стек растет от начала до конца, а второй растет от начала до конца. Переполнение для любого из них не произойдет, если в массиве не останется свободного места.
Для трех стеков требуется следующее: Вспомогательный массив для поддержки родителя для каждого node. Переменные для хранения текущей вершины каждого стека. С этими двумя на месте данные из всех стеков могут быть перемежены в исходном массиве, и все еще можно выполнять операции push/pop/size для всех стеков.
При вставке любого элемента вставьте его в конец всех элементов в нормальном массиве. Сохраните текущую вершину этого стека как родителя для нового элемента (в массиве родителей) и обновите текущую вершину до новой позиции.
При удалении вставьте NULL в массив стеков для удалённого элемента и reset stack-top для этого стека родительскому.
Когда массив заполнен, он будет иметь некоторые отверстия, соответствующие удаленным элементам. На этом этапе либо массив может быть уплотнен, чтобы объединить все свободное пространство, либо линейный поиск может быть сделан для свободного пространства при вставке новых элементов.
для получения дополнительной информации обратитесь к этой ссылке: - https://coderworld109.blogspot.in/2017/12/how-to-implement-3-stacks-with-one-array.html
Ответ 11
Вот мое решение из N стеков в одном массиве.
Некоторые ограничения будут здесь. этот размер массива будет не меньше количества стеков.
Я использовал для настройки исключения класса StackException в моем решении. Вы можете изменить класс исключения для запуска программы.
Для нескольких стеков в массиве я управлял указателями на другой массив.
package com.practice.ds.stack;
import java.util.Scanner;
import java.util.logging.Logger;
/** Multiple stacks in a single array */
public class MultipleStack {
private static Logger logger = Logger.getLogger("MultipleStack");
private int[] array;
private int size = 10;
private int stackN = 1;
private int[] pointer;
public MultipleStack() {
this.array = new int[size];
this.pointer = new int[1];
}
public MultipleStack(int size, int stackN) throws StackException {
if (stackN > size)
throw new StackException("Input mismatch ! no of stacks can't be larger than size ");
this.size = size;
this.stackN = stackN;
init();
}
private void init() {
if (size <= 0) {
logger.info("Initialize size is " + size + " so assiginig defalt size ");
this.size = 10;
}
if (stackN < 1) {
logger.info("Initialize no of Stack is " + size + " so assiginig defalt");
this.stackN = 1;
}
this.array = new int[size];
this.pointer = new int[stackN];
initializePointer();
}
private void initializePointer() {
for (int i = 0; i < stackN; i++)
pointer[i] = (int)(i * Math.ceil(size / stackN) - 1);
}
public void push(int item, int sn) throws StackException {
if (full(sn))
throw new StackException(sn + " is overflowed !");
int stkPointer = pointer[sn - 1];
array[++stkPointer] = item;
pointer[sn - 1] = stkPointer;
}
public void pop(int sn) throws StackException {
if (empty(sn))
throw new StackException(sn + " is underflow !");
int peek = peek(sn);
System.out.println(peek);
pointer[sn - 1] = --pointer[sn - 1];
}
public int peek(int sn) throws StackException {
authenticate(sn);
return array[pointer[sn - 1]];
}
public boolean empty(int sn) throws StackException {
authenticate(sn);
return pointer[sn - 1] == (int)(((sn - 1) * Math.ceil(size / stackN)) - 1);
}
public boolean full(int sn) throws StackException {
authenticate(sn);
return sn == stackN ? pointer[sn - 1] == size - 1 : pointer[sn - 1] == (int)((sn) * Math.ceil(size / stackN)) - 1;
}
private void authenticate(int sn) throws StackException {
if (sn > stackN || sn < 1)
throw new StackException("No such stack found");
}
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
System.out.println("Define size of the stack");
int size = scanner.nextInt();
System.out.println("total number of stacks");
int stackN = scanner.nextInt();
MultipleStack stack = new MultipleStack(size, stackN);
boolean exit = false;
do {
System.out.println("1. Push");
System.out.println("2. Pop");
System.out.println("3. Exit");
System.out.println("Choice");
int choice = scanner.nextInt();
switch (choice) {
case 1:
try {
System.out.println("Item : ");
int item = scanner.nextInt();
System.out.println("Stack Number : ");
int stk = scanner.nextInt();
stack.push(item, stk);
} catch (Exception e) {
e.printStackTrace();
}
break;
case 2:
try {
System.out.println("Stack Number : ");
int stk = scanner.nextInt();
stack.pop(stk);
} catch (Exception e) {
e.printStackTrace();
}
break;
case 3:
exit = true;
break;
default:
System.out.println("Invalid choice !");
break;
}
} while (!exit);
} catch (Exception e) {
e.printStackTrace();
}
}
}
Ответ 12
Python
class Stack:
def __init__(self):
self.pos_1 = 0
self.pos_2 = 1
self.pos_3 = 2
self.stack = [None, None, None]
def pop_1(self):
if self.pos_2 - 1 > 0:
to_ret = self.stack.pop(self.pos_1)
self.pos_2 -= 1
self.pos_3 -= 1
return to_ret
def push_1(self, value):
self.stack.insert(self.pos_1, value)
self.pos_2 += 1
self.pos_3 += 1
return None
def pop_2(self):
if self.pos_2 - 1 < self.pos_3:
to_ret = self.stack.pop(self.pos_2)
self.pos_3 -= 1
return to_ret
def push_2(self, value):
self.stack.insert(self.pos_2, value)
self.pos_3 += 1
return None
def pop_3(self):
if self.pos_3 - 1 > self.pos_2:
to_ret = self.stack.pop(self.pos_3)
return to_ret
def push_3(self, value):
self.stack.insert(self.pos_3, value)
return None
if __name__ == "__main__":
stack = Stack()
stack.push_2(22)
stack.push_1(1)
stack.push_1(2)
print stack.pop_1()
print stack.pop_1()
print stack.pop_2()
отпечатки: 2 1 22
Ответ 13
Здесь мое решение для него в С# -
/* Program: Implement 3 stacks using a single array
*
* Date: 12/26/2015
*/
using System;
namespace CrackingTheCodingInterview
{
internal class Item
{
public object data;
public int prev;
}
/// <summary>
/// Class implementing 3 stacks using single array
/// </summary>
public class Stacks
{
/// <summary>
/// Pushing an element 'data' onto a stack 'i'
/// </summary>
public void Push(int i, object d)
{
i--;
if (available != null)
{
int ava = (int)available.DeleteHead();
elems[ava].data = d;
elems[ava].prev = top[i];
top[i] = ava;
}
else
{
Console.WriteLine("Array full. No more space to enter!");
return;
}
}
/// <summary>
/// Popping an element from stack 'i'
/// </summary>
public object Pop(int i)
{
i--;
if (top[i] != -1)
{
object popVal = elems[top[i]].data;
int prevTop = elems[top[i]].prev;
elems[top[i]].data = null;
elems[top[i]].prev = -1;
available.Insert(top[i]);
top[i] = prevTop;
return popVal;
}
else
{
Console.WriteLine("Stack: {0} empty!", i);
return null;
}
}
/// <summary>
/// Peeking top element of a stack
/// </summary>
public object Peek(int i)
{
i--;
if (top[i] != -1)
{
return elems[top[i]].data;
}
else
{
Console.WriteLine("Stack: {0} empty!", i);
return null;
}
}
/// <summary>
/// Constructor initializing array of Nodes of size 'n' and the ability to store 'k' stacks
/// </summary>
public Stacks(int n, int k)
{
elems = new Item[n];
top = new int[k];
for (int i = 0; i < k; i++)
{
top[i] = -1;
}
for (int i = 0; i < n; i++)
{
elems[i] = new Item();
elems[i].data = null;
elems[i].prev = -1;
}
available = new SinglyLinkedList();
for (int i = n - 1; i >= 0; i--)
{
available.Insert(i);
}
}
private Item[] elems;
private int[] top;
private SinglyLinkedList available;
}
internal class StacksArrayTest
{
static void Main()
{
Stacks s = new Stacks(10, 3);
s.Push(1, 'a');
s.Push(1, 'b');
s.Push(1, 'c');
Console.WriteLine("After pushing in stack 1");
Console.WriteLine("Top 1: {0}", s.Peek(1));
s.Push(2, 'd');
s.Push(2, 'e');
s.Push(2, 'f');
s.Push(2, 'g');
Console.WriteLine("After pushing in stack 2");
Console.WriteLine("Top 1: {0}", s.Peek(1));
Console.WriteLine("Top 2: {0}", s.Peek(2));
s.Pop(1);
s.Pop(2);
Console.WriteLine("After popping from stack 1 and 2");
Console.WriteLine("Top 1: {0}", s.Peek(1));
Console.WriteLine("Top 2: {0}", s.Peek(2));
s.Push(3, 'h');
s.Push(3, 'i');
s.Push(3, 'j');
s.Push(3, 'k');
s.Push(3, 'l');
Console.WriteLine("After pushing in stack 3");
Console.WriteLine("Top 3: {0}", s.Peek(3));
Console.ReadLine();
}
}
}
Вывод:
After pushing in stack 1
Top 1: c
After pushing in stack 2
Top 1: c
Top 2: g
After popping from stack 1 and 2
Top 1: b
Top 2: f
After pushing in stack 3
Top 3: l
Я ссылаюсь на этот пост для его кодирования - http://codercareer.blogspot.com/2013/02/no-39-stacks-sharing-array.html
Ответ 14
Мы можем обобщить это до K стеков в одном массиве. Основная идея заключается в следующем:
- Поддерживайте PriorityQueue в качестве минимальной кучи текущих свободных индексов в массиве размещения.
- Сохраняйте массив размера K, который содержит вершину стека, для каждого из стеков.
- Создайте класс данных с 1) значением 2) индексом элемента Prev в массиве размещения 3) индексом текущего элемента, помещаемого в массив размещения
- Поддерживать массив размещения типа Data
Обратитесь к коду для рабочего примера реализации.
import java.util.*;
public class Main
{
// A Java class to represent k stacks in a single array of size n
public static final class KStack {
/**
* PriorityQueue as min heap to keep track of the next free index in the
* backing array.
*/
private final PriorityQueue<Integer> minHeap = new PriorityQueue<>((a,b) -> (a - b));
/**
* Keeps track of the top of the stack of each of the K stacks
*/
private final Data index[];
/**
* Backing array to hold the data of K stacks.
*/
private final Data array[];
public KStack(int noOfStacks, int sizeOfBackingArray) {
index = new Data[noOfStacks];
array = new Data[sizeOfBackingArray];
for(int i =0; i< sizeOfBackingArray; i++) {
minHeap.add(i);
}
}
public void push(int val, int stackNo) {
if(minHeap.isEmpty()) {
return;
}
int nextFreeIdx = minHeap.poll();
Data tos = index[stackNo];
if(tos == null) {
tos = new Data(val, -1 /* Previous elemnet idx*/, nextFreeIdx
/* This elemnent idx in underlying array*/);
} else {
tos = new Data(val, tos.myIndex, nextFreeIdx);
}
index[stackNo] = tos;
array[nextFreeIdx] = tos;
}
public int pop(int stackNo) {
if(minHeap.size() == array.length) {
return -1; // Maybe throw Exception?
}
Data tos = index[stackNo];
if(tos == null) {
return -1; // Maybe throw Exception?
}
minHeap.add(tos.myIndex);
array[tos.myIndex] = null;
int value = tos.value;
if(tos.prevIndex == -1) {
tos = null;
} else {
tos = array[tos.prevIndex];
}
index[stackNo] = tos;
return value;
}
}
public static final class Data {
int value;
int prevIndex;
int myIndex;
public Data(int value, int prevIndex, int myIndex) {
this.value = value;
this.prevIndex = prevIndex;
this.myIndex = myIndex;
}
@Override
public String toString() {
return "Value: " + this.value + ", prev: " + this.prevIndex + ", myIndex: " + myIndex;
}
}
// Driver program
public static void main(String[] args)
{
int noOfStacks = 3, sizeOfBackingArray = 10;
KStack ks = new KStack(noOfStacks, sizeOfBackingArray);
// Add elements to stack number 1
ks.push(11, 0);
ks.push(9, 0);
ks.push(7, 0);
// Add elements to stack number 3
ks.push(51, 2);
ks.push(54, 2);
// Add elements to stack number 2
ks.push(71, 1);
ks.push(94, 1);
ks.push(93, 1);
System.out.println("Popped from stack 3: " + ks.pop(2));
System.out.println("Popped from stack 3: " + ks.pop(2));
System.out.println("Popped from stack 3: " + ks.pop(2));
System.out.println("Popped from stack 2: " + ks.pop(1));
System.out.println("Popped from stack 1: " + ks.pop(0));
}
}
Ответ 15
пакет job.interview; import java.util.Arrays;
public class NStack1ArrayGen<T> {
T storage[];
int numOfStacks;
Integer top[];
public NStack1ArrayGen(int numOfStks, T myStorage[]){
storage = myStorage;
numOfStacks = numOfStks;
top = new Integer[numOfStks];
for(int i=0;i<numOfStks;i++){top[i]=-1;}
}
public void push(int stk_indx, T value){
int r_indx = stk_indx -1;
if(top[r_indx]+numOfStacks < storage.length){
top[r_indx] = top[r_indx] < 0 ? stk_indx-1 : top[r_indx]+numOfStacks;
storage[top[r_indx]] = value;
}
}
public T pop(int stk_indx){
T ret = top[stk_indx-1]<0 ? null : storage[top[stk_indx-1]];
top[stk_indx-1] -= numOfStacks;
return ret;
}
public void printInfo(){
print("The array", Arrays.toString(storage));
print("The top indices", Arrays.toString(top));
for(int j=1;j<=numOfStacks;j++){
printStack(j);
}
}
public void print(String name, String value){
System.out.println(name + " ==> " + value);
}
public void printStack(int indx){
String str = "";
while(top[indx-1]>=0){
str+=(str.length()>0 ? "," : "") + pop(indx);
}
print("Stack#"+indx,str);
}
public static void main (String args[])throws Exception{
int count=4, tsize=40;
int size[]={105,108,310,105};
NStack1ArrayGen<String> mystack = new NStack1ArrayGen<String>(count,new String[tsize]);
for(int i=1;i<=count;i++){
for(int j=1;j<=size[i-1];j++){
mystack.push(i, "stk"+i+"_value"+j);
}
}
}
}
Отпечатки:
Массив == > [stk1_value1, stk2_value1, stk3_value1, stk4_value1, stk1_value2, stk2_value2, stk3_value2, stk4_value2, stk1_value3, stk2_value3, stk3_value3, stk4_value3, stk1_value4, stk2_value4, stk3_value4, stk4_value4, stk1_value5, stk2_value5, stk3_value5, stk4_value5, stk1_value6, stk2_value6, stk3_value6, stk4_value6, stk1_value7, stk2_value7, stk3_value7, stk4_value7, stk1_value8, stk2_value8, stk3_value8, stk4_value8, stk1_value9, stk2_value9, stk3_value9, stk4_value9, stk1_value10, stk2_value10, stk3_value10, stk4_value10] Верхние индексы == > [36, 37, 38, 39] Стек # 1 == > stk1_value10, stk1_value9, stk1_value8, stk1_value7, stk1_value6, stk1_value5, stk1_value4, stk1_value3, stk1_value2, stk1_value1 Стек # 2 == > stk2_value10, stk2_value9, stk2_value8, stk2_value7, stk2_value6, stk2_value5, stk2_value4, stk2_value3, stk2_value2, stk2_value1 Stack # 3 == > stk3_value10, stk3_value9, stk3_value8, stk3_value7, stk3_value6, stk3_value5, stk3_value4, stk3_value3, stk3_value2, stk3_value1 Stack # 4 == > stk4_value10, stk4_value9, stk4_value8, stk4_value7, stk4_value6, stk4_value5, stk4_value4, stk4_value3, stk4_value2, stk4_value1
Ответ 16
enum stackId{LEFT, MID, RIGHT };
class threeStacks {
int* arr;
int leftSize;
int rightSize;
int midSize;
int mid;
int maxSize;
public:
threeStacks(int n):leftSize(0), rightSize(0), midSize(0), mid(n/2), maxSize(n)
{
arr = new int[n];
}
void push(stackId sid, int val){
switch(sid){
case LEFT:
pushLeft(val);
break;
case MID:
pushMid(val);
break;
case RIGHT:
pushRight(val);
}
}
int pop(stackId sid){
switch(sid){
case LEFT:
return popLeft();
case MID:
return popMid();
case RIGHT:
return popRight();
}
}
int top(stackId sid){
switch(sid){
case LEFT:
return topLeft();
case MID:
return topMid();
case RIGHT:
return topRight();
}
}
void pushMid(int val){
if(midSize+leftSize+rightSize+1 > maxSize){
cout << "Overflow!!"<<endl;
return;
}
if(midSize % 2 == 0){
if(mid - ((midSize+1)/2) == leftSize-1){
//left side OverFlow
if(!shiftMid(RIGHT)){
cout << "Overflow!!"<<endl;
return;
}
}
midSize++;
arr[mid - (midSize/2)] = val;
}
else{
if(mid + ((midSize+1)/2) == (maxSize - rightSize)){
//right side OverFlow
if(!shiftMid(LEFT)){
cout << "Overflow!!"<<endl;
return;
}
}
midSize++;
arr[mid + (midSize/2)] = val;
}
}
int popMid(){
if(midSize == 0){
cout << "Mid Stack Underflow!!"<<endl;
return -1;
}
int val;
if(midSize % 2 == 0)
val = arr[mid - (midSize/2)];
else
val = arr[mid + (midSize/2)];
midSize--;
return val;
}
int topMid(){
if(midSize == 0){
cout << "Mid Stack Underflow!!"<<endl;
return -1;
}
int val;
if(midSize % 2 == 0)
val = arr[mid - (midSize/2)];
else
val = arr[mid + (midSize/2)];
return val;
}
bool shiftMid(stackId dir){
int freeSpace;
switch (dir){
case LEFT:
freeSpace = (mid - midSize/2) - leftSize;
if(freeSpace < 1)
return false;
if(freeSpace > 1)
freeSpace /= 2;
for(int i=0; i< midSize; i++){
arr[(mid - midSize/2) - freeSpace + i] = arr[(mid - midSize/2) + i];
}
mid = mid-freeSpace;
break;
case RIGHT:
freeSpace = maxSize - rightSize - (mid + midSize/2) - 1;
if(freeSpace < 1)
return false;
if(freeSpace > 1)
freeSpace /= 2;
for(int i=0; i< midSize; i++){
arr[(mid + midSize/2) + freeSpace - i] = arr[(mid + midSize/2) - i];
}
mid = mid+freeSpace;
break;
default:
return false;
}
}
void pushLeft(int val){
if(midSize+leftSize+rightSize+1 > maxSize){
cout << "Overflow!!"<<endl;
return;
}
if(leftSize == (mid - midSize/2)){
//left side OverFlow
if(!shiftMid(RIGHT)){
cout << "Overflow!!"<<endl;
return;
}
}
arr[leftSize] = val;
leftSize++;
}
int popLeft(){
if(leftSize == 0){
cout << "Left Stack Underflow!!"<<endl;
return -1;
}
leftSize--;
return arr[leftSize];
}
int topLeft(){
if(leftSize == 0){
cout << "Left Stack Underflow!!"<<endl;
return -1;
}
return arr[leftSize - 1];
}
void pushRight(int val){
if(midSize+leftSize+rightSize+1 > maxSize){
cout << "Overflow!!"<<endl;
return;
}
if(maxSize - rightSize - 1 == (mid + midSize/2)){
//right side OverFlow
if(!shiftMid(LEFT)){
cout << "Overflow!!"<<endl;
return;
}
}
rightSize++;
arr[maxSize - rightSize] = val;
}
int popRight(){
if(rightSize == 0){
cout << "Right Stack Underflow!!"<<endl;
return -1;
}
int val = arr[maxSize - rightSize];
rightSize--;
return val;
}
int topRight(){
if(rightSize == 0){
cout << "Right Stack Underflow!!"<<endl;
return -1;
}
return arr[maxSize - rightSize];
}
};