Take the 2-minute tour ×

I came across this problem in an interview website. The problem asks for efficiently implement three stacks in a single array, such that no stack overflows until there is no space left in the entire array space.

For implementing 2 stacks in an array, it's pretty obvious: 1st stack grows from LEFT to RIGHT, and 2nd stack grows from RIGHT to LEFT; and when the stackTopIndex crosses, it signals an overflow.

Thanks in advance for your insightful answer.

share|improve this question
Ah, this is a very well studied problem of the '70ies (or maybe earlier than that). Trying to recall where I first saw this. Knuth? Sedgewick? Standish? Hmm... I think Knuth in particular mentioned a trick/heuristic to favor the faster growing stack (of N stacks, 3 in your case), but can't readily remember :) –  Dimitris Andreou Jun 19 '10 at 23:51
Ah, found it, adding it as an answer below. –  Dimitris Andreou Jun 20 '10 at 0:28
whats the application of doing 3 stacks in single array? real need? –  Dineshkumar Jun 5 '13 at 9:04
@Dineshkumar Locality of reference. If we take three separate stacks, their memory will be allocated at different places, so they might not be in physical memory (RAM) at the same time. And, we might have page miss.. and will need to bring the new stack from disk to RAM. Whereas, in the case of 3 stack as one array implementation, most likely, all stacks will be on a single page, and all the stacks will be in RAM, even if only one stack is more frequently used, and others are used less often. –  superuser Apr 6 at 14:42

15 Answers 15

You can implement three stacks with a linked list:

  • You need a pointer pointing to the next free element. Three more pointers return the last element of each stack (or null, if the stack is empty).
  • When a stack gets another element added, it has to use the first free element and set the free pointer to the next free element (or an overflow error will be raised). Its own pointer has to point to the new element, from there back to the next element in the stack.
  • When a stack gets an element removed it will hand it back into the list of free elements. The own pointer of the stack will be redirected to the next element in the stack.

A linked list can be implemented within an array.

How (space) efficent is this?
It is no problem to build a linked list by using two cells of an array for each list element (value + pointer). Depending on the specification you could even get pointer and value into one array element (e.g. the array is long, value and pointer are only int).
Compare this to the solution of kgiannakakis ... where you lose up to 50% (only in the worst case). But I think that my solution is a bit cleaner (and maybe more academic, which should be no disadvantage for an interview question ^^).

share|improve this answer
You can point stacks to "null"-indexes and have pointer to first free element in sequence of chained free elements. Each time you push to stack you get that element from sequence of free elements and changes next pointer of it to old stack-top. When element is popped out of stack it returns to head of free sequence. And kgiannakakis wastes up to 50% and your variant spends 50% always for pointer. –  ony Jun 17 '10 at 9:49
The question doesn't say what type the array is or the values you need to store. If you assumed your stack has to store 32-bit numbers and you create an array of 64-bit numbers you could easily pack the linked-list pointers into the upper/lower bits of each array value. –  Paolo Jun 17 '10 at 10:04
@Paolo: yes it depends on the specification - you always need some space for your pointers. But my point is that a doubly-linked list is basically an adequate data structure for this problem. You you use it the implementation isn't difficult anymore. –  tanascius Jun 17 '10 at 10:17
@tanascius Why the "double" links? A stack is always traversed in the same direction ... –  belisarius Jun 17 '10 at 14:10
@belisarius: You are right. The idea is to use a 4th pointer for a list of free elements. I updated my answer ... ^^ thx –  tanascius Jun 17 '10 at 15:00

First stack grows from left to right.

Second stack grows from right to left.

Third stack starts from the middle. Suppose odd sized array for simplicity. Then third stack grows like this:

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

First and second stacks are allowed to grow maximum at the half size of array. The third stack can grow to fill in the whole array at a maximum.

Worst case scenario is when one of the first two arrays grows at 50% of the array. Then there is a 50% waste of the array. To optimise the efficiency the third array must be selected to be the one that grows quicker than the other two.

share|improve this answer
But that does not fit the requirements. Put in one element for the 3rd stack, then only elements for the 1st stack ... how will your solution handle that? –  tanascius Jun 17 '10 at 8:46
But suppose 1st stack has 1 entry, 2nd stack has 4 entries. Where do you put 3rd stack's 4th entry? –  Chowlett Jun 17 '10 at 8:46
Both of you are right. My solution can waste up to 50%. I will be interested to see if anyone can offer a better solution. –  kgiannakakis Jun 17 '10 at 8:54
I wanted to mention this approach in my initial post. But as the author pointed that it could waste 50% space in the worst case. –  user369070 Jun 19 '10 at 8:13

See Knuth, The Art of Computer Programming, Volume 1, Section 2.2.2. titled "Sequential allocation". Discusses allocating multiple queues/stacks in a single array, with algorithms dealing with overflows, etc.

