ARRAY : Two Stacks In One Array A[1..N]

0
1900

Two Stacks in One Array HiringLibrary-Com

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. 

Professional Teacher at HiringLibrary.com

Clarification Points 

 

Clarification Point-1:

Can any stack be empty?

Clarification Point-2:

Can we implement separate push / pop operations for the stack?

Diversity in WorkPlace - Japanese,Korea,Chinese

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 N-s2.length to N in array

 

How did you find your first job?

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 N-1 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.

 

Career Summary from a Professional for HiringLibrar

Major Data Structures 

Major data structures:

Array of Integers

Example at Hiring Library

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

Answer of the coding Problem

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 N-1 (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 at HiringLibrary-Com

Output and Further Excercise

Further Exercise at HiringLibrary

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.