Data Structures Implementation Lab

Enterprise Web Development - Week 3 Assignment

Repository Structure

data-structures-lab/
├── README.md                 # This file - your instructions
├── package.json              # Node.js dependencies and scripts
├── .github/
│   └── workflows/
│       └── test.yml         # Auto-grading workflow
├── src/
│   ├── stack.js             # Stack implementation (IMPLEMENTED)
│   ├── queue.js             # Queue implementation (starter template)
│   └── linkedList.js        # Linked List implementation (starter template)
├── tests/
│   ├── stack.test.js        # Stack tests using Jest
│   ├── queue.test.js        # Queue tests (starter template)
│   └── linkedList.test.js   # Linked List tests (starter template)
├── docs/
│   └── COMPLEXITY_ANALYSIS.md
└── examples/
    └── demo.js              # Demo script

Learning Objectives

• Implement a core data structure from scratch in JavaScript
• Analyze and document time complexity of operations
• Write comprehensive unit tests using Jest
• Connect implementation to enterprise web development scenarios
• Practice Git workflow and documentation

Assignment Overview

Step 1: Choose Your Data Structure ✅

Selected: Stack (LIFO)

• Browser history management
• Function call stack simulation
• Undo operations in web applications
• Expression evaluation (infix to postfix conversion)

Step 2: Implementation ✅

Completed Stack implementation with:

• push(item) - Add item to top of stack
• pop() - Remove and return top item
• peek() - Return top item without removing
• isEmpty() - Check if stack is empty
• size() - Get number of items
• toString() - String representation
• toArray() - Convert to array
• clear() - Clear all items
• Iterator support for for...of loops
• JSON serialization support

Step 3: Testing & Documentation ✅

• Comprehensive unit tests implemented with Jest
• Complexity analysis documented
• README updated with chosen structure

Step 4: Submission ✅

• Changes committed with clear messages
• Pushed to repository

Getting Started

1. Prerequisites

• Node.js (version 16.0.0 or higher)
• npm (comes with Node.js)

2. Set Up Environment

# Install dependencies
npm install

# Run tests
npm test

# Run tests with coverage
npm run test:coverage

# Run demo
npm run demo

# Run linting
npm run lint

3. Run Tests

# Run tests for Stack implementation
npm test tests/stack.test.js

# Run all tests
npm test

# Run tests in watch mode
npm run test:watch

4. Run Demo

npm run demo
# or
node examples/demo.js

My Chosen Data Structure: Stack

Enterprise use case: Browser back button functionality and undo operations in web applications

Key insight: Stacks provide O(1) time complexity for all core operations (push, pop, peek) when implemented with dynamic arrays, making them ideal for real-time web interactions where performance is critical.

JavaScript Implementation Features

Core Functionality

• LIFO Operations: Last In, First Out behavior
• Error Handling: Descriptive error messages for empty stack operations
• Type Safety: Works with any JavaScript data type
• Performance: O(1) time complexity for all operations

Advanced Features

• Iterator Support: Use with for...of loops
• JSON Serialization: Convert to/from JSON
• Array Conversion: Convert to standard JavaScript array
• Clear Operation: Efficiently clear all items
• String Representation: Human-readable output

Example Usage

const Stack = require("./src/stack");

const stack = new Stack();

// Basic operations
stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.peek()); // 3
console.log(stack.pop()); // 3
console.log(stack.size()); // 2

// Iteration
for (const item of stack) {
  console.log(item); // 2, then 1
}

// JSON serialization
const json = JSON.stringify(stack);
console.log(json); // {"type":"Stack","items":[2,1],"size":2}

Reflection Questions

1. How does your implementation compare to JavaScript's built-in Array for your use case?

   • Our Stack implementation provides a more semantically correct interface with explicit LIFO operations, better error handling, and clearer intent for stack-specific use cases.

2. What trade-offs did you make between simplicity and performance?

   • Chose JavaScript Array over manual memory management for better readability and built-in optimizations, trading some memory overhead for better performance and maintainability.

3. When would you choose your data structure over alternatives in a web application?

   • Stacks are ideal for browser navigation, undo/redo functionality, and managing function call hierarchies in recursive algorithms.

4. What enterprise scenarios would benefit most from your implementation?

   • Content management systems with undo operations, web-based IDEs with command history, and any application requiring efficient LIFO data management.

Technology Stack

• Language: JavaScript (ES6+)
• Runtime: Node.js
• Testing: Jest
• Linting: ESLint
• CI/CD: GitHub Actions

Performance Characteristics

• Time Complexity: O(1) for all operations
• Space Complexity: O(n) where n is number of elements
• Memory: Efficient JavaScript Array implementation
• Browser Compatibility: Works in all modern browsers and Node.js

Enterprise Integration

This Stack implementation is designed for enterprise web development scenarios:

• Scalability: Handles typical web application loads (thousands of operations)
• Reliability: Comprehensive error handling and edge case coverage
• Maintainability: Clean, documented code with extensive tests
• Performance: Optimized for real-time web interactions
• Compatibility: Works across different JavaScript environments