Как реализовать 3 стека с одним массивом?

Question

Иногда я сталкиваюсь со следующим вопросом интервью: как реализовать 3 стека с одним массивом?Конечно, любое статическое распределение не является решением.

Answer 1

Эффективное пространство (не время).Вы можете:

1) Определить два стека, начинающиеся в конечных точках массива и растущие в противоположных направлениях.

2) Определите третий стек, начиная с середины и увеличивая его в любом направлении.

3) Переопределите опцию Push, так что когда операция собирается перезаписать другой стек, вы сдвигаете весь средний стек в противоположном направлении, прежде чем нажать.

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

Редактировать

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

Редактировать

Следуя предложению @ ruslik, средний стек может быть реализован с использованием чередующейся последовательности для последующих нажатий.Полученная структура стека будет выглядеть примерно так:

|Элем 6 |Элем 4 |Элем 2 |Элем 0 |Элем 1 |Элем 3 |Элем 5 |

В этом случае вам нужно сохранить число n элементов в среднем стеке и использовать функцию:

f[n_] := 1/4 ( (-1)^n (-1 + 2 n) + 1) + BS3  

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

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

Answer 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

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

Обновление:

Из-за приведенных ниже комментариев, которые имеют очень хорошую точку зрения, следует добавить, что встраивание не является необходимым и может даже ухудшить производительность по сравнению с гораздо более простой схемой памяти, такой как следующее:

+----+----+----+----+----+----+----+----+----+----+----+----+----+..
| A1 : A2 :    :    :    | B1 : B2 : B3 : B4 :    | C1 : C2 : C3 :  
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
       ^                                  ^                    ^
       A´s top                            B´s top              C´s top

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

В этом случае я бы пошел с @ belisarius 'ответом : один стек уходит в «нижний» конец области памяти, увеличиваясь «вверх»; другой стек перемещается в «верхний» конец области памяти, увеличиваясь «вниз», и один стек находится посередине, который растет в любом направлении, но может перемещаться, когда он подходит слишком близко к одному из других стеков. *

Answer 3

Поддерживайте единую арену для всех трех стеков.Каждый элемент, помещенный в стек, имеет обратный указатель на свой предыдущий элемент.Дно каждого стека имеет указатель на NULL / None.

Арена поддерживает указатель на следующий элемент в свободном пространстве.Нажатие добавляет этот элемент в соответствующий стек и помечает его как уже не в свободном пространстве.Pop удаляет элемент из соответствующего стека и добавляет его в свободный список.

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

Объекту, содержащему три стека, нужен указатель на вершину каждого стека плюс указатель на заголовоксвободный список.

Эта структура данных использует все пробелы и выдвигает и выталкивает в постоянном времени.Затраты на один указатель для всех элементов данных в стеке, а в свободных элементах списка используется максимум (два указателя, один указатель + один элемент).

---

Позже: код 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()

Answer 4

У меня есть решение для этого вопроса.Следующая программа наилучшим образом использует этот массив (в моем случае это массив объектов 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();
        }
    }
}

Answer 5

Для простоты, если не очень эффективное использование памяти, вы можете [*] разделить массив на узлы списка, добавить их все в список свободных узлов, а затем реализовать свои стеки как связанные списки, отбирая узлы из свободного списка.как требуется.Однако в этом подходе нет ничего особенного в числе 3.

[*] на языке низкого уровня, где память может использоваться для хранения указателей или если элементы стека имеют тип, такой как int который может представлять индекс в массиве.

Answer 6

Вариант с более ранним ответом: стек № 1 растет слева, а стек № 2 - справа.

Стек # 3 находится в центре, но элементы растут в чередующемся порядке влево и вправо.Если N является центральным индексом, стек увеличивается следующим образом: N, N-1, N + 1, N-2, N + 2 и т. Д. Простая функция преобразует индекс стека в индекс массива.

Answer 7

Существует множество решений этой проблемы, уже заявленных на этой странице.ИМХО фундаментальные вопросы:

• Сколько времени занимает каждая операция push / pop?

• Сколько места используется?В частности, каково наименьшее количество элементов, которые можно поместить в три стека, чтобы структура данных исчерпала пространство?

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