share|improve this answer
Heh, whoever downvoted Knuth's reference, don't be ashamed, reveal yourself :) –  Dimitris Andreou Aug 6 '10 at 14:05
By the way, the best answers given are already subsumed in Knuth's much more thorough treatment of this problem. Just sayin'. –  Dimitris Andreou Aug 6 '10 at 14:08
Perhaps that person was not downvoting Knuth, but an answer that is basically useless if you do not already have the book at home (in which case you would not be interested in the question in the first place, I guess). –  Pascal Cuoq Sep 19 '10 at 15:45
How about libraries. I can't remember the last time when I lived at a place without a library having Knuth in it. –  Dimitris Andreou Sep 20 '10 at 13:44
Hi, do you mind posting the part talking about that ? At least the idea of it –  warl0ck Jul 27 '12 at 14:36

We can use long bit array representing to which stack the i-th array cell belongs to. We can take values by modulo 3 (00 - empty, 01 - A, 10 - B, 11 - C). It would take N/2 bits or N/4 bytes of additional memory for N sized array.

For example for 1024 long int elements (4096 bytes) it would take only 256 bytes or 6%.

This bit array map can be placed in the same array at the beginning or at the end, just shrinking the size of the given array by constant 6%!

share|improve this answer
I really like this idea; I think it's the most optimal use of memory-space. In terms of speed, the drawback is that a push() or pop() operation on any stack is no longer O(1), but can be O(N) in the worst case. Still, very nice! –  Ciaran Oct 10 '12 at 23:33
Should that read "N*2 bits or N/4 bytes"? –  Ciaran Oct 10 '12 at 23:34

This is an interesting conundrum, and I don't have a real answer but thinking slightly outside the box...

it could depend on what each element in the stack consists of. If it's three stacks of true/false flags, then you could use the first three bits of integer elements. Ie. bit 0 is the value for the first stack, bit 1 is the value for the second stack, bit 2 is the value for the third stack. Then each stack can grow independently until the whole array is full for that stack. This is even better as the other stacks can also continue to grow even when the first stack is full.

I know this is cheating a bit and doesn't really answer the question but it does work for a very specific case and no entries in the stack are wasted. I am watching with interest to see whether anyone can come up with a proper answer that works for more generic elements.

share|improve this answer
You'll have waste of bit-sized elements instead of waste of any-sized elements. That's variant of splitting array in 3 parts but in this case with using interleaving. –  ony Jun 17 '10 at 9:35
True and well spotted, so back to the think-tank. As Damien said, it depends on whether all array positions should be used to store values. If so, then the doubly-linked-list method (which is probably the correct answer, from an interview POV) can't be used. In this case kgiannakakis answer is probably ok, but obviously wastes up to 50% of the space. We're still waiting for a definitive answer that uses every element for a value and doesn't waste any space. Damien's does, but would be difficult to maintain order of the stack when moving from one end of the middle stack to the other. –  giles123 Jun 17 '10 at 9:58

