How to implement 3 stacks with one array?

Question

Sometimes, I come across the following interview question: How to implement 3 stacks with one array ? Of course, any static allocation is not a solution.

Answer 1

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.

Answer 2

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

Answer 3

A variant on an earlier answer: stack #1 grows from the left, and stack #2 grows from the right.

Stack #3 is in the center, but the elements grow in alternate order to the left and right. If N is the center index, the stack grows as: N, N-1, N+1, N-2, N+2, etc. A simple function converts the stack index to an array index.

Answer 4

Solution: Implementing two stacks is easy. First stack grows from start to end while second one grows from end to start. Overflow for any of them will not happen unless there really is no space left on the array.

For three stacks, following is required: An auxiliary array to maintain the parent for each node. Variables to store the current top of each stack. With these two in place, data from all the stacks can be interspersed in the original array and one can still do push/pop/size operations for all the stacks.

When inserting any element, insert it at the end of all the elements in the normal array. Store current-top of that stack as parent for the new element (in the parents' array) and update current-top to the new position.

When deleting, insert NULL in the stacks array for the deleted element and reset stack-top for that stack to the parent.

When the array is full, it will have some holes corresponding to deleted elements. At this point, either the array can be compacted to bring all free space together or a linear search can be done for free space when inserting new elements.

for further details refer this link:- https://coderworld109.blogspot.in/2017/12/how-to-implement-3-stacks-with-one-array.html

Answer 5

For simplicity if not very efficient memory usage, you could[*] divide the array up into list nodes, add them all to a list of free nodes, and then implement your stacks as linked lists, taking nodes from the free list as required. There's nothing special about the number 3 in this approach, though.

[*] in a low-level language where memory can be used to store pointers, or if the stack elements are of a type such as int that can represent an index into the array.

Answer 6

There are many solutions to this problem already stated on this page. The fundamental questions, IMHO are:

• How long does each push/pop operation take?

• How much space is used? Specifically, what is the smallest number of elements that can be pushed to the three stacks to cause the data structure to run out of space?

As far as I can tell, each solution already posted on this page either can take up to linear time for a push/pop or can run out of space with a linear number of spaces still empty.

In this post, I will reference solutions that perform much better, and I will present the simplest one.

---

In order to describe the solution space more carefully, I will refer to two functions of a data structure in the following way:

A structure that takes O(f(n)) amortized time to perform a push/pop and does not run out of space unless the three stacks hold at least n - O(g(n)) items will be referred to as an (f,g) structure. Smaller f and g are better. Every structure already posted on this page has n for either the time or the space. I will demonstrate a (1,√n) structure.

This is all based on:

• Michael L. Fredman and Deborah L. Goldsmith, "Three Stacks", in Journal of Algorithms, Volume 17, Issue 1, July 1994, Pages 45-70

  • An earlier version appeared in the 29th Annual Symposium on Foundations of Computer Science (FOCS) in 1988

• Deborah Louise Goldsmith's PhD thesis from University of California, San Diego, Department of Electrical Engineering/Computer Science in 1987, "Efficient memory management for >= 3 stacks"

They show, though I will not present, a (log n/log S,S) structure for any S. This is equivalent to a (t, n^1/t) structure for any t. I will show a simplified version that is a (1,√n) structure.

---

Divide the array up into blocks of size Θ(√n). The blocks are numbered from 1 to Θ(√n), and the number of a block is called its "address". An address can be stored in an array slot instead of a real item. An item within a given block can be referred to with a number less than O(√n), and such a number is called an index. An index will also fit in an array slot.

The first block will be set aside for storing addresses and indexes, and no other block will store any addresses or indexes. The first block is called the directory. Every non-directory block will either be empty or hold elements from just one of the three stacks; that is, no block will have two elements from different stacks. Additionally, every stack will have at most one block that is partially filled -- all other blocks associated with a stack will be completely full or completely empty.

As long as there is an empty block, a push operation will be permitted to any stack. Pop operations are always permitted. When a push operation fails, the data structure is full. At that point, the number of slots not containing elements from one of the stacks is at most O(√n): two partially-filled blocks from the stacks not being pushed to, and one directory block.

Every block is ordered so that the elements closer to the front of the block (lower indexes) are closer to the bottom of the stack.

The directory holds:

• Three addresses for the blocks at the top of the three stacks, or 0 if there are no blocks in a particular stack yet

• Three indexes for the element at the top of the three stacks, or 0 if there are no items in a particular stack yet.

• For each full or partially full block, the address of the block lower than it in the same stack, or 0 if it is the lowest block in the stack.

• The address of a free block, called the leader block, or 0 if there are no free blocks

• For each free block, the address of another free block, or 0 if there are no more free blocks

These last two constitute a stack, stored as a singly-linked list, of free blocks. That is, following the addresses of free blocks starting with the leader block will give a path through all the free blocks, ending in a 0.

To push an item onto a stack, find its top block and top element within that block using the directory. If there is room in that block, put the item there and return.

Otherwise, pop the stack of free blocks by changing the address of the leader block to the address of the next free block in the free block stack. Change the address and index for the stack to be the address of the just-popped free block and 1, respectively. Add the item to the just-popped block at index 1, and return.

All operations take O(1) time. Pop is symmetric.