如何使用單個陣列實現三個堆棧

Question

我在採訪網站中遇到了這個問題。該問題要求在單個陣列中有效實施三個堆棧，以便在整個陣列空間中沒有剩餘空間的情況下不會發生堆棧溢出。爲了在一個數組中實現2個堆棧，這是非常明顯的：第一個堆棧從LEFT增長到RIGHT，第二個堆棧從RIGHT增長到LEFT;當stackTopIndex交叉時，它表示溢出。

在此先感謝您的深刻解答。

Answer 1

第一堆棧從左向右增長。

第二堆棧從右向左增長。

第三堆棧從中間開始。爲簡單起見，假設奇數大小的數組。然後第三堆棧像這樣增長：

* * * * * * * * * * * 
     5 3 1 2 4 

允許第一和第二堆棧在陣列的一半大小處增長最大值。第三個堆棧可以增長以最大限度地填充整個陣列。

最糟糕的情況是當前兩個數組中的一個增長到數組的50％時。然後陣列有50％的浪費。爲了優化效率，第三個陣列必須選擇成比另外兩個快速增長的那個。

Answer 2

第一疊層生長在3N， 第二疊層生長在3N + 1，第三 生長在3N + 2

對於n = {0 ... N}

Answer 3

可以實現三個堆塊與a linked list：

• 您需要一個指向下一個空閒元素的指針。三個指針返回每個堆棧的最後一個元素（如果堆棧爲空，則返回null）。
• 當堆棧獲取另一個元素時，它必須使用第一個空閒元素並將空閒指針設置爲下一個空閒元素（否則將引發溢出錯誤）。它自己的指針必須指向新的元素，從那裏回到堆棧中的下一個元素。
• 當一個堆棧獲取一個元素時，它將把它交回到空閒元素列表中。堆棧自己的指針將被重定向到堆棧中的下一個元素。

甲鏈表可以在陣列內來實現。

如何（空間）efficent是這樣嗎？
通過爲每個列表元素（值+指針）使用數組的兩個單元格構建鏈接列表是沒有問題的。根據規範，你甚至可以將指針和值放入一個數組元素中（例如數組很長，值和指針只是int）。
將此與kgiannakakis的解決方案進行比較...您將損失高達50％（僅在最差情況下）。但我認爲我的解決方案有點乾淨（也許更多學術，這應該是面試問題^^沒有缺點）。

Answer 4

這是一個有趣的難題，我沒有一個真正的答案，但稍微考慮了一下......

它可能取決於堆棧中每個元素的組成。如果它是三堆真/假標誌，那麼你可以使用整數元素的前三位。 IE瀏覽器。位0是第一個堆棧的值，位1是第二個堆棧的值，位2是第三個堆棧的值。然後，每個堆棧可以獨立增長，直到整個陣列滿了堆棧。這甚至更好，因爲即使第一個堆棧已滿，其他堆棧也可以繼續增長。

我知道這有點欺騙，並沒有真正回答這個問題，但它確實適用於一個非常特殊的情況，並且棧中沒有條目被浪費。我正在有興趣地觀察，看看是否有人能夠提出適用於更通用元素的正確答案。

Answer 5

假設所有的陣列位置應該用來存儲值 - 我想這取決於您的效率定義。

如果你做了兩個堆棧解決方案，把第三個堆棧放在中間的某個地方，並且跟蹤它的底部和頂部，那麼大多數操作將繼續保持高效，而犧牲昂貴的Move操作（第三個堆棧朝向剩餘空間的地方，移動到自由空間的中間點），每當碰撞發生時。

它的編碼和理解確實很快。我們的效率目標是什麼？

Answer 6

在任何3個部分拆分數組（無論您是按順序還是交錯分割）。如果一個堆棧增長超過數組的三分之一，則從頭開始填充其餘兩個堆棧的結尾。

 
aaa bbb ccc 
1 2 3 
145 2 3 
145 2 6 3 
145 2 6 3 7 
145 286 3 7 
145 286 397 

最糟糕的情況是，當兩個堆棧增長到1/3的邊界，然後你有30％的空間浪費。

Answer 7

