CareerCup

Well, I guess the way I would like to Achieve this is by something like this.
1> Grow First Stack from the array[0].
2> Grow Second Stack from array[n-1].
3> Here Comes the Challenge. For which I may go for something like this.
Initially I assume array[n/2] and the third array and start growing it accordingly. but when I hit the stacktop of third Stack to the stacktop of any of the other stack, I would recalculate the stackbase of the third array and shift all of its allocated value accordinly.

To recalculate the stackbase of third array probably I may use, the stacktop of the array which does not collide to the stackbase of the third array to find the spacing still available in an array and then divide by 2 to make sure I have spaces left for all the three stack to grow again.
Similarly I would think of stackbase of third array to the stacktop of either array and make again adjustments accordingly.
Ofcourse the collision case would create the time complexity JUMP hugely.. coz I need all stack operation working on together again right from the beginning.

0.1) Assume: ThreeWayStack<T> is a single class/interface provides 3 stacks of 'T' in one instance
0.2) Assume: ThreeWayStack.Push(int stackId, T item) - Notice extra 'stackId' param
0.3) Assume: ThreeWayStack.Pop(int stackId) - Notice extra 'stackId' param
0.4) Assume: TWS is short form of ThreeWayStack

1) Define StackItem<T> as { T userItem; int link; }
1.1) Link is used as 'previous' item for stacks
1.2) Link is used as 'next' item for free
1.3) UserItem is actual user item

2) TWS has members as:
2.1) top[3] is an array integers initialized to -1
2.2) items[MAX_SIZE] is an array of StackItem<T> - initialized to item(null, slotId+1)
2.2.1) Ex: items[0] = (null, 1), items[1] = (null, 2)
2.3) free - integer representing the free slot id - initialized to 0

3) None

4) TWS.Push(stackId, item)
4.1) Get free slot id (using member var 'free')
4.2) If free slot can't be found, return stack full error
4.3) Take copy of current 'top' as prevTop, and set top of the stack to this free slot
4.4) Move free slot to next free slot using 'link'
4.5) Update a stack item at top slot with userItem = input item and link = prevTop

5) TWS.Pop(stackId)
5.1) Check if top of the given stack id is < 0; if true, return stack empty error
5.2) Take out the stack item at the top of stack id
5.3) Update top of that stack id to the stack item's 'link' value
5.4) Get stack item's userItem in a local variable, say userItem
5.5) Update stack item, with userItem as null and 'link' as current free slot id
5.6) Update current free slot to this slot id
5.7) Return userItem

Time Complexity: O(1) for push and pop

Thanks,
Laxmi

Could we use some extra spaces to preserve some other information?

I think we can maintain a DOUBLE LINKED LIST
I use nxt[x] to indicates the next node of node x ( if next node is empty, then nxt[x] = -1)
I use pre[x] to indicates the previous node in the Stacks.
In the following code, "cur" is the HeadPoint of the vacant list, and "las" is the last node of the vacant list.

For
(1) push, we simply check whether cur is valid.
(2) pop, we may add one node to the vacant list, we have to note that in this time, the list may be empty.

#include <iostream>
#include <cmath>
#include <cstdio>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <cstring>
#include <sstream>
using namespace std;
 
#define mp make_pair
#define pb push_back
 
typedef double db;
typedef long long LL ;

const int MAXN = 5;
int cur, las;
int arr[ MAXN ];
int pre[ MAXN ];
int nxt[ MAXN ];

struct Stack{
	 int top ;  
	 bool push( int x) {
	 	  if(cur == - 1) return false ; //overflows
  	 	  arr[ cur ] = x;
  	 	  pre[ cur ] = top ;
  	 	  top = cur; cur = nxt[ cur ];
  	 	  return true;
  	 }
  	 void init(){
	 	  top = - 1;
  	 }
  	 bool pop(){
	 	  if(top == -1) return false;
	 	  if(cur == -1) cur = las = top; //the vacant list is empty
	 	  else nxt[ las ] = top,las = top;// otherwise
	      nxt[top]=-1;
	 	  top = pre[ top ];
	 	  return true ;
  	 }
}S[3];

