Search⌘ K
AI Features

Solution Review: Implement Two Stacks Using One Array

Explore how to efficiently implement two stacks using one array by leveraging opposite ends for growth. Understand the space optimization and overflow checks involved. This lesson equips you to apply constant time stack operations without resizing arrays, essential for coding interviews.

Solution: Stacks on opposite ends

...
C#
namespace chapter_4
{
//You can either divide array in two halves or start stacks at extreme ends.
//We'll use the second technique to solve this problem.
//Top of Stack 1 starts from extreme left of array i.e top1 = 0;
//Top of Stack 2 starts from extreme right of array i.e top2 = size - 1;
class twoStacks
{
int size;
int [] arr;
int top1, top2;
//Store top value indices of Stack 1 and Stack 2
public twoStacks(int n)
{
size = n;
arr = new int[size];
top1 = -1;
top2 = size;
}
//Insert Value in First Stack
public void push1(int value)
{
//Check for empty space and insert value if there's an empty space.
if (top1 < top2 - 1)
{
arr[++top1] = value;
}
}
//Insert Value in Second Stack
public void push2(int value)
{
//Check for empty space and insert value if there's an empty space.
if (top1 < top2 - 1)
{
arr[--top2] = value;
}
}
//Return and remove top Value from First Stack
public int pop1()
{
//Get value from top1 index and increment it.
if (top1 >= 0)
{
int val = arr[top1--];
return val;
}
return -1;
}
//Return and remove top Value from Second Stack
public int pop2()
{
//Get value from top2 index and increment it.
if (top2 < size)
{
int val = arr[top2++];
return val;
}
return -1;
}
static void Main(string[] args)
{
twoStacks tS = new twoStacks(5);
tS.push1(11);
tS.push1(3);
tS.push1(7);
tS.push2(1);
tS.push2(9);
Console.WriteLine(tS.pop1());
Console.WriteLine(tS.pop2());
Console.WriteLine(tS.pop2());
Console.WriteLine(tS.pop2());
Console.WriteLine(tS.pop1());
return;
}
};
}

This ...