Как реализовать три стека, используя один массив

Question

Я столкнулся с этой проблемой на сайте интервью. Проблема требует эффективной реализации трех стеков в одном массиве, так что стек не переполняется до тех пор, пока во всем пространстве массива не останется свободного места.

Для реализации 2 стеков в массиве, это довольно очевидно: 1-й стек увеличивается от LEFT до RIGHT, а 2-й стек - от RIGHT до LEFT; и когда пересечет stackTopIndex, это сигнализирует о переполнении.

Заранее спасибо за ваш проницательный ответ.

Answer 1

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

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

например: у вас есть 3 стека (s1, s2, s3), и вы хотите реализовать это, используя один массив (dataArray []). Следовательно, мы сделаем 3 других массива (a1 [], a2 [], a3 []) для s1, s2 и s3 соответственно, которые будут отслеживать все их элементы в dataArray [] путем сохранения их соответствующего индекса.

insert(s1, 10) at dataArray[0] a1[0] = 0;
insert(s2, 20) at dataArray[1] a2[0] = 1;
insert(s3, 30) at dataArray[2] a3[0] = 2;
insert(s1, 40) at dataArray[3] a1[1] = 3;
insert(s3, 50) at dataArray[4] a3[1] = 4;
insert(s3, 60) at dataArray[5] a3[2] = 5;
insert(s2, 30) at dataArray[6] a2[1] = 6;

и так далее ...

Теперь мы выполним операцию в dataArray [], используя a1, a2 и a3 для соответствующих стеков и очередей.

чтобы вытолкнуть элемент из s1 вернуть a1 [0] сдвинуть все элементы влево

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

Answer 2

Может быть, это может помочь вам немного ... я написал это сам:)

// by ashakiran bhatter
// compile: g++ -std=c++11 test.cpp
// run    : ./a.out
// sample output as below
// adding:  1 2 3 4 5 6 7 8 9
// array contents:  9 8 7 6 5 4 3 2 1
// popping now...
// array contents:  8 7 6 5 4 3 2 1


#include <iostream>
#include <cstdint>

#define MAX_LEN 9
#define LOWER   0
#define UPPER   1
#define FULL   -1
#define NOT_SET -1

class CStack
{
private:
     int8_t array[MAX_LEN];
     int8_t stack1_range[2];
     int8_t stack2_range[2];
     int8_t stack3_range[2];
     int8_t stack1_size;
     int8_t stack2_size;
     int8_t stack3_size;
     int8_t stack1_cursize;
     int8_t stack2_cursize;
     int8_t stack3_cursize;
     int8_t stack1_curpos;
     int8_t stack2_curpos;
     int8_t stack3_curpos;
public:
     CStack();
    ~CStack();

     void push(int8_t data);
     void pop();
     void print();
};

CStack::CStack()
{
     stack1_range[LOWER] = 0;
     stack1_range[UPPER] = MAX_LEN/3 - 1;
     stack2_range[LOWER] = MAX_LEN/3;
     stack2_range[UPPER] = (2 * (MAX_LEN/3)) - 1;
     stack3_range[LOWER] = 2 * (MAX_LEN/3);
     stack3_range[UPPER] = MAX_LEN - 1;

     stack1_size = stack1_range[UPPER] - stack1_range[LOWER];
     stack2_size = stack2_range[UPPER] - stack2_range[LOWER];
     stack3_size = stack3_range[UPPER] - stack3_range[LOWER];

     stack1_cursize = stack1_size;
     stack2_cursize = stack2_size;
     stack3_cursize = stack3_size;

     stack1_curpos = stack1_cursize;
     stack2_curpos = stack2_cursize;
     stack3_curpos = stack3_cursize;
}

CStack::~CStack()
{
}

void CStack::push(int8_t data)
{
     if(stack3_cursize != FULL) 
     {
          array[stack3_range[LOWER] + stack3_curpos--] = data;
          stack3_cursize--;
     } else if(stack2_cursize != FULL) {
          array[stack2_range[LOWER] + stack2_curpos--] = data;
          stack2_cursize--;
     } else if(stack1_cursize != FULL) {   
          array[stack1_range[LOWER] + stack1_curpos--] = data;
          stack1_cursize--;
     } else {
          std::cout<<"\tstack is full...!"<<std::endl;
     }
}