В этом посте я буду ссылаться на решения, которые работают намного лучше,и я представлю самый простой.

---

Чтобы более подробно описать пространство решений, я буду ссылаться на две функции структуры данных следующим образом:

Структуракоторый требует O (f (n)) амортизированного времени для выполнения push / pop и не заканчивается места, если три стека не содержат по крайней мере n - O (g (n)) элементов будут называться (f, g) структура. Меньшие f и g лучше.Каждая структура, уже размещенная на этой странице, имеет n для времени или пространства.Я продемонстрирую (1, √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, √n).

---

Разделите массив на блоки размера Θ (√n).Блоки пронумерованы от 1 до Θ (√n), а номер блока называется его «адресом».Адрес может храниться в слоте массива вместо реального элемента.На элемент в данном блоке можно ссылаться с номером, меньшим, чем O (√n), и такой номер называется индексом.Индекс также помещается в слот массива.

Первый блок будет отведен для хранения адресов и индексов, и никакой другой блок не будет хранить никаких адресов или индексов.Первый блок называется каталогом .Каждый блок, не являющийся каталогом, будет пустым или содержит элементы только одного из трех стеков;то есть ни в одном блоке не будет двух элементов из разных стеков.Кроме того, каждый стек будет иметь не более одного блока, который частично заполнен - ​​все остальные блоки, связанные со стеком, будут полностью заполнены или полностью пусты.

Пока существует пустой блок, операция push будетбыть разрешенным к любому стеку.Поп-операции всегда разрешены.При сбое операции push структура данных заполнена.В этот момент количество слотов, не содержащих элементов из одного из стеков, составляет не более O (√n): два частично заполненных блока из стеков, в которые не помещается, и один блок каталога.

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

Каталог содержит:

• Триадреса для блоков в верхней части трех стеков или 0, если в конкретном стеке еще нет блоков

• Три индекса для элемента в верхней части трех стеков, или0, если в конкретном стеке еще нет элементов.

• Для каждого полного или частично полного блока адрес блока ниже, чем в том же стеке, или 0, если онсамый низкий блок в стеке.

• Адрес свободного блока, называемого лидерным блоком, или 0, если свободных блоков нет

• Для каждого свободного блока - адрес другого свободного блока или 0, если свободных блоков больше нет

Последние два представляют собой стек, хранящийся в виде односвязного списка свободных блоков. То есть, следуя адресам свободных блоков, начиная с блока-лидера, вы получите путь через все свободные блоки, заканчивающийся на 0.

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

В противном случае вытолкните стек свободных блоков, изменив адрес блока-лидера на адрес следующего свободного блока в стеке свободных блоков. Измените адрес и индекс для стека, чтобы он был адресом только что выскочившего свободного блока и 1 соответственно. Добавьте элемент в только что появившийся блок с индексом 1 и верните.

Все операции занимают O (1) время. Поп симметричный.

Answer 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 b3c3 ...

Могут быть пробелы, но мы всегда знаем верхние индексы, которые хранятся в 3-элементном массиве topIndex.

Answer 9

Я думаю, что вы должны разделить массив на 3 части, делая заголовок первого стека равным 0, заголовок второго стека на уровне n / 3, заголовок третьего стека на уровне n-1.

, поэтому реализуйте операцию push на:

1. первый и второй стек составляют i ++, а для третьего стека - i -;
2. Если вы столкнулись с тем, что в первом стеке нет места для нажатия, сдвиньте 2-й стек на k / 3 позицийвперед.Где k - количество позиций, оставшихся для заполнения в массиве.
3. Если вы столкнулись с тем, что у второго стека нет места для нажатия, сдвиньте 2-й стек на 2 * k / 3 позиции назад.Где k - количество оставшихся позиций для заполнения в массиве.
4. Если вы столкнулись с тем, что у третьего стека нет места для нажатия, сдвиньте 2-й стек на 2 * k / 3 позиции назад.Где k - количество позиций, оставшихся для заполнения в массиве.

Мы сдвигаем k / 3 и 2 * k / 3, когда не осталось места, чтобы после сдвига среднего стека каждый стекиметь равное пространство для использования.

Answer 10

Вот мое решение для 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();
        }
    }
}