Queue Using Two Stacks in DSA Python - Build from Scratch

Queue Using Two Stacks

📖 Scenario: Imagine you are managing a line of customers waiting to buy tickets. You want to keep track of the order they arrive and serve them in the same order. But you only have two stacks (like two piles of plates) to help you manage this line.

🎯 Goal: Build a queue using two stacks. You will add customers to the line and serve them in the order they arrived, using only two stacks.

📋 What You'll Learn

Create two empty stacks named stack_in and stack_out

Create a variable queue_size to keep track of the number of customers

Write a function enqueue to add a customer to stack_in and update queue_size

Write a function dequeue to remove a customer from stack_out, transferring from stack_in if needed, and update queue_size

Print the state of stack_in and stack_out after operations

💡 Why This Matters

🌍 Real World

Queues are used in many places like customer service lines, printer job management, and task scheduling. Using two stacks to build a queue is a common programming technique to understand data structure transformations.

💼 Career

Understanding how to implement one data structure using others shows problem-solving skills and knowledge of data structures, which is important for software development and technical interviews.

1

Create two empty stacks

Create two empty lists called stack_in and stack_out to represent the two stacks.

DSA Python

# Your code here

Hint

Use empty lists to represent stacks in Python.

2

Create a variable to track queue size

Create a variable called queue_size and set it to 0 to track how many customers are in the queue.

DSA Python

stack_in = []
stack_out = []
# Your code here

Hint

Start with zero customers in the queue.

3

Write enqueue and dequeue functions

Write a function called enqueue that takes a parameter customer, adds it to stack_in, and increases queue_size by 1. Then write a function called dequeue that removes and returns the oldest customer from the queue by using stack_out. If stack_out is empty, move all items from stack_in to stack_out first. Decrease queue_size by 1 when a customer is removed.

DSA Python

stack_in = []
stack_out = []
queue_size = 0
# Your code here

Hint

Remember to move all items from stack_in to stack_out only when stack_out is empty before dequeuing.

4

Print the stacks after enqueue and dequeue

Call enqueue three times with customers 'Alice', 'Bob', and 'Charlie'. Then call dequeue once. Finally, print the contents of stack_in and stack_out to show the current state of the queue.

DSA Python

stack_in = []
stack_out = []
queue_size = 0

def enqueue(customer):
    global queue_size
    stack_in.append(customer)
    queue_size += 1

def dequeue():
    global queue_size
    if not stack_out:
        while stack_in:
            stack_out.append(stack_in.pop())
    if stack_out:
        queue_size -= 1
        return stack_out.pop()
    else:
        return None

# Your code here

Hint

After dequeuing once, stack_out should have the remaining customers in reverse order, and stack_in should be empty.