Welcome to our comprehensive guide on implementing two stacks in one array! In this lesson, we'll learn how to leverage a single array to simulate the behavior of two separate stacks, a fundamental concept in computer science. Let's dive in! š¤æ
Before we dive into the main topic, let's quickly review what a stack is. A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. It operates like a pile of dishes where the last dish placed is the first one to be removed.
To simulate two stacks in one array, we'll use a clever trick called the 'Linked List' approach. We'll divide the array into two regions, each acting as a separate stack. Let's call them stack1 and stack2.
Here's a simple diagram:
Array: [0, 1, 2, 3, 4, 5, 6, 7, 8]
stack1: [0, 1, 2]
stack2: [8]In this example, stack1 is using the first three indices of the array, while stack2 is using the last index.
To push an element into a stack, we'll move all elements from the corresponding stack to the right until we find an empty space.
Array: [0, 1, 2, 3, 4, 5, 6, 7, 8]
stack1: [0, 1, 2]
stack2: [8]
Push 4 into stack1:
Array: [0, 1, 2, 3, 4, 5, 6, 7, 8]
stack1: [0, 1, 2, 4]
stack2: [8]Array: [0, 1, 2, 3, 4, 5, 6, 7, 8]
stack1: [0, 1, 2, 4]
stack2: [8]
Push 6 into stack2:
Array: [0, 1, 2, 3, 4, 5, 6, 7, 8]
stack1: [0, 1, 2, 4]
stack2: [6, 8]š” Pro Tip: When pushing into a stack, always check if the array is full before pushing an element.
To pop an element from a stack, we'll simply remove the last element from the corresponding stack.
Array: [0, 1, 2, 3, 4, 5, 6, 7, 8]
stack1: [0, 1, 2, 4]
stack2: [6, 8]
Pop from stack1:
Array: [0, 1, 2, 3, 4, 5, 6, 7, 8]
stack1: [0, 1, 2, 3]
stack2: [6, 8]Array: [0, 1, 2, 3, 4, 5, 6, 7, 8]
stack1: [0, 1, 2, 3]
stack2: [6, 8]
Pop from stack2:
Array: [0, 1, 2, 3, 4, 5, 6, 7, 8]
stack1: [0, 1, 2, 3]
stack2: [8]š” Pro Tip: When popping from a stack, always check if the stack is empty before popping an element.
Here's a simple Python implementation of the two-stack solution:
class TwoStacksInOneArray:
def __init__(self, size):
self.arr = [None] * size
self.top1, self.top2 = -1, size
def push1(self, value):
if not self.isFull():
if self.top1 == self.top2 - 1:
print("Stack1 is full.")
return
self.top1 += 1
self.arr[self.top1] = value
def push2(self, value):
if not self.isFull():
if self.top1 == self.top2:
print("Stack2 is full.")
return
self.top2 -= 1
self.arr[self.top2] = value
def pop1(self):
if not self.isEmpty1():
val = self.arr[self.top1]
self.top1 -= 1
return val
def pop2(self):
if not self.isEmpty2():
val = self.arr[self.top2]
self.top2 += 1
return val
def peek1(self):
if not self.isEmpty1():
return self.arr[self.top1]
def peek2(self):
if not self.isEmpty2():
return self.arr[self.top2]
def isFull(self):
return self.top1 + 1 == self.top2
def isEmpty1(self):
return self.top1 == -1
def isEmpty2(self):
return self.top2 == len(self.arr)
# Instantiate the TwoStacksInOneArray object with a size of 5
stack = TwoStacksInOneArray(5)
# Push elements into stack1
stack.push1(1)
stack.push1(2)
stack.push1(3)
# Push elements into stack2
stack.push2(4)
stack.push2(5)
# Pop elements from stack1 and stack2
print(stack.pop1()) # Output: 3
print(stack.pop2()) # Output: 5
# Peek into stack1 and stack2
print(stack.peek1()) # Output: 2
print(stack.peek2()) # Output: 4What is the principle that a stack follows?
What is the advantage of simulating two stacks in one array?