Write a function to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The Push and Pop operations run in O(1) time.
Rationale: The best way to do this is to place the base of the two stacks at an end of the given array and let the first stack ‘grow’ from the left and the right one ‘grow’ from the right. For example, if we had an array of 10 elements available and two stacks, s1={0,1,2} and s2={4,5,6}, the array would look as follows:
A = 0, 1, 2, x, x, x, x, 6, 5, 4
x denotes an unused space. Notice that if s1.length + s2.length > n an overflow will occur. If we store the stacks in this way it will be easy to implement push and pop operations in O(1) for both of them.
Before solving this problem do the following (not limited to):
 Clarify doubts
 Write/loudly speak/analyze single or multiple pseudocode(e.g. trivial algorithm to advanced algorithm/Data Structures) which can lead to solution
 Explain any assumptions or limitations on the written pseudocode
 Mention major data structures to be used
 Also how the positive/negative functional tests prove that the resultant solution is correct.
Clarification Points
Clarification Point1:
Can any stack be empty?
Clarification Point2:
Can we implement separate push / pop operations for the stack?
Pseudo Code
Pseudo code:
Stacks_to_array(s1,s2):
Place elements of s1 from 0 to s1.length in array
Place elements of s2 from Ns2.length to N in array
Assumptions/Limitations
Assumption/Limitation:
 We will implement separate push / pop operations for the two stacks, in O(1)
 The first stack will start from index 0 in the array and ‘grow’ to the right, while the second one will start at index N1 in the same array and ‘grow’ to the left. In this way an overflow would only occur if the sum of the number of elements of the two stacks exceeds the capacity of the array.
Major Data Structures
Major data structures:
Array of Integers
Unit Tests
Unit tests:  
Postive Functional Test cases  
Input  Expected Output 
S1={0,1,2} S2={3,4,5}, N=10  Array={0, 1, 2, 0, 0, 0, 0, 5, 4, 3} 
S1={1}, S2={3}, N=3
S1={1}, S2={3}, N=2 S1={1,2,3}, S2={1,2,3}, N=6

Array={1, 0, 3}
Array={1, 3} Array={1,2,3,3,2,1}

Negative Functional Test Cases  
N1 + N2 > N  Invalid input 
N <= 0  Invalid input 
Here sample answer, which implements the idea defined above. We implement separate push and pop functions for the two array, which both run in O(1). We also test these methods by performing a pop and a push for each stack.
#include <cstdio> #define maxLengthOfArray 10001 using namespace std; void pop1(int &head) { head; } void pop2(int &head) { head++; } void push1(int array[], int &head, int value) { array[++head] = value; } void push2(int array[], int &head, int value) { array[head] = value; } void stacks_to_array(int array[], int lengthOfArray, int s1[], int lengthOfs1, int s2[], int lengthOfs2) { if (lengthOfArray <= 0  lengthOfs1 + lengthOfs2 > lengthOfArray) { printf("Invalid input!\n"); return; } // stack 1 'grows' from 0 for (int index1 = 0; index1 < lengthOfs1; index1++) array[index1] = s1[index1]; int head1 = lengthOfs1  1; // head of stack 1 // stack 2 starts at N1 (the other end of the array) // and grows to the left for (int index2 = 0; index2 < lengthOfs2; index2++) array[lengthOfArray  index2  1] = s2[index2]; int head2 = lengthOfArray  lengthOfs2; // head of stack 2 // we now define the push and pop operations for each stack // all these are O(1) pop1(head1); pop2(head2); push1(array, head1, 10); push2(array, head2, 10); // print contents of stack 1 printf("Stack 1: "); for (int index1 = 0; index1 <= head1; index1++) printf("%d ", array[index1]); printf("\n"); // print contents of stack 2 printf("Stack 2: "); for (int index2 = lengthOfArray  1; index2 >= head2; index2) printf("%d ", array[index2]); printf("\n"); } int main() { int lengthOfArray = 10; int lengthOfs1 = 2, lengthOfs2 = 3; int array[maxLengthOfArray]; int s1[maxLengthOfArray] = {1, 2}, s2[maxLengthOfArray] = {4, 5, 6}; stacks_to_array(array, lengthOfArray, s1, lengthOfs1, s2, lengthOfs2); return 0; }
Output and Further Excercise
Output:  Further exercise: 
N = 10, N1=2, N2=3
S1={1,2} S2={4,5,6} 10 2 1 2 3 4 5 6 Stack 1: 1 10 Stack 2: 4 5 10
(After a pop() and a push(10)) 
Q: Is it possible to store multiple stacks in a single array? How?
A: We could divide the array into more chunks, but chances for an overflow would then increase considerably. Suppose we had an array of 10 and three stacks of 3 elements each.
A = {s11,s12,s13,x,s21,s22,s23,s31,s32,s33} If we perform a push on stack 2, it would clash with the third stack, even though there is one space available, where the element inserted could fit.
