Queue and Deque Data Structures Exercise - Complete Solutions

from collections import deque

class ShuttlecockBox:
    def __init__(self, capacity=10):
        self.box = deque()
        self.capacity = capacity
        self.shuttlecock_count = 0
    
    def add_shuttlecock(self, shuttlecock_id):
        """Add a shuttlecock to the box (enqueue)"""
        if len(self.box) >= self.capacity:
            print(f"Box is full! Cannot add shuttlecock {shuttlecock_id}")
            return False
        
        self.box.append(shuttlecock_id)
        self.shuttlecock_count += 1
        print(f"Shuttlecock {shuttlecock_id} added to the box")
        return True
    
    def remove_shuttlecock(self):
        """Remove a shuttlecock from the box (dequeue)"""
        if not self.box:
            print("Box is empty! No shuttlecock to remove")
            return None
        
        removed = self.box.popleft()
        print(f"Shuttlecock {removed} removed from the box")
        return removed
    
    def peek(self):
        """View the next shuttlecock to be removed"""
        if not self.box:
            print("Box is empty!")
            return None
        
        print(f"Next shuttlecock to be removed: {self.box[0]}")
        return self.box[0]
    
    def display_box(self):
        """Display current state of the box"""
        if not self.box:
            print("Box is empty!")
        else:
            print(f"Current shuttlecocks in box: {list(self.box)}")
            print(f"Total shuttlecocks: {len(self.box)}")
    
    def is_empty(self):
        """Check if box is empty"""
        return len(self.box) == 0
    
    def is_full(self):
        """Check if box is full"""
        return len(self.box) >= self.capacity

def main():
    box = ShuttlecockBox()
    
    while True:
        print("\n" + "="*50)
        print("SHUTTLECOCK BOX MANAGEMENT SYSTEM")
        print("="*50)
        print("1. Add Shuttlecock to Box")
        print("2. Remove Shuttlecock from Box")
        print("3. Peek Next Shuttlecock")
        print("4. Display Box Contents")
        print("5. Check if Box is Empty")
        print("6. Check if Box is Full")
        print("7. Simulate Game (Add multiple shuttlecocks)")
        print("8. Exit")
        print("="*50)
        
        try:
            choice = int(input("Enter your choice (1-8): "))
            
            if choice == 1:
                shuttlecock_id = input("Enter shuttlecock ID: ")
                box.add_shuttlecock(shuttlecock_id)
            
            elif choice == 2:
                box.remove_shuttlecock()
            
            elif choice == 3:
                box.peek()
            
            elif choice == 4:
                box.display_box()
            
            elif choice == 5:
                if box.is_empty():
                    print("Box is empty!")
                else:
                    print("Box is not empty!")
            
            elif choice == 6:
                if box.is_full():
                    print("Box is full!")
                else:
                    print(f"Box has space for {box.capacity - len(box.box)} more shuttlecocks")
            
            elif choice == 7:
                print("Simulating a badminton game...")
                shuttlecocks = ["S1", "S2", "S3", "S4", "S5"]
                for s in shuttlecocks:
                    box.add_shuttlecock(s)
                
                print("\nGame started! Using shuttlecocks in FIFO order:")
                while not box.is_empty():
                    used = box.remove_shuttlecock()
                    print(f"Playing with shuttlecock {used}")
            
            elif choice == 8:
                print("Thank you for using Shuttlecock Box Management System!")
                break
            
            else:
                print("Invalid choice! Please enter a number between 1-8.")
        
        except ValueError:
            print("Invalid input! Please enter a valid number.")
        except KeyboardInterrupt:
            print("\n\nProgram interrupted by user. Goodbye!")
            break

if __name__ == "__main__":
    main()

from collections import deque

def is_palindrome_deque(s):
    """
    Check if a string is palindrome using deque
    Algorithm 4.1: Palindrome Checker
    
    Steps:
    1. Remove spaces and convert to lowercase
    2. Add all characters to deque
    3. Compare characters from both ends
    4. Remove matching characters from both ends
    5. Continue until deque is empty or mismatch found
    """
    # Preprocessing: remove spaces and convert to lowercase
    cleaned_string = ''.join(s.split()).lower()
    
    # Create deque and add all characters
    char_deque = deque(cleaned_string)
    
    # Check palindrome by comparing front and rear characters
    while len(char_deque) > 1:
        front_char = char_deque.popleft()  # Remove from front
        rear_char = char_deque.pop()       # Remove from rear
        
        if front_char != rear_char:
            return False
    
    return True

def is_palindrome_advanced(s):
    """
    Advanced palindrome checker with more preprocessing
    Handles punctuation, spaces, and case sensitivity
    """
    # Remove non-alphanumeric characters and convert to lowercase
    cleaned = ''.join(char.lower() for char in s if char.isalnum())
    
    # Create deque
    char_deque = deque(cleaned)
    
    # Check palindrome
    while len(char_deque) > 1:
        if char_deque.popleft() != char_deque.pop():
            return False
    
    return True

def demonstrate_palindrome_checking():
    """Demonstrate palindrome checking with various examples"""
    test_strings = [
        "racecar",
        "A man a plan a canal Panama",
        "race a car",
        "hello",
        "Madam",
        "Was it a car or a cat I saw",
        "No 'x' in Nixon",
        "Mr. Owl ate my metal worm",
        "12321",
        "12345"
    ]
    
    print("PALINDROME CHECKER USING DEQUE")
    print("=" * 50)
    
    for test_string in test_strings:
        result_basic = is_palindrome_deque(test_string)
        result_advanced = is_palindrome_advanced(test_string)
        
        print(f"String: '{test_string}'")
        print(f"  Basic Check: {'✓ Palindrome' if result_basic else '✗ Not Palindrome'}")
        print(f"  Advanced Check: {'✓ Palindrome' if result_advanced else '✗ Not Palindrome'}")
        print()

def interactive_palindrome_checker():
    """Interactive palindrome checker"""
    print("\nINTERACTIVE PALINDROME CHECKER")
    print("=" * 40)
    
    while True:
        user_input = input("\nEnter a string to check (or 'quit' to exit): ")
        
        if user_input.lower() == 'quit':
            break
        
        # Show deque operations step by step
        print(f"\nChecking: '{user_input}'")
        cleaned = ''.join(user_input.split()).lower()
        print(f"Cleaned string: '{cleaned}'")
        
        char_deque = deque(cleaned)
        print(f"Initial deque: {list(char_deque)}")
        
        is_palindrome = True
        step = 1
        
        while len(char_deque) > 1:
            front = char_deque.popleft()
            rear = char_deque.pop()
            
            print(f"Step {step}: Comparing '{front}' (front) with '{rear}' (rear)")
            
            if front != rear:
                print(f"  ✗ Mismatch found! Not a palindrome.")
                is_palindrome = False
                break
            else:
                print(f"  ✓ Match! Remaining deque: {list(char_deque)}")
            
            step += 1
        
        if is_palindrome:
            print(f"  🎉 '{user_input}' is a PALINDROME!")
        else:
            print(f"  ❌ '{user_input}' is NOT a palindrome.")

# Algorithm 4.1 Implementation
def palindrome_algorithm_4_1(string):
    """
    Implementation of Algorithm 4.1 for Palindrome Checking
    
    Algorithm 4.1: Palindrome Checker using Deque
    Input: String to check
    Output: Boolean (True if palindrome, False otherwise)
    
    Steps:
    1. Initialize empty deque
    2. Process string (remove spaces, convert to lowercase)
    3. Insert all characters into deque
    4. While deque has more than one character:
       a. Remove character from front
       b. Remove character from rear
       c. If characters don't match, return False
    5. Return True (palindrome confirmed)
    """
    
    # Step 1: Initialize deque
    dq = deque()
    
    # Step 2: Process string
    processed_string = ''.join(string.split()).lower()
    
    # Step 3: Insert all characters
    for char in processed_string:
        dq.append(char)
    
    # Step 4: Compare characters from both ends
    while len(dq) > 1:
        front_char = dq.popleft()  # Remove from front
        rear_char = dq.pop()       # Remove from rear
        
        if front_char != rear_char:
            return False
    
    # Step 5: String is palindrome
    return True

def main():
    """Main function to run palindrome checker"""
    print("PALINDROME CHECKER USING DEQUE")
    print("Based on Algorithm 4.1")
    print("=" * 50)
    
    # Demonstrate with predefined examples
    demonstrate_palindrome_checking()
    
    # Interactive checker
    interactive_palindrome_checker()
    
    print("\nThank you for using the Palindrome Checker!")

if __name__ == "__main__":
    main()