void CStack::pop()
{
     std::cout<<"popping now..."<<std::endl;
     if(stack1_cursize < stack1_size)
     {
          array[stack1_range[LOWER] + ++stack1_curpos] = 0; 
          stack1_cursize++;
     } else if(stack2_cursize < stack2_size) {
          array[stack2_range[LOWER] + ++stack2_curpos] = 0;
          stack2_cursize++;
     } else if(stack3_cursize < stack3_size) {
          array[stack3_range[LOWER] + ++stack3_curpos] = 0;
          stack3_cursize++;
     } else {
          std::cout<<"\tstack is empty...!"<<std::endl;
     }
}

void CStack::print()
{
     std::cout<<"array contents: ";
     for(int8_t i = stack1_range[LOWER] + stack1_curpos + 1; i <=  stack1_range[UPPER]; i++)
          std::cout<<" "<<static_cast<int>(array[i]);
     for(int8_t i = stack2_range[LOWER] + stack2_curpos + 1; i <=  stack2_range[UPPER]; i++)
          std::cout<<" "<<static_cast<int>(array[i]);
     for(int8_t i = stack3_range[LOWER] + stack3_curpos + 1; i <=  stack3_range[UPPER]; i++)
          std::cout<<" "<<static_cast<int>(array[i]);
     std::cout<<"\n";    
}

int main()
{
     CStack stack;

     std::cout<<"adding: ";
     for(uint8_t i = 1; i < 10; i++) 
     {
          std::cout<<" "<<static_cast<int>(i);
          stack.push(i);
     }
     std::cout<<"\n";

     stack.print();

     stack.pop();

     stack.print();


     return 0;
}

Answer 3

Еще одно решение в PYTHON, пожалуйста, дайте мне знать, если это работает так, как вы думаете.

    class Stack(object):

    def __init__(self):
        self.stack = list()

        self.first_length = 0
        self.second_length = 0
        self.third_length = 0

        self.first_pointer = 0
        self.second_pointer = 1

    def push(self, stack_num, item):

        if stack_num == 1:
            self.first_pointer += 1
            self.second_pointer += 1
            self.first_length += 1
            self.stack.insert(0, item)

        elif stack_num == 2:
            self.second_length += 1
            self.second_pointer += 1
            self.stack.insert(self.first_pointer, item)
        elif stack_num == 3:
            self.third_length += 1
            self.stack.insert(self.second_pointer - 1, item)
        else:
            raise Exception('Push failed, stack number %d is not allowd' % stack_num)

    def pop(self, stack_num):
        if stack_num == 1:
            if self.first_length == 0:
                raise Exception('No more element in first stack')
            self.first_pointer -= 1
            self.first_length -= 1
            self.second_pointer -= 1
            return self.stack.pop(0)
        elif stack_num == 2:
            if self.second_length == 0:
                raise Exception('No more element in second stack')
            self.second_length -= 1
            self.second_pointer -= 1
            return self.stack.pop(self.first_pointer)
        elif stack_num == 3:
            if self.third_length == 0:
                raise Exception('No more element in third stack')
            self.third_length -= 1
            return self.stack.pop(self.second_pointer - 1)

    def peek(self, stack_num):
        if stack_num == 1:
            return self.stack[0]
        elif stack_num == 2:
            return self.stack[self.first_pointer]
        elif stack_num == 3:
            return self.stack[self.second_pointer]
        else:
            raise Exception('Peek failed, stack number %d is not allowd' % stack_num)

    def size(self):
        return len(self.items)

s = Stack()

# push item into stack 1
s.push(1, '1st_stack_1')
s.push(1, '2nd_stack_1')
s.push(1, '3rd_stack_1')
#
## push item into stack 2
s.push(2, 'first_stack_2')
s.push(2, 'second_stack_2')
s.push(2, 'third_stack_2')
#
## push item into stack 3
s.push(3, 'FIRST_stack_3')
s.push(3, 'SECOND_stack_3')
s.push(3, 'THIRD_stack_3')
#
print 'Before pop out: '
for i, elm in enumerate(s.stack):
    print '\t\t%d)' % i, elm

#
s.pop(1)
s.pop(1)
#s.pop(1)
s.pop(2)
s.pop(2)
#s.pop(2)
#s.pop(3)
s.pop(3)
s.pop(3)
#s.pop(3)
#
print 'After pop out: '
#
for i, elm in enumerate(s.stack):
    print '\t\t%d)' % i, elm

Answer 4

