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

Question

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

Answer 1

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

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

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

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

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

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

Answer 2

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

Answer 3

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 * ​​1006 *

Answer 4

enum stackId{LEFT, MID, RIGHT };

класс 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];
    }

};

Answer 5

пакет 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 Стек # 3 ==> stk3_value10, stk3_value9, stk3_value8, stk3_value7, stk3_value6, stk3_value5, stk3_value4, stk3_value3, stk3_value2, stk3_value1 Стек # 4 ==> stk4_value10, stk4_value9, stk4_value8, stk4_value7, stk4_value6, stk4_value5, stk4_value4, stk4_value3, stk4_value2, stk4_value1