Guided Project: Stacks and Queues

Project Overview

Learning Goals

Understand stack data structure
Implement bracket validation
Handle different bracket types
Optimize validation logic

Prerequisites

Basic JavaScript knowledge
Array operations understanding
Stack concept familiarity
Basic problem-solving skills

Key Concepts

Stack Operations

Push: Add element to top
Pop: Remove top element
Peek: View top element
isEmpty: Check if empty

Bracket Types

Opening

( { [

Closing

) } ]

Valid Bracket Sequence Implementation

Step-by-Step Implementation

Step 1: Setup Bracket Maps

                                    bracket_pairs = {
    '(': ')',
    '{': '}',
    '[': ']'
}

open_brackets = {'(', '{', '['}
close_brackets = {')', '}', ']'}
                                

Step 2: Validation Function

                                    def is_valid_bracket_sequence(sequence):
    stack = []
    for char in sequence:
        # Skip non-bracket characters
        if char not in open_brackets and char not in close_brackets:
            continue
        # Handle logic here
    return len(stack) == 0
                                

Step 3: Open Bracket Logic

                                    # Inside the for loop from step 2
if char in open_brackets:
    # If it's an opening bracket, push to stack
    stack.append(char)
else:
    # Handle closing brackets
    pass
                                

Step 4: Close Bracket Logic

                                    # Inside the else block from step 3
# If stack is empty, no matching open bracket
if len(stack) == 0:
    return False
# Get the last open bracket
last_open = stack.pop()
# Check if brackets match
if bracket_pairs[last_open] != char:
    return False
                                

Step 5: Complete Implementation

                                def is_valid_bracket_sequence(sequence):
    stack = []
    for char in sequence:
        # Skip non-bracket characters
        if char not in open_brackets and char not in close_brackets:
            continue
        if char in open_brackets:
            # If it's an opening bracket, push to stack
            stack.append(char)
        else:
            # If stack is empty, no matching open bracket
            if len(stack) == 0:
                return False
            # Get the last open bracket
            last_open = stack.pop()
            # Check if brackets match
            if bracket_pairs[last_open] != char:
                return False
    # Valid only if all brackets were matched
    return len(stack) == 0
                            

Practice Challenge

Now that you've learned how to validate bracket sequences using a stack, try implementing a queue with a twist.

Challenge: Implement Queue using Stacks

Create a queue data structure using two stacks. Your implementation should include these methods:

Requirements:

enqueue(element): Add element to the queue
dequeue(): Remove and return the front element
peek(): Return (without removing) the front element
isEmpty(): Return true if queue is empty

Starter Code:

                            class StackQueue:
    def __init__(self):
        self.stack_newest = []  # for enqueue
        self.stack_oldest = []  # for dequeue
    
    def enqueue(self, value):
        self.stack_newest.append(value)
    
    def dequeue(self):
        if not self.stack_oldest:
            while self.stack_newest:
                self.stack_oldest.append(self.stack_newest.pop())
        if self.stack_oldest:
            return self.stack_oldest.pop()
        return None
    
    def peek(self):
        if not self.stack_oldest:
            while self.stack_newest:
                self.stack_oldest.append(self.stack_newest.pop())
        if self.stack_oldest:
            return self.stack_oldest[-1]
        return None
    
    def is_empty(self):
        return not self.stack_newest and not self.stack_oldest
                        

Challenge Practice Resources:

If you want more practice with stacks and queues, check out these LeetCode problems: