Чем это отличается от предложения Руслика от 23 января 11 года?

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

 Dr. belisarius23 янв. 2011 г., 09:13
@Rafal Futzerberger настроен на пять стеков, а не на три :)
 Dr. belisarius23 янв. 2011 г., 04:45
@sth Я думаю, это означает, что ограничение каждого стека пространством n / 3 не является правильным решением.
 sth22 янв. 2011 г., 22:37
Ты имеешь в видудинамический Распределение памяти не является решением?
 Matthieu M.24 янв. 2011 г., 15:30
@Michael: Я все же определенно отвечу сначала, используя решение по модулю. Может быть, это не то, что они ищут, но это показывает, что вы сами не усложняете проблему.
 Rafał Dowgird23 янв. 2011 г., 08:35
Я подозреваю, что это вопрос, где не существует идеального решения, разработанного, чтобы показать, как вы подходите к проблемам. Лучшая стратегия состоит в том, чтобы обмануть ваш путь - сказать им, что вы будете использовать алгоритм Футцербергера, а затем кричать на них, что они не слышали об этом.

Ответы на вопрос(14)

питон

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

 greybeard27 дек. 2015 г., 05:58
не документировано, код tl: dr - что особенного в этой реализации и как онаwith one array?

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

поэтому выполните операцию push на:

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

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

нце» массива, вам не хватает места для третьего стека.

Тем не менее, вы можете «перемежать» элементы стека. Элементы первого стека находятся по индексам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: Один стек уходит в «нижний» конец области памяти, увеличиваясь «вверх»; другой стек идет к «верхнему» концу области памяти, растя «вниз», и один стек находится посередине, который растет в любом направлении, но может перемещаться, когда он оказывается слишком близко к одному из других стеков.

 stakx22 янв. 2011 г., 23:38
@ Ферруччо, это не так. По крайней мере, не фундаментально. Память расходуется более «равномерно». А поскольку значения остаются «ближе друг к другу», кэши ЦП могут лучше справляться с вкраплениями стеков.
 Ferruccio22 янв. 2011 г., 23:29
Чем это отличается от произвольного разделения массива на три статически распределенных раздела одинакового размера?
 ruslik23 янв. 2011 г., 01:28
это на самом деле хуже. Скорее всего, они не будут использоваться с одинаковой скоростью, и каждый стек будет использовать разную строку кэша, таким образом используя в 3 раза большую пропускную способность памяти. 3 явно разных стека будут иметь лучшую местность. Кроме того, основной вопрос заключается в том, чтобы ограничить общий размер доступным пространством, а не каждым из них одной третью.

Вот мое решение для этого в C # -