int main(){ 
	for(int i=0;i<MAXN-1;++i) nxt[i]=i+1; nxt[MAXN-1]=-1;
	cur = 0; las = MAXN - 1;
	for(int i = 0; i < 3; ++ i) S[i].init();
	S[0].push( 5 );
    S[0].push( 4 );
	S[1].push( 3 ); 
	S[2].push( 2 );
	S[0].push( 1 ); // {5, 4, 3, 2, 1}
	cout << S[0].push( 7 ) << endl; // FULL
	S[2].pop(); // {5, 4, 3, x, 1}
	cout << S[0].push( 7 ) << endl; //{5,4,3,7,1}
	for(int i=0;i<MAXN;++i) cout << arr[i] <<' '; cout << endl;
	S[1].pop();//{5,4,x,7,1}
	cout << S[2].push(6) << endl;//{5,4,6,7,1}
	for(int i=0;i<MAXN;++i) cout << arr[i] <<' '; cout << endl;
	cin >> cur ;
    return 0;
}

how about using a datastructure Node {int value; int indexOfNextElement} as array element and then having three index references, one each for each stack pointing to the position of top element of each stack....adding a new element will simply be at the array index equal to the sum of number of elements in the three stacks or simply max of the top position of the three stack + 1

Here is an other solution with LINK LIST
we maintain a list indicates the vacant space stack, whose top node is "cur"

For
(1) Push, we simply add node(cur) to the stack respectively,and pop node(cur) from the vacant stack.
(2) Pop, we add node( Stack_now.top ) to the top of the vacant space stack.

#include <iostream>
#include <cmath>
#include <cstdio>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <cstring>
#include <sstream>
using namespace std;
 
#define mp make_pair
#define pb push_back
 
typedef double db;
typedef long long LL ;

const int MAXN = 5;
int cur;
int arr[ MAXN ];
int pre[ MAXN ];

struct Stack{
	 int top ;  
	 bool push( int x) {
	 	  if(cur == - 1) return false ; //overflows
	 	  int p=pre[cur];
  	 	  pre[ cur ] = top ;
  	 	  arr[ cur ] = x;
  	 	  top = cur;cur=p;
  	 	  return true;
  	 }
  	 void init(){
	 	  top = - 1;
  	 }
  	 bool pop(){
	 	  if(top == -1) return false;
	 	  int p=pre[top];
	 	  pre[top]=cur;
	 	  cur=top;top=p;
	 	  return true ;
  	 }
}S[3];

int main(){ 
	for(int i = 1; i < MAXN; ++ i) pre[i]=i-1; pre[0]=-1;
	cur = MAXN - 1;
	for(int i = 0; i < 3; ++ i) S[i].init();
	S[0].push( 5 );
    S[0].push( 4 );
	S[1].push( 3 ); 
	S[2].push( 2 );
	S[0].push( 1 ); // {5, 4, 3, 2, 1}
	cout << S[0].push( 7 ) << endl; // FULL
	S[2].pop(); // {5, 4, 3, x, 1}
	cout << S[0].push( 7 ) << endl; //{5,4,3,7,1}
	for(int i=0;i<MAXN;++i) cout << arr[i] <<' '; cout << endl;
	S[1].pop();//{5,4,x,7,1}
	cout << S[2].push(6) << endl;//{5,4,6,7,1}
	for(int i=0;i<MAXN;++i) cout << arr[i] <<' '; cout << endl;
	cin >> cur ;
    return 0;
}

Store it as a String array where the data has two parts "<Data>:<index>" . Here address points to the previous index of that stack. When a new 'Push' comes in we place it in the next empty slot. If we could not find a empty slot and return back to the same address then we have run out of space throw a OutOfBoundsException. The very first element will have index as -1 so when pop-ing pop till index == -1.

use stack if extra space is allowed.

else use universal hash.

=> O(1) time complexity for push-pop
=> No shifting required
=> Efficient only if array elements are +ve or in a particular range, otherwise it requires extra O(n) memory [ which is ridiculous because if we already have some extra memory why would we want to do such thing in a single array :) ]

Suppose given array is A[n].
X: First stack starts from A[0] and grows towards right [ maintain only top pointer ]
Y: Second stack starts from A[n-1] and grows towards left.[ maintain only top pointer ]
Z: Third stack starts from A[n/2] and can grow on either side and we can switch the end depending upon availability of space [ maintain left and right pointer + boolean switch for setting direction change for push/pop for its each element + current_top ]

Stack X : Push p

if X.top+1 != Z.left :
         A[++X.top] = p
else If Z.right+1 != Y.top:
         A[++Z.right] = A[Z.left]
         Z.left++
         Z.right.direction_change = true
         A[++X.top] = p
else 
        overflow

Stack X: Pop p

Pop A[X.top--] with stack underflow check

Push/Pop strategy for stack Y is same as stack X.

Stack Z: Push p

