You are given a fixed-size array of length n.
The task is to implement two stacks in this array in such a way that they use the array space efficiently and do not overwrite each other’s data.
Note:
A stack follows the LIFO (Last In, First Out) principle:
-
push() inserts an element on top of the stack.
-
pop() removes the top element.
-
peek() returns the top element without removing it.
My Approach
Overview
I need to implement two stacks in a single fixed-size array.
-
I will use one side of the array for STACK 1.
-
And the opposite side is used for STACK 2.
-
I will maintain two variables to track the tops of the stacks:
-
top1 for STACK 1 (initialized to -1)
top2 for STACK 2 (initialized to n)
-
PUSH Operation
The purpose of this push operation is to insert an element into a stack.
Overflow Check:
- If the array is full, we cannot push any element.
- Condition for overflow is (top1 + 1 == top2)
- If true, the array is full, and further push is not allowed.
Implementation:
- Stack 1: Increment top1 and insert the element at array[top1].
- Stack 2: Decrement top2 and insert the element at array[top2].
POP Operation
The purpose of this pop operation is to remove the top element from a stack.
Underflow Check:
- Stack 1 empty if (top1 == -1)
- Stack 2 empty if (top2 == n)
- Stack 1: Access the element at top1, optionally set it to 0, then decrement top1.
- Stack 2: Access the element at top2, optionally set it to 0, then increment top2.
PEEK Operation
The purpose of this peek operation is to view the top element of the stack without removing it.Empty Check: Use the same conditions as in POP.
Implementation:
- Stack 1: Return array[top1].
- Stack 2: Return array[top2].
DISPLAY Operation
The purpose of this display operation is to print all elements in the stack.
Empty Check: Same as POP/PEEK operations.Implementation:
- Stack 1: Loop from top1 down to index 0 and print elements.
- Stack 2: Loop from top2 up to index n-1 and print elements.
#include <stdio.h>
#define SIZE 4
// Global array and top variables
int stackArray[SIZE];
int top1 = -1; // Stack 1 starts from left
int top2 = SIZE; // Stack 2 starts from right
// Push element into Stack 1
void pushStack1(int data) {
if (top1 + 1 == top2) {
printf("Stack 1 Overflow! Cannot push %d\n", data);
return;
}
stackArray[++top1] = data;
printf("Element %d added to Stack 1\n", data);
}
// Push element into Stack 2
void pushStack2(int data) {
if (top1 + 1 == top2) {
printf("Stack 2 Overflow! Cannot push %d\n", data);
return;
}
stackArray[--top2] = data;
printf("Element %d added to Stack 2\n", data);
}
// Pop element from Stack 1
void popStack1() {
if (top1 == -1) {
printf("Stack 1 Underflow! Cannot pop\n");
return;
}
printf("Element %d popped from Stack 1\n", stackArray[top1]);
stackArray[top1--] = 0;
}
// Pop element from Stack 2
void popStack2() {
if (top2 == SIZE) {
printf("Stack 2 Underflow! Cannot pop\n");
return;
}
printf("Element %d popped from Stack 2\n", stackArray[top2]);
stackArray[top2++] = 0;
}
// Peek top element of Stack 1
void peekStack1() {
if (top1 == -1) {
printf("Stack 1 is EMPTY\n");
return;
}
printf("Top of Stack 1: %d\n", stackArray[top1]);
}
// Peek top element of Stack 2
void peekStack2() {
if (top2 == SIZE) {
printf("Stack 2 is EMPTY\n");
return;
}
printf("Top of Stack 2: %d\n", stackArray[top2]);
}
// Display elements of Stack 1
void displayStack1() {
if (top1 == -1) {
printf("Stack 1 is EMPTY\n");
return;
}
printf("STACK 1: ");
for (int i = top1; i >= 0; i--) {
printf("%d ", stackArray[i]);
}
printf("\n");
}
// Display elements of Stack 2
void displayStack2() {
if (top2 == SIZE) {
printf("Stack 2 is EMPTY\n");
return;
}
printf("STACK 2: ");
for (int i = top2; i < SIZE; i++) {
printf("%d ", stackArray[i]);
}
printf("\n");
}
int main() {
// Initialize array with 0
for (int i = 0; i < SIZE; i++) stackArray[i] = 0;
// Push elements into Stack 2
pushStack2(2);
pushStack2(4);
pushStack2(6);
pushStack2(8);
// Display stacks
displayStack1(); // STACK 1 is empty
displayStack2(); // STACK 2: 8 6 4 2
// Pop from Stack 2
popStack2();
// Push into Stack 1
pushStack1(10);
// Display stacks after operations
displayStack1(); // STACK 1: 10
displayStack2(); // STACK 2: 6 4 2
// Attempt to push into Stack 2 (may cause overflow)
pushStack2(20);
return 0;
}
JS Code:
// Custom Exception for Stack Overflow
class StackDataOverflowException extends Error {
constructor(message) {
super(message);
this.name = "StackDataOverflowException";
}
}
// Custom Exception for Stack Underflow / Access Error
class StackDataAccessException extends Error {
constructor(message) {
super(message);
this.name = "StackDataAccessException";
}
}
class TwoStacksInArray {
constructor(n) {
this.array = new Array(n).fill(0); // Initialize array with zeros
this.n = n;
this.top1 = -1; // Stack 1 starts from left
this.top2 = n; // Stack 2 starts from right
}
// Push element into Stack 1
pushIntoStack1(data) {
if (this.top1 + 1 === this.top2)
throw new StackDataOverflowException("Stack 1 is FULL");
this.array[++this.top1] = data;
console.log(`Element ${data} added to Stack 1`);
}
// Push element into Stack 2
pushIntoStack2(data) {
if (this.top1 + 1 === this.top2)
throw new StackDataOverflowException("Stack 2 is FULL");
this.array[--this.top2] = data;
console.log(`Element ${data} added to Stack 2`);
}
// Pop element from Stack 1
popFromStack1() {
if (this.top1 === -1)
throw new StackDataAccessException("Stack 1 is EMPTY");
console.log(`Element ${this.array[this.top1]} popped from Stack 1`);
this.array[this.top1--] = 0;
}
// Pop element from Stack 2
popFromStack2() {
if (this.top2 === this.n)
throw new StackDataAccessException("Stack 2 is EMPTY");
console.log(`Element ${this.array[this.top2]} popped from Stack 2`);
this.array[this.top2++] = 0;
}
// Peek top element of Stack 1
peekFromStack1() {
if (this.top1 === -1)
throw new StackDataAccessException("Stack 1 is EMPTY");
console.log(`Top of Stack 1: ${this.array[this.top1]}`);
}
// Peek top element of Stack 2
peekFromStack2() {
if (this.top2 === this.n)
throw new StackDataAccessException("Stack 2 is EMPTY");
console.log(`Top of Stack 2: ${this.array[this.top2]}`);
}
// Display elements of Stack 1
displayStack1() {
if (this.top1 === -1) {
console.log("Stack 1 is EMPTY");
return;
}
process.stdout.write("STACK 1: ");
for (let i = this.top1; i >= 0; i--) {
process.stdout.write(`${this.array[i]} `);
}
console.log();
}
// Display elements of Stack 2
displayStack2() {
if (this.top2 === this.n) {
console.log("Stack 2 is EMPTY");
return;
}
process.stdout.write("STACK 2: ");
for (let i = this.top2; i < this.n; i++) {
process.stdout.write(`${this.array[i]} `);
}
console.log();
}
}
let stacks = new TwoStacksInArray(4);
try {
// Push elements into Stack 2
stacks.pushIntoStack2(2);
stacks.pushIntoStack2(4);
stacks.pushIntoStack2(6);
stacks.pushIntoStack2(8);
// Display current stacks
stacks.displayStack1(); // STACK 1 is empty
stacks.displayStack2(); // STACK 2: 8 6 4 2
// Pop from Stack 2
stacks.popFromStack2();
// Push into Stack 1
stacks.pushIntoStack1(10);
// Display stacks after operations
stacks.displayStack1(); // STACK 1: 10
stacks.displayStack2(); // STACK 2: 6 4 2
// Attempt to push into Stack 2 (may cause overflow)
stacks.pushIntoStack2(20);
} catch (error) {
if (error instanceof StackDataOverflowException || error instanceof StackDataAccessException) {
console.error("Custom Stack Error:", error.message);
} else {
console.error("Unknown Error:", error);
}
}
Comments
Post a Comment