/*  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

 greybeard27 дек. 2015 г., 06:41
Неплохо для именования источников и представления документированного кода. Не новый (здесь), но для языка реализации.
 Ankit27 дек. 2015 г., 08:30
Спасибо @greybeard! Да, только что попробовал сегодня его написать, поэтому подумал, что поделюсь своей реализацией в C #. Интересная проблема!

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

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

Вставляя любой элемент, вставьте его в конце всех элементов в обычном массиве. Сохраните current-top этого стека как родительский для нового элемента (в массиве parent) и обновите current-top до новой позиции.

При удалении вставьте NULL в массив стеков для удаленного элемента и сбросьте верхнюю часть стека для этого стека до родительского.

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

для получения более подробной информации обратитесь по этой ссылке: - https://coderworld109.blogspot.in/2017/12/how-to-implement-3-stacks-with-one-array.html

 Mohit Thakur30 дек. 2017 г., 08:15
coderworld109.blogspot.in/2017/12/... Я предлагаю вам прочитать его здесь: все pop () и push () выполняются за O (1) время // принимая от geeksforgeeks ссылку о том, что Стив использует мой стэк, это экономит память, но не экономит время, чтобы сделать его более эффективный я делаю пост в стеке следуйте по ссылке о
 greybeard30 дек. 2017 г., 11:12
Задачаimplement 3 stacks with one array, Это предполагаетAn auxiliary array: проголосовал против. (А что ты предлагаешьуплотнение или желинейный поиск за? Означает ли этоне с помощьюродительс длясвободно узлы?)
 Mohit Thakur30 дек. 2017 г., 12:29
брат, я просто говорю вам альтернативное решение, я знаю, что это не тот ответ, который был задан. (именно поэтому я дал вам только ссылку) я нашел расширенную версию этого вопроса, которая сделала push и pop в O (1)) я думаю, что вам понятно
 greybeard30 дек. 2017 г., 00:11
Чем это отличается отОтвет Стива Джессопа?

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> stk3_value1> stk4> stk # 4 stk4_value9, stk4_value8, stk4_value7, stk4_value6, stk4_value5, stk4_value4, stk4_value3, stk4_value2, stk4_value1

 greybeard27 дек. 2015 г., 06:18
Недокументированный код - что особенного в этой реализации,где и почему это печатает этот вывод?

ом использует этот массив (в моем случае это массив объектов 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();
        }
    }
}
 superuser06 апр. 2014 г., 16:23
нет документации .. но я нашел код аккуратным и самоочевидным ..

когда первый стек попадает в индекс 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.

 smttsp01 дек. 2017 г., 07:06
Хорошая идея, но если a становится 1/3 + 1, а остальные стеки пусты, вам не хватит места
 Anthony Raimondo03 нояб. 2017 г., 16:47
Хорошее решение, не думайте о массиве как о линейном ... думайте о нем как о матрице
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];
    }

};

 Aiias08 апр. 2013 г., 05:12
Когда вы отправляете только исходный код, вы должны подумать о добавлении комментариев, чтобы люди могли следить за вашим ходом мыслей через ваш код.
 greybeard27 дек. 2015 г., 06:03
Чем это отличается от предложения Руслика от 23 января 11 года?
 Fox21 сент. 2013 г., 07:18
Проголосовал без объяснения причин !! Хотя мы можем проследить ваш код ... нам было бы легче понять вашу логику ..

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

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

 greybeard27 дек. 2015 г., 05:52
Есть что-то особенное в простоте, а также в том, что она не эпигона, не говоря уже о не исповедующей.
Решение Вопроса

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

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

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

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

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

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

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

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

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

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

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

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

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

 ruslik23 янв. 2011 г., 15:29
@belisarius: простое улучшение: вы можетеpush околоBS3 : BS3, BS3 + 1, BS3-1, BS3 + 2, BS3-2 и так далее. Это будет держать третий стек посередине и половину скорости приближения к стеку 2. Это напоминает мне о хорошей проблемеf(f(n))==-n;
 MahlerFive23 янв. 2011 г., 07:18
Незначительная точка, но может быть лучше начать средний стек на 1/3 пути через массив, а не в средней точке. Если предположить, что стеки в среднем заполнены примерно с одинаковой скоростью, это будет означать, что вы можете ждать дольше, чтобы сделать первый большой ход.
 Dr. belisarius23 янв. 2011 г., 04:55
@ruslik Конечно, это возможно. Просто используйте массив как связанный список. Но у вас много места впустую, и это как-то противоречит концепции «использовать массив».
 ruslik23 янв. 2011 г., 01:32
Это лучшее решение, но я бы пересмотрел опцию push, чтобы средний стек не перемещался полностью. Это сложнее, но возможно.
 Dr. belisarius24 янв. 2011 г., 20:17
@hugh Потому что, если нет, вы должны сохранять указатели, и я попытался сделать решение с эффективным использованием пространства, поэтому я не позволил дополнительное место для указателей.

уже заявленные на этой странице. Основными вопросами, ИМХО, являются:

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

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

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

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

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

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

Это все основано на:

Майкл Л. Фредман и Дебора Л. Голдсмит, «Три стека», в журнале алгоритмов, том 17, выпуск 1, июль 1994 года, страницы 45–70

Более ранняя версия появилась на 29-м ежегодном симпозиуме по основам компьютерных наук (FOCS) в 1988 году.

Кандидатская диссертация Деборы Луизы Голдсмит из Калифорнийского университета, Сан-Диего, факультет электротехники / компьютерных наук в 1987 году, «Эффективное управление памятью для> = 3 стеков»

Они показывают, хотя я не буду представлять, (log n / log S, S) структуру для любого S. Это эквивалентно a (t, n1 / т) структура для любого т. Я покажу упрощенную версию структуры (1, √n).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

помещенный в стек, имеет обратный указатель на свой предыдущий элемент. Дно каждого стека имеет указатель на 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()

стек № 1 растет слева, а стек № 2 растет справа.

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

 Dr. belisarius23 янв. 2011 г., 07:13
Вы можете исчерпать пространство для любого стека до того, как весь ваш массив заполнится.

Ваш ответ на вопрос