if current_top is right:
       if Z.right+1 != Y.top:
           A[++Z.right] = p
      else if Z.left-1 != X.top
           A[--Z.left] = p
           Z.left.direction_change = true
          current_top = left
      else  
           overflow
else //current_top is left
         if Z.left-1 != X.top:
            A[--Z.left] = p
      else if Z.right+1 != Y.top
           A[++Z.right] = p
           Z.right.direction_change = true
           current_top = right
      else  
           overflow

Stack Z : Pop p

//with stack underflow check
if current_top is right:
     pop p
     if Z.right.direction_switch = true
           Z.right.direction_switch = false
           currect_top = left
     Z.right--
else //current_top is left
     pop p
     if Z.left.direction_switch = true
           Z.left.direction_switch = false
           currect_top = right
     Z.left++

Idea for stack Z is we push on current_top if space is available, otherwise we push on other end
and set the newly pushed element's direction switch flag as true i.e we will use this direction switch
flag while pop operation. This sounds tricky but its better than shifting the middle stack elements.
Moreover if stack elements are all +ve or in some range then there is no need for using extra memory
for direction_switch as we can convert elements to corresponding negative value to denote the flag being set as true.

Theres a simple trick that might be useful:

Maintain a data structure which can store 3 elements of required types each accessible independently.

{{
struct node{

<Type1> stack1_data;
<Type2> stack2_data;
<Type3> stack3_data;
};

}}

Maintain 3 variables top1,top2,top3 (each showing TOP of individual stack).

Functions will look like :

push(node,stack_id,value)
pop(stack_id)

Pushing element in stack 1 means setting stack1_data and keeping the other 2 either zero or NULL meaning they are not occupied.
Poping takes stack_id and returns corresponding value using tuple < stack_id , topi > (i 1-3)

Comments are welcome.

Linked list approach to handle N number of stacks in an array:
- Each Node in the array keeps the link to previous item in the list.
- FreeStore is singleton stack which tracks the free nodes in the array.
- to push an element in stack, get an free Node from free store and add the value. O(1)
- to pop. reset the top of the stack. release the popped node to FreeStore. Time O(1).

//Note: code below is not tested completely. Correction/suggestions are appreciated.

#include <iostream>
using namespace std;

struct Node {
	int data;
	int prev;
};

const int MAX = 5;

// Singleton FreeStore
class FreeStore {
public:
	static FreeStore& getFreeStore() {
		static FreeStore freeStore;
		return freeStore;
	}

	int pop() {
		int ret = top;
		if(top != -1) {
			top = nodes[top].prev;
		}
		return ret;
	}

	void push(int i) {
		nodes[i].prev = top;
		top = i;
	}

	Node& getNode(int index) {
		return nodes[index];
	}

	void printNodes() {
		for(int i=0; i<MAX; ++i) {
			cout << nodes[i].data << ":" << nodes[i].prev << " ";
		}
		cout << endl;
	}
private:
	FreeStore() : top(-1) {
		cout << "Creating FreeStore" << endl;
		for(int i=0; i<MAX; ++i) {
			nodes[i].prev = top;
			++top;
		}
	}
private:
	int top;
	Node nodes[MAX];
};

class Stack {
public:
	Stack() : top(-1) {}

	void push(int data) {
		int index = FreeStore::getFreeStore().pop();
		if(index != -1) {
			FreeStore::getFreeStore().getNode(index).data = data;
			FreeStore::getFreeStore().getNode(index).prev = top;
			top = index;
		}
		else {
			cout << "Overflow" << endl;
		}
	}

	int pop() {
		int data = -1;
		if(top != -1) {
			data = FreeStore::getFreeStore().getNode(top).data;
			int oldtop = top;			
			top = FreeStore::getFreeStore().getNode(top).prev;
			FreeStore::getFreeStore().push(oldtop);
		}
		else {
			cout << "Stack is empty" << endl;
		}
		return data;
	}

private:
	int top;
};

int main() {
	Stack st1, st2, st3;
	cout << "Poping : " << st1.pop() << endl;
	st1.push(5);
	st2.push(4);
	st3.push(3);
	st1.push(2);
	st1.push(1);
	cout << "Poping : " << st1.pop() << endl;
	st1.push(0);
	cout << "Poping : " << st3.pop() << endl;
	cout << "Poping : " << st2.pop() << endl;
	st1.push(6);
	st3.push(7);
	st2.push(8);
	cout << "Poping : " << st2.pop() << endl;
	cout << "Poping : " << st1.pop() << endl;
	cout << "Poping : " << st3.pop() << endl;
	return 0;
}

