How to implement 3 stacks with one array?
Space (not time) efficient. You could:
1) Define two stacks beginning at the array endpoints and growing in opposite directions.
2) Define the third stack as starting in the middle and growing in any direction you want.
3) Redefine the Push op, so that when the operation is going to overwrite other stack, you shift the whole middle stack in the opposite direction before Pushing.
You need to store the stack top for the first two stacks, and the beginning and end of the third stack in some structure.
Edit
Above you may see an example. The shifting is done with an equal space partitioning policy, although other strategies could be chosen depending upon your problem heuristics.
Edit
Following @ruslik's suggestion, the middle stack could be implemented using an alternating sequence for subsequent pushes. The resulting stack structure will be something like:
| Elem 6 | Elem 4 | Elem 2 | Elem 0 | Elem 1 | Elem 3 | Elem 5 |
In this case, you'll need to store the number n of elements on the middle stack and use the function:
f[n_] := 1/4 ( (-1)^n (-1 + 2 n) + 1) + BS3
to know the next array element to use for this stack.
Although probably this will lead to less shifting, the implementation is not homogeneous for the three stacks, and inhomogeneity (you know) leads to special cases, more bugs and difficulties to maintain code.
As long as you try to arrange all items from one stack together at one "end" of the array, you're lacking space for the third stack.
However, you could "intersperse" the stack elements. Elements of the first stack are at indices i * 3, elements of the second stack are at indices i * 3 + 1, elements of the third stack are at indices i * 3 + 2 (where i is an integer).
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
| A1 : B1 : C1 | A2 : B2 : C2 | : B3 | C3 | : B4 : | :
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
^ ^ ^
A´s top C´s top B´s top
Of course, this scheme is going to waste space, especially when the stacks have unequal sizes. You could create arbitrarily complex schemes similar to the one described above, but without knowing any more constraints for the posed question, I'll stop here.
Update:
Due to the comments below, which do have a very good point, it should be added that interspersing is not necessary, and may even degrade performance when compared to a much simpler memory layout such as the following:
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
| A1 : A2 : : : | B1 : B2 : B3 : B4 : | C1 : C2 : C3 :
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
^ ^ ^
A´s top B´s top C´s top
i.e. giving each stack it's own contiguous block of memory. If the real question is indeed to how to make the best possible use of a fixed amount of memory, in order to not limit each stack more than necessary, then my answer isn't going to be very helpful.
In that case, I'd go with @belisarius' answer: One stack goes to the "bottom" end of the memory area, growing "upwards"; another stack goes to the "top" end of the memory area, growing "downwards", and one stack is in the middle that grows in any direction but is able to move when it gets too close to one of the other stacks.
Maintain a single arena for all three stacks. Each element pushed onto the stack has a backwards pointer to its previous element. The bottom of each stack has a pointer to NULL/None.
The arena maintains a pointer to the next item in the free space. A push adds this element to the respective stack and marks it as no longer in the free space. A pop removes the element from the respective stack and adds it to the free list.
From this sketch, elements in stacks need a reverse pointer and space for the data. Elements in the free space need two pointers, so the free space is implemented as a doubly linked list.
The object containing the three stacks needs a pointer to the top of each stack plus a pointer to the head of the free list.
This data structure uses all the space and pushes and pops in constant time. There is overhead of a single pointer for all data elements in a stack and the free list elements use the maximum of (two pointers, one pointer + one element).
Later: python code goes something like this. Note use of integer indexes as pointers.
class StackContainer(object):
def __init__(self, stack_count=3, size=256):
self.stack_count = stack_count
self.stack_top = [None] * stack_count
self.size = size
# Create arena of doubly linked list
self.arena = [{'prev': x-1, 'next': x+1} for x in range(self.size)]
self.arena[0]['prev'] = None
self.arena[self.size-1]['next'] = None
self.arena_head = 0
def _allocate(self):
new_pos = self.arena_head
free = self.arena[new_pos]
next = free['next']
if next:
self.arena[next]['prev'] = None
self.arena_head = next
else:
self.arena_head = None
return new_pos
def _dump(self, stack_num):
assert 0 <= stack_num < self.stack_count
curr = self.stack_top[stack_num]
while curr is not None:
d = self.arena[curr]
print '\t', curr, d
curr = d['prev']
def _dump_all(self):
print '-' * 30
for i in range(self.stack_count):
print "Stack %d" % i
self._dump(i)
def _dump_arena(self):
print "Dump arena"
curr = self.arena_head
while curr is not None:
d = self.arena[curr]
print '\t', d
curr = d['next']
def push(self, stack_num, value):
assert 0 <= stack_num < self.stack_count
# Find space in arena for new value, update pointers
new_pos = self._allocate()
# Put value-to-push into a stack element
d = {'value': value, 'prev': self.stack_top[stack_num], 'pos': new_pos}
self.arena[new_pos] = d
self.stack_top[stack_num] = new_pos
def pop(self, stack_num):
assert 0 <= stack_num < self.stack_count
top = self.stack_top[stack_num]
d = self.arena[top]
assert d['pos'] == top
self.stack_top[stack_num] = d['prev']
arena_elem = {'prev': None, 'next': self.arena_head}
# Link the current head to the new head
head = self.arena[self.arena_head]
head['prev'] = top
# Set the curr_pos to be the new head
self.arena[top] = arena_elem
self.arena_head = top
return d['value']
if __name__ == '__main__':
sc = StackContainer(3, 10)
sc._dump_arena()
sc.push(0, 'First')
sc._dump_all()
sc.push(0, 'Second')
sc.push(0, 'Third')
sc._dump_all()
sc.push(1, 'Fourth')
sc._dump_all()
print sc.pop(0)
sc._dump_all()
print sc.pop(1)
sc._dump_all()
I have a solution for this question. The following program makes the best use of the array (in my case, an array of StackNode Objects). Let me know if you guys have any questions about this. [It's pretty late out here, so i didn't bother to document the code - I know, I should :) ]
public class StackNode {
int value;
int prev;
StackNode(int value, int prev) {
this.value = value;
this.prev = prev;
}
}
public class StackMFromArray {
private StackNode[] stackNodes = null;
private static int CAPACITY = 10;
private int freeListTop = 0;
private int size = 0;
private int[] stackPointers = { -1, -1, -1 };
StackMFromArray() {
stackNodes = new StackNode[CAPACITY];
initFreeList();
}
private void initFreeList() {
for (int i = 0; i < CAPACITY; i++) {
stackNodes[i] = new StackNode(0, i + 1);
}
}
public void push(int stackNum, int value) throws Exception {
int freeIndex;
int currentStackTop = stackPointers[stackNum - 1];
freeIndex = getFreeNodeIndex();
StackNode n = stackNodes[freeIndex];
n.prev = currentStackTop;
n.value = value;
stackPointers[stackNum - 1] = freeIndex;
}
public StackNode pop(int stackNum) throws Exception {
int currentStackTop = stackPointers[stackNum - 1];
if (currentStackTop == -1) {
throw new Exception("UNDERFLOW");
}
StackNode temp = stackNodes[currentStackTop];
stackPointers[stackNum - 1] = temp.prev;
freeStackNode(currentStackTop);
return temp;
}
private int getFreeNodeIndex() throws Exception {
int temp = freeListTop;
if (size >= CAPACITY)
throw new Exception("OVERFLOW");
freeListTop = stackNodes[temp].prev;
size++;
return temp;
}
private void freeStackNode(int index) {
stackNodes[index].prev = freeListTop;
freeListTop = index;
size--;
}
public static void main(String args[]) {
// Test Driver
StackMFromArray mulStack = new StackMFromArray();
try {
mulStack.push(1, 11);
mulStack.push(1, 12);
mulStack.push(2, 21);
mulStack.push(3, 31);
mulStack.push(3, 32);
mulStack.push(2, 22);
mulStack.push(1, 13);
StackNode node = mulStack.pop(1);
node = mulStack.pop(1);
System.out.println(node.value);
mulStack.push(1, 13);
} catch (Exception e) {
e.printStackTrace();
}
}
}