另一種方法（作爲鏈表的補充）是使用堆棧圖。在這種情況下，您必須使用額外的日誌（3^n）/ log（2）位來構建n長度數組中的數據分佈圖。地圖的3值部分的每一部分表示哪個堆棧擁有下一個元素。例如， 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()的實際位置，通過在cell-map中行走（即除以3而mod由3不是2），然後將所有內容陣列回來覆蓋那個洞。在通過單元格映射時，您必須存儲您已經通過的所有位置（mapX），並且在通過指向堆棧「c」的那個位置之後，必須再劃分3次並乘以3 ^（通過金額頭寸-1）並添加mapX以獲取單元格圖的新值。
開銷爲固定，並且取決於堆疊元件（bits_per_value）的大小：
（日誌（3 N）/日誌（2））/（N 日誌（bits_per_value）/日誌（2））=日誌（3 N）/（N日誌（bits_per_value））=日誌（3）/日誌（bits_per_value）
所以對於bits_per_value = 32這將是31.7％的空間開銷，並用生長bits_per_value它會衰減（即，對於64位，這將是26.4 ％）。

Answer 8

參見Knuth, The Art of Computer Programming, Volume 1，第2.2.2節。標題爲「順序分配」。討論在單個陣列中分配多個隊列/堆棧以及處理溢出的算法等。

Answer 9

我們可以使用長位數組來表示第i個數組單元所屬的堆棧。 我們可以通過模3（00 - 空，01 - A，10 - B，11 - C）取值。對於N大小的陣列，需要N/2位或N/4字節的額外內存。

例如，對於1024長的int元素（4096字節），只需要256個字節或6％。

這個位數組映射可以放在開始或結束的同一個數組中，只是將給定數組的大小縮小6％！

Answer 10

在這種方法中，只要數組中有空閒空間，任何堆棧都可以增長。 我們依次爲堆棧分配空間，並將新塊鏈接到前一個塊。這意味着堆棧中的任何新元素都會保留指向該特定堆棧的前一個頂層元素的指針。

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 11

此代碼在單個數組中實現3個堆棧。它處理空白空間並填充數據之間的空白空間。

的#include < stdio.h>中

結構stacknode {
    int值;
    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;
   如果（freeindex> = 0）{
       指數=空閒列表[freeindex];
        freeindex--;
   }否則{
       指數= stackindex;
        stackindex ++;
   }
    stacklist [index] .value = value;
   如果（頂[stackno-1]！= -1）{
        stacklist [指數]。prev = top [stackno-1];
   }否則{
        stacklist [指數] .prev = -1;
   }
    top [stackno-1] = index;
    printf（「％d被壓入堆棧％d在％d \ n」，value，stackno，index）;
}

INT彈出（INT stackno）{
    INT指數值;
   如果（頂[stackno-1] == 1）{
       的printf（ 「在堆棧％d \ N無元件」，值，stackno）;
        return -1;
   }
    index = top [stackno-1];
    freeindex ++;
    freelist [freeindex] = index;
    value = stacklist [index] .value;
    top [stackno-1] = stacklist [index] .prev;
    printf（「％d從堆棧％d中彈出放入％d \ n」，value，stackno，index）;
   返回值;
}

INT主（）{
   推（1,1）;
    push（1,2）;
    push（3,3）;
    push（2,4）;
    pop（3）;
    pop（3）;
    push（3,3）;
    push（2,3）;
}

Answer 12

在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 13

一個相當愚蠢，但有效的解決方案可能是：

• 商店在i*3位置第一個堆棧元素：0,3,6，...
• 商店在i*3+1第二堆棧元素職位：1,4,7 ...
• 第三堆棧元素位於i*3+2位置。

該解決方案的問題是，使用的內存將始終是最深堆棧大小的三倍，即使陣列中存在可用位置，也可能會溢出。

Answer 14

可能這可以幫助你有點...我寫我自己 :)

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

1. 做一個HashMap與鍵在開始和結束位置例如<「B1」，0>，<「E1」，n/3>

2. 對於每個Push（值）添加條件以檢查Bx的位置是否在Ex之前或者是否存在其他「By」之間。 - 讓稱之爲條件（2）

3. 與上面如果考慮， 上述條件（2）爲真//如果B1和E1是爲了 {如果（S1.Push（）），然後E1 ++; else //溢出的條件， {在E2或E3（有空格）的末端開始推動並更新E1爲E2--或E3--; } }

   if if above（2）is false {if（S1.Push（）），then E1 - ; else //溢出的條件， {在E2或E3（有空格）的末端開始推動並更新E1爲E2--或E3--; } }

Answer 16

假設你只有整數索引。如果使用FILO（First In Last Out）進行處理並且不引用單個數據並僅將數組用作數據。使用它的6空間作爲堆棧參考應有助於：

[頭-1，最後-1，頭-2，最後-2，頭部3，最後-3，數據，數據，.. 。，data]

您可以簡單地使用4個空格，因爲head-1 = 0和last-3 =數組長度。如果使用FIFO（先進先出），則需要重新建立索引。

nb：我正在努力提高我的英語水平。