питон

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

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

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

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

Вот мое решение для этого в 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

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

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

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

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

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

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

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

ом использует этот массив (в моем случае это массив объектов 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();
        }
    }
}

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

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];
    }

};

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

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

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

Сколько времени занимает каждая операция 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

Кандидатская диссертация Деборы Луизы Голдсмит из Калифорнийского университета, Сан-Диего, факультет электротехники / компьютерных наук в 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 и т. Д. Простая функция преобразует индекс стека в индекс массива.