Этот код реализует 3 стека в одном массиве. Он заботится о пустых местах и ​​заполняет пустые места между данными.

# include

struct stacknode {
int value;
int prev;
};

struct stacknode stacklist [50];
int top [3] = {-1, -1, -1};
int freelist [50];
int stackindex = 0;
int freeindex = -1;

void push (int stackno, int value) {
int index;
if (freeindex> = 0) {
index = freelist [freeindex];
freeindex--;
} else {
index = stackindex;
stackindex ++;
}
стек-лист [index] .value = значение;
if (top [stackno-1]! = -1) {
stacklist [index] .prev = top [stackno-1];
} else {
стек-лист [index] .prev = -1;
}
top [stackno-1] = index;
printf ("% d помещается в стек% d в% d \ n", значение, stackno, индекс);
}

int pop (int stackno) {
int index, value;
if (top [stackno-1] == -1) {
printf («Нет элементов в стеке% d \ n», значение, stackno);
возврат -1;
}
index = top [stackno-1];
freeindex ++;
freelist [freeindex] = index;
значение = стек-лист [индекс] .value;
top [stackno-1] = стек-лист [index] .prev;
printf («% d извлечено из стека% d в% d \ n», значение, стека, индекс);
возвращаемое значение;
}

int main () {
толчок (1,1);
толчок (1,2);
толчок (3,3);
толчок (2,4);
поп (3);
поп (3);
толчок (3,3);
толчок (2,3);
}

Answer 5

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

int stackSize = 300;
int indexUsed = 0;
int[] stackPointer = {-1,-1,-1};
StackNode[] buffer = new StackNode[stackSize * 3];

void push(int stackNum, int value) {
    int lastIndex = stackPointer[stackNum];
    stackPointer[stackNum] = indexUsed;
    indexUsed++;
    buffer[stackPointer[stackNum]]=new StackNode(lastIndex,value);
}

int pop(int stackNum) {
    int value = buffer[stackPointer[stackNum]].value;
    int lastIndex = stackPointer[stackNum];
    stackPointer[stackNum] = buffer[stackPointer[stackNum]].previous;
    buffer[lastIndex] = null;
    indexUsed--;
    return value;
}

int peek(int stack) { return buffer[stackPointer[stack]].value; }

boolean isEmpty(int stackNum) { return stackPointer[stackNum] == -1; }

class StackNode {
    public int previous;
    public int value;

    public StackNode(int p, int v){
        value = v;
        previous = p;
    }
}

Answer 6

первый стек растет на 3n, второй стек растет на 3n + 1, третий растет на 3n + 2

для n = {0 ... N}

Answer 7

Еще один подход (в дополнение к связанному списку) заключается в использовании карты стеков. В этом случае вам придется использовать дополнительные биты log (3 ^ n) / log (2) для построения карты распределения данных в вашем массиве n-длины. Каждая часть карты с 3 значениями говорит, какой стек является владельцем следующего элемента. Ex. a.push(1); b.push(2); c.push(3); a.push(4); a.push(5); даст вам изображение

aacba
54321

соответствующее значение карты вычисляется, когда элементы помещаются в стек (со смещением содержимого массива)

map0 = any
map1 = map0*3 + 0
map2 = map1*3 + 1
map3 = map2*3 + 2
map4 = map3*3 + 0
map5 = map4*3 + 0 = any*3^5 + 45

и длина стеков 3,1,1
Как только вы захотите сделать c.pop(), вам придется реорганизовать свои элементы, найдя фактическое положение c.top() в исходном массиве, пройдясь по карте ячеек (т.е. разделите на 3, тогда как mod на 3 не равно 2) и затем сдвиньте все содержимое массива обратно, чтобы закрыть это отверстие. При прохождении карты ячеек вам нужно будет сохранить все пройденные вами позиции (mapX), а после прохождения той, которая указывает на стек "c", вам придется еще раз разделить на 3 и умножить на 3 ^ (количество пройденных позиций -1) и добавьте mapX, чтобы получить новое значение ячейки-карты.
Затраты на это фиксированы и зависят от размера элемента стека (bits_per_value):
(log (3 n) / log (2)) / (n log (bits_per_value) / log (2)) = log (3 n) / (n log (bits_per_value) ) = log (3) / log (bits_per_value)
Таким образом, для bits_per_value = 32 это будет пространство на 31,7% больше, а с ростом bits_per_value оно будет уменьшаться (то есть для 64 битов это будет 26,4%).