Divide Array into three portions 0 --- N/3, N/3 --- 2*(N/3), 2*(N/3) --- N.

S1 will start from index 0 and move towards right, S2 will start at N/3 and move towards left. S3 will start at 2*(N/3) and move towards left. If S1 and S2 meet between 0 and N/3, S1 will continue from N and move towards left and S2 will continue from N/3 and move towards right. If S2 and S3 meet in N/3 and 2*(N/3), S3 will continue from 2*(N/3) and move towards right.

The logic is This is like If I assume 3 Stacks A, B, C, I will subdivide A into A1, A2, B into B1 and B2, and C into C1 and C2.

I use 0 to N/3 for A1 and B1, N/3 to 2*(N/3) for B2 and C1 and 2*(N/3) to N for C2 and A2. In this way we can manage three stacks in an array ... I didn't cross check my logic ;) ...

A 2D integer array arr[3][n] where arr[0],arr[1],arr[2] list of indices for the respective stacks' values. For eg. arr[0][0] = 1 arr[0][1] = 2 arr[0][2] =5 will mean that indices 1, 2 and 5 in the given array(of size n) will hold values for the given stack. Also keep 3 counters l1, l2, l3 which will hold the lengths of the respective stacks.

The length of the three stacks doesn't matter. Divide the array into three parts according to your wish with the condition that the new stack must have starting index as the next value of previous stack end (initially assigned)
Store the starting point of the stacks in some location. Now keep track of the top of the stacks as elements are entered. When a stack has reached the end, i.e., reached location one index behind the next stack, check whether the next stack is full or not via the same method. If its not full,move the entire stack elements one position right(not the array) and change the top as well as starting point of the corresponding stack. If the second stack is also ful, turn to third and check the conditions. If thats also full, then array is fully loaded.
this was the case if the first stack overflows.
For the second stack, check the first stack for empty space first, if not present, look the third stack.
For the third stack, check the second stack first, followed by first if no space in second.

1. Build a new Data structure: Node { int nextIndex, T val};
2. Create three integer variables: s1_top, s2_top, s3_top, for tracking the top index for each stack, create method to read and update top index for all stacks.
3. Create a LinkedList for tracking vacant space in the array: list;
3. Implements method:
    
    T pop(int stack_no){
           int top = getStackTopIndex(stack_no);
           if(top==-1) return null;    //stack is empty, nothing to pop up
           list.add(top);
           int newtop = T.nextIndex;
           setStatckTopIndex(stack_no, newtop);
           return array[top].val;
     }


    push(int stack_no, int data){
           if(list.isEmpty) return; 
           int vacant_index = list.getFirst();
           int top = getStackTopIndex(stack_no);
           array[vacant_index]=new T(data, top);
           setStatckTopIndex(stack_no, vacant_index);
           list.removeFirst();
     }

    T peek(int stack_no){
           int top = getStackTopIndex(stack_no);
           if(top==-1) return null;    //stack is empty, nothing to peek
           return array[top].val;
     }

All O(1) in time.

Here is my solution:
I am storing the MID stack starting initially in the middle of the array.
Then onwards every push to the MID stack is done on either side of the mid variable, depending on the current size of the MID stack.

When performing a push to the MID stack, following collision might occur:

If there is a possible collision with the LEFT stack on a particular push, then i shift the entire mid stack to the RIGHT by half the value of available free space, and then execute the push to the mid stack

Similarly, if there is collision with the RIGHT stack, then I shift the MID stack to the LEFT by half the value of the available free space.

When pushing to the LEFT or RIGHT stack, if there is a possible collision with MID, then I move, the MID stack in the other direction by half the available freespace.

If there is now free space available, then we have an Overflow.

This implementation, doesnt use any extra space.
Every push that results in a shift operation, will take O(n), otherwise all operations are O(1).

enum stackId{LEFT, MID, RIGHT };

class threeStacks {

	int* arr;
	
	int leftSize;
	int rightSize;
	int midSize;
	int mid;
	int maxSize;
	public:
		threeStacks(int n):leftSize(0), rightSize(0), midSize(0), mid(n/2), maxSize(n)
		{
			arr = new int[n];
		}
		
		void push(stackId sid, int val){
			switch(sid){
				case LEFT:
					pushLeft(val);
				break;
				
				case MID:
					pushMid(val);
				break;
				
				case RIGHT:
					pushRight(val);
			}
		}
		
