Implement Two stacks using one array

Problem: How to implement/code two stacks using one array.

Solution: The obvious solution is to have the two stacks at the two ends of the array. The stacks will grow in opposite direction. When the two stacks collide and there is no more room in the array the stacks will over flow. This problem is probably one of the easier problems and targeted towards exercising your array index manipulation skills. See the figure below for a visual representation of the two stacks in the array.



Code (C#):
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Array2Stacks
{
    /// 
    /// DualStack class implements 2 stacks in a single array.
    /// Stack A starts on the right and increases towards the left
    /// Stack B starts on the left and increases towards the right
    /// When both stacks meet there is no more room for adding items
    /// The cool thing about the dual stack is that both stacks share the
    /// same array with built in collision detection. If one stack was empty
    /// the other stack can potentially use the entire array.
    /// 
    public class DualStack
    {
        int size = 50; //default array size
        int stackATop = -1;
        int stackBTop = 50;

        public DualStack(int size)
        {
            this.size = size;
            array = new object[this.size];
            stackBTop = size;
        }

        //one array to hold the two stacks
        object[] array = null;
 
        //pushes an item on stack A
        public bool PushStackA(object obj)
        {
            if (stackATop < stackBTop - 1) //we have at least one empty slot in the array
            {
                array[++stackATop] = obj;
                return true;
            }
            else
            {
                //return false if stack is full
                return false;   
            }
        }

        //pops an item from stack A
        public object PopStackA()
        {
            if (stackATop >= 0 && stackATop < stackBTop)
            {
                //take the element at the top of the stack
                object obj = array[stackATop]; 
                stackATop--;//decrement stack top pointer
                return obj;
            }
            return null;
        }

        /// pushes an item on stack B
        public bool PushStackB(object obj)
        {
            if (stackBTop > stackATop + 1) //we have at least one empty slot between the stacks
            {
                array[--stackBTop] = obj;
                return true;
            }
            else
            {
                //stack is full
                return false;
            }
        }

        public object PopStackB()
        {

            if (stackBTop < this.size && stackBTop > stackATop) //stack is not empty
            {
                object obj = array[stackBTop];
                stackBTop++;
                return obj;
            }
            else
            {   //stack is empty
                return null;
            }
        }
    }
}

10 comments:

  1. Helped me a lot..Thanx :)

    ReplyDelete
  2. what are the advantages and disadvantages of implementing 2 or n stacks using single array?

    ReplyDelete
  3. Savitha,
    The advantage is you can get by with a single buffer (save memory). This is true only if only one of the stacks is bigger than the other and you don't know the potential sizes of the stacks. This is how stack and heap are laid out for an operating system process. They both grow towards each other.

    The disadvantage is it complicates things a big since you have to make sure you handle the case when the two stack meet. You don't want them to overwrite each others data.

    ReplyDelete
  4. actually my instructor asked me this following question , can u pls help me out in understanding this concept
    can many stacks be implemented using 1 push and 1 pop?
    can it be of different of different size? if NO what modification has to be done to make it YES?

    ReplyDelete
  5. need to implement it using C programme.

    ReplyDelete
  6. In implement two stacks in one array push is very easy. but pop is difficult.

    ReplyDelete
  7. In the popStackA() operation, isn't it enough if we check stackATop >= 0 alone.
    Why do we bother whether stackATop < stackBTop too?

    ReplyDelete
  8. >> In the popStackA() operation, isn't it enough if we check stackATop >= 0 alone.
    Why do we bother whether stackATop < stackBTop too?

    I agree

    ReplyDelete
  9. I think there is no need of stackATop < stackBTop this condition in pop to stack
    and similarly for stackb...

    ReplyDelete