top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

How can we implement two stack in an array?

+1 vote
64 views
How can we implement two stack in an array?
posted Aug 11, 2014 by Deepak Negi

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

Just an algo -
1. start two stacks from two extreme corners of array.
2. stack1 starts from the leftmost element, the first element in stack1 is pushed at index 0.
3. stack2 starts from the rightmost corner, the first element in stack2 is pushed at index (n-1).
4. Both stacks grow (or shrink) in opposite direction.

How to check overflow
Check space between top elements of the two stacks.

answer Aug 12, 2014 by Salil Agrawal
Implemented your algo :)
#include<iostream>
#include<stdlib.h>
 
using namespace std;
 
class twoStacks
{
    int *array;
    int size;
    int top_stack1, top_stack2;

public:
   twoStacks(int n)  
   {
       size = n;
       array = new int[n];
       top_stack1 = -1;
       top_stack2 = size;
   }
 
   void push1(int x)
   {
       // check for one empty space
       if (top_stack1 < top_stack2 - 1)
       {
           top_stack1++;
           array[top_stack1] = x;
       }
       else
       {
           cout << "Overflow";
           exit(1);
       }
   }
 
   void push2(int x)
   {
       // check for one empty space
       if (top_stack1 < top_stack2 - 1)
       {
           top_stack2--;
           array[top_stack2] = x;
       }
       else
       {
           cout << "Overflow";
           exit(1);
       }
   }
 
   int pop1()
   {
       if (top_stack1 >= 0 )
       {
          int x = array[top_stack1];
          top_stack1--;
          return x;
       }
       else
       {
           cout << "Underflow";
           exit(1);
       }
   }
 
   int pop2()
   {
       if (top_stack2 < size)
       {
          int x = array[top_stack2];
          top_stack2++;
          return x;
       }
       else
       {
           cout << "Underflow";
           exit(1);
       }
   }
};
Similar Questions
+3 votes

How can we implement an LRU cache using just a single container i.e. map or unordered_map?

Expected operations:
1. find(key_t) - find a certain value in cache
2. insert(key_t, value_t) - insert a new value to the cache

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...