		int pop(stackId sid){
			switch(sid){
				case LEFT:
					return popLeft();
				case MID:
					return popMid();
				case RIGHT:
					return popRight();
			}
		}
		
		
		int top(stackId sid){
			switch(sid){
				case LEFT:
					return topLeft();
				case MID:
					return topMid();
				case RIGHT:
					return topRight();
			}
		}
		
		void pushMid(int val){
			if(midSize+leftSize+rightSize+1 > maxSize){
				cout << "Overflow!!"<<endl;
				return;
			}
			if(midSize % 2 == 0){
				if(mid - ((midSize+1)/2) == leftSize-1){
					//left side OverFlow
					if(!shiftMid(RIGHT)){
						cout << "Overflow!!"<<endl;
						return;	
					}
				}
				midSize++;
				arr[mid - (midSize/2)] = val;
			}
			else{
				if(mid + ((midSize+1)/2) == (maxSize - rightSize)){
					//right side OverFlow
					if(!shiftMid(LEFT)){
						cout << "Overflow!!"<<endl;
						return;	
					}
				}
				midSize++;
				arr[mid + (midSize/2)] = val;							
			}
		}
		
		int popMid(){
			if(midSize == 0){
				cout << "Mid Stack Underflow!!"<<endl;
				return -1;
			}
			int val;
			if(midSize % 2 == 0)
				val = arr[mid - (midSize/2)];
			else
				val = arr[mid + (midSize/2)];
			midSize--;
			return val;
		}
		
		int topMid(){
			if(midSize == 0){
				cout << "Mid Stack Underflow!!"<<endl;
				return -1;
			}
			int val;
			if(midSize % 2 == 0)
				val = arr[mid - (midSize/2)];
			else
				val = arr[mid + (midSize/2)];
			return val;
		}
		
		bool shiftMid(stackId dir){
			int freeSpace;
			switch (dir){
				case LEFT:
					freeSpace = (mid - midSize/2) - leftSize;
					if(freeSpace < 1)
						return false;				
					if(freeSpace > 1)
						freeSpace /= 2;
					for(int i=0; i< midSize; i++){
						arr[(mid - midSize/2) - freeSpace + i] = arr[(mid - midSize/2) + i];
					}
					mid = mid-freeSpace;
				break;
				case RIGHT:
					freeSpace = maxSize - rightSize - (mid + midSize/2) - 1;
					if(freeSpace < 1)
						return false;				
					if(freeSpace > 1)
						freeSpace /= 2;
					for(int i=0; i< midSize; i++){
						arr[(mid + midSize/2) + freeSpace - i] = arr[(mid + midSize/2) - i];
					}
					mid = mid+freeSpace;
				break;				
				default:
					return false;
			}
		}
		
		void pushLeft(int val){
			if(midSize+leftSize+rightSize+1 > maxSize){
				cout << "Overflow!!"<<endl;
				return;
			}
			if(leftSize == (mid - midSize/2)){
				//left side OverFlow
				if(!shiftMid(RIGHT)){
					cout << "Overflow!!"<<endl;
					return;	
				}
			}
			arr[leftSize] = val;
			leftSize++;
		}
		
		int popLeft(){
			if(leftSize == 0){
				cout << "Left Stack Underflow!!"<<endl;
				return -1;
			}
			leftSize--;
			return arr[leftSize];
		}
		
		int topLeft(){
			if(leftSize == 0){
				cout << "Left Stack Underflow!!"<<endl;
				return -1;
			}
			return arr[leftSize - 1];
		}
		
		void pushRight(int val){
			if(midSize+leftSize+rightSize+1 > maxSize){
				cout << "Overflow!!"<<endl;
				return;
			}
			if(maxSize - rightSize - 1 == (mid + midSize/2)){
				//right side OverFlow
				if(!shiftMid(LEFT)){
					cout << "Overflow!!"<<endl;
					return;	
				}
			}
			rightSize++;
			arr[maxSize - rightSize] = val;
		}
		
		int popRight(){
			if(rightSize == 0){
				cout << "Right Stack Underflow!!"<<endl;
				return -1;
			}
			int val = arr[maxSize - rightSize];
			rightSize--;
			return val;
		}
		
		int topRight(){
			if(rightSize == 0){
				cout << "Right Stack Underflow!!"<<endl;
				return -1;
			}
			return arr[maxSize - rightSize];
		}
};

split array into 3 parts such as 0 -- n/3, n/3 -- 2n/3, 2n/3 -- n.
use each of them as separate stack.
You may use one byte in the bottom of each partition for tracking the current top location in the present stack.