Related: Implement k stacks in a single array
Problem 2: How can you implement n (n > 2) stacks in a single array, where no stack overflows until no space left in the entire array space?
We may implement the array like a list, where each item in the array has a link to another item. When an item has not been occupied by any stacks and it is available, it is linked to the next available item. When an item is pushed into a stack, it is linked to the previous item in the stack.
Problem 2: How can you implement n (n > 2) stacks in a single array, where no stack overflows until no space left in the entire array space?
We may implement the array like a list, where each item in the array has a link to another item. When an item has not been occupied by any stacks and it is available, it is linked to the next available item. When an item is pushed into a stack, it is linked to the previous item in the stack.
template <typename T, int capacity, int count> class Stacks
{
public:
Stacks()
{
int i;
for(i = 0; i < capacity - 1; ++i)
items[i].link = i + 1;
items[i].link = -1;
emptyHead = 0;
for(i = 0; i < count; ++i)
stackHead[i] = -1;
}
T top(int stackIndex)
{
validateIndex(stackIndex);
if(empty(stackIndex))
throw new exception("The stack is empty.");
return items[stackHead[stackIndex]].data;
}
void push(int stackIndex, const T& item)
{
validateIndex(stackIndex);
if(full())
throw new exception("All space has been occupied.");
Item<T>& block = items[emptyHead];
int nextEmpty = block.link;
block.data = item;
block.link = stackHead[stackIndex];
stackHead[stackIndex] = emptyHead;
emptyHead = nextEmpty;
}
void pop(int stackIndex)
{
validateIndex(stackIndex);
if(empty(stackIndex))
throw new exception("The stack is empty.");
Item<T>& block = items[stackHead[stackIndex]];
int nextItem = block.link;
block.link = emptyHead;
emptyHead = stackHead[stackIndex];
stackHead[stackIndex] = nextItem;emptyHead = stackHead[stackIndex];
}
bool empty(int stackIndex)
{
return (stackHead[stackIndex] < 0);
}
private:
void validateIndex(int stackIndex)
{
if(stackIndex < 0 || stackIndex >= count)
throw new exception("Invalid index of stack.");
}
bool full()
{
return (emptyHead < 0);
}
private:
template <typename T> struct Item
{
T data;
int link;
};
private:
Item<T> items[capacity];
int emptyHead;
int stackHead[count];
}
Problem 1: How can you implement two stacks in a single array, where no stack overflows until no space left in the entire array space?
template <typename T, int capacity> class TwoStacks
{
public:
TwoStacks()
{
topFirst = -1;
topSecond = capacity;
}
T top(int stackIndex)
{
validateIndex(stackIndex);
if(empty(stackIndex))
throw new exception("The stack is empty.");
if(stackIndex == 0)
return items[topFirst];
return items[topSecond];
}
void push(int stackIndex, T item)
{
validateIndex(stackIndex);
if(full())
throw new exception("All space has been occupied.");
if(stackIndex == 0)
items[++topFirst] = item;
else
items[--topSecond] = item;
}
void pop(int stackIndex)
{
validateIndex(stackIndex);
if(empty(stackIndex))
throw new exception("The stack is empty.");
if(stackIndex == 0)
--topFirst;
else
++topSecond;
}
bool empty(int stackIndex)
{
if(stackIndex == 0 && topFirst == -1)
return true;
if(stackIndex == 1 && topSecond == capacity)
return true;
return false;
}
private:
bool full()
{
return (topFirst >= topSecond - 1);
}
void validateIndex(int stackIndex)
{
if(stackIndex < 0 || stackIndex > 1)
throw new exception("Invalid Stack Index.");
}
private:
T items[capacity];
int topFirst;
int topSecond;
};
Read full article from Coding Interview Questions: No. 39 - Stacks Sharing an Array