Split array in any 3 parts (no matter if you'll split it sequentially or interleaved). If one stack grows greater than 1/3 of array you start filling ends of rest two stacks from the end.

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

The worse case is when two stacks grows up to 1/3 boundary and then you have 30% of space waste.

share|improve this answer
I couldn't grasp your idea completely. Did you mean, when first stack (marked with 'aaa') is filled up, say from LEFT to RIGHT, you'll insert elements in second stack space (marked with 'bbb') from RIGHT to LEFT. Similarly for second stack, you'll use third stack's space (marked with 'ccc'); and for third stack you'll use first stack's space. I believe it works with the penalty of 1/3rd space wastage. –  user369070 Jun 19 '10 at 8:26
When "aaa" is filled completely from LEFT to RIGHT it starts filling "bbb" and "ccc" simultaneously (odd element goes to one stack and even to other) from RIGHT to LEFT until it will met one of their top. I.e. length of stack for "aaa" is (n + (n- max (top("bbb"), top("ccc"))). When you hit problem with adding another element to stack "aaa" that means that array for "bbb" or for "ccc" is filled completely. So if all stacks grows with the same speed or one stack grows with speed 2x or two with 0x than no space is wasted. If there is one stack 2x and other 0x - you'll get (1/3)/2 space wasted. –  ony Jun 19 '10 at 10:06

Assuming that all array positions should be used to store values - I guess it depends on your definition of efficiency.

If you do the two stack solution, place the third stack somewhere in the middle, and track both its bottom and top, then most operations will continue to be efficient, at a penalty of an expensive Move operation (of the third stack towards wherever free space remains, moving to the half way point of free space) whenever a collision occurs.

It's certainly going to be quick to code and understand. What are our efficiency targets?

share|improve this answer

first stack grows at 3n, second stack grows at 3n+1, third grows at 3n+2

for n={0...N}

share|improve this answer
You divide the array just in three parts ... what happens when only the 1st stack grows all the time? –  tanascius Jun 17 '10 at 8:47
Doesn't fit requirements. Once the first stack has 1/3 as many entries as the array length, it overflows regardless of whether there's space in the array allotted for stacks 2 and 3. –  Chowlett Jun 17 '10 at 8:47
It might waste 2/3rd space in worst case. –  user369070 Jun 19 '10 at 8:15

Yet another approach (as additional to linked-list) is to use map of stacks. In that case you'll have to use additional log(3^n)/log(2) bits for building map of data distribution in your n-length array. Each of 3-value part of map says which stack is owns next element. Ex. a.push(1); b.push(2); c.push(3); a.push(4); a.push(5); will give you image


appropriate value of map is calculated while elements is pushed onto stack (with shifting contents of array)

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

and length of stacks 3,1,1
Once you'll want to do c.pop() you'll have to reorganize your elements by finding actual position of c.top() in original array through walking in cell-map (i.e. divide by 3 while mod by 3 isn't 2) and then shift all contents in array back to cover that hole. While walking through cell-map you'll have to store all position you have passed (mapX) and after passing that one which points to stack "c" you'll have to divide by 3 yet another time and multiply it by 3^(amount positions passed-1) and add mapX to get new value of cells-map.
Overhead for that fixed and depends on size of stack element (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)
So for bits_per_value = 32 it will be 31.7% space overhead and with growing bits_per_value it will decay (i.e. for 64 bits it will be 26.4%).

share|improve this answer

In this approach, any stack can grow as long as there is any free space in the array. We sequentially allocate space to the stacks and we link new blocks to the previous block. This means any new element in a stack keeps a pointer to the previous top element of that particular stack.

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;
    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;
    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;
share|improve this answer

This code implements 3 stacks in single array. It takes care of empty spaces and fills the empty spaces in between the data.

#include <stdio.h>

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];
   } else {
     index = stackindex;
   stacklist[index].value = value;
   if(top[stackno-1] != -1) {
     stacklist[index].prev = top[stackno-1];
   } else {
     stacklist[index].prev = -1;
   top[stackno-1] = index;
   printf("%d is pushed in stack %d at %d\n", value, stackno, index);

int pop(int stackno) {
   int index, value;
   if(top[stackno-1] == -1) {
     printf("No elements in the stack %d\n", value, stackno);
     return -1;
   index = top[stackno-1];
   freelist[freeindex] = index;
   value = stacklist[index].value;
   top[stackno-1] = stacklist[index].prev;
   printf("%d is popped put from stack %d at %d\n", value, stackno, index);
   return value;

int main() {

share|improve this answer

Another solution in PYTHON, please let me know if that works as what you think.

    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)
            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]
            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

print 'After pop out: '
for i, elm in enumerate(s.stack):
share|improve this answer

A rather silly but effective solution could be:

  • Store the first stack elements at i*3 positions: 0,3,6,...
  • Store the second stack elements at i*3+1 positions: 1,4,7...
  • And third stack elements at i*3+2 positions.

The problem with this solution is that the used memory will be always three times the size of the deepest stack and that you can overflow even when there are available positions at the array.

share|improve this answer

May be this can help you a bit...i wrote it by myself :)

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

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

     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;


void CStack::push(int8_t data)
     if(stack3_cursize != FULL) 
          array[stack3_range[LOWER] + stack3_curpos--] = data;
     } else if(stack2_cursize != FULL) {
          array[stack2_range[LOWER] + stack2_curpos--] = data;
     } else if(stack1_cursize != FULL) {   
          array[stack1_range[LOWER] + stack1_curpos--] = data;
     } 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; 
     } else if(stack2_cursize < stack2_size) {
          array[stack2_range[LOWER] + ++stack2_curpos] = 0;
     } else if(stack3_cursize < stack3_size) {
          array[stack3_range[LOWER] + ++stack3_curpos] = 0;
     } 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++)
     for(int8_t i = stack3_range[LOWER] + stack3_curpos + 1; i <=  stack3_range[UPPER]; i++)

int main()
     CStack stack;

     std::cout<<"adding: ";
     for(uint8_t i = 1; i < 10; i++) 
          std::cout<<" "<<static_cast<int>(i);




     return 0;

share|improve this answer

This problem can be solved by partitioning array for any given stack size 'N'.

  1. For given stack count determine start/top count for every stack.
  2. Determine maximum value every stack can reach.
  3. While pushing element on a particular stack use it'sown top and max value to determine the push location as well as check is stack is full.
  4. While poping out element from particular stck use max/top values for that stack and update the same as well as check if stack is empty.

The java code answer for this problem can be fond here, http://programmingpassionforjava.blogspot.com/2012/10/efficiently-implement-3-stacks-in.html

share|improve this answer

Your Answer


