# Understanding Data Structures and Algorithms: Week 1 (Stack, Queue, and List)

## Introduction

Data Structures and Algorithms (DSA) form the backbone of computer science and software development. Programming ultimately relies on it. Mastering DSA is essential to solving problems effectively and writing optimized code.

This article introduces the fundamentals of DSA and focuses on three foundational linear data structures: Stack, Queue, and List. We will explore how data is added and accessed within these structures, and examine the time complexity of their core operations.

## What is a Data Structure?

A data structure is a particular way of organizing and storing data in a computer so that it can be used efficiently. Different data structures are suited for different types of applications, and some are highly specialized for specific tasks.

## What is an Algorithm?

An algorithm is a finite, well-defined sequence of steps used to perform a task or solve a problem. Algorithms are used to manipulate data stored in data structures—searching, sorting, inserting, deleting, and more.

## Stack

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means the most recently added element is the first to be removed. Data is always added and removed from the same end, known as the "top" of the stack.

In a stack, data entry happens at the top. When you push an item onto the stack, it becomes the new top. When you pop an item from the stack, the current top element is removed and the one below it becomes the new top. This makes stack operations highly predictable and suitable for scenarios like undo functionality, backtracking algorithms, and expression evaluation.

**Time Complexity of Queue Operations:**
A stack is just like an array, Stack operations are generally very efficient. Most stack operations, such as adding an element (push), removing the top element (pop), and checking the top element (peek), all run in constant time O(1). This makes the stack a reliable choice for problems that require quick access to the most recently added data without needing to traverse the structure.

class Stack {

    constructor(){
            this.items = []
            this.length = 0
            this.undoStack = []
            this.redoStack = []
    }

    push(item){
        this.items[this.length] = item
        this.length += 1

        return this.items
    }

    pop(){
        if(this.isEmpty()) return undefined
        
        const item = this.items[this.length-1]
        delete this.items[this.length -1]
        this.length -= 1

        return item
    }

    print(){
        
        let output = this.items.forEach(item => console.log(`${item}  \n`))

        return output
    }

    size(){
        return this.length
    }

    isEmpty(){
        return this.length=== 0  
    }

    clear(){
        this.items = []
        this.length = 0
    }

    undo(){
        
    }
}

const stack = new Stack()

## Queue

A queue is a linear data structure that follows the the First In, First Out (FIFO) principle. The element that is added first will be removed first. Data is entered at the rear and removed from the front.

When an element is enqueued, it is placed at the end of the queue. To retrieve or remove data, the operation always happens at the front. This ensures that the order of processing is maintained. Queues are widely used in scheduling algorithms, task management systems etc.

**Time Complexity of Queue Operations:**
Queue operations typically run in constant time, especially when implemented efficiently. Insertion at the rear (enqueue) and removal from the front (dequeue) both operate in O(1) time under most implementations, making queues suitable for systems where processing order matters.

Example in JavaScript:

class Queue {
  constructor() {
    this.items = [];
    this.front = 0;
    this.back = 0;
  }

  enqueue(item) {
    this.items[this.back] = item;
    this.back += 1;

    return item;
  }

  dequeue() {
    let item = this.items[this.front];
    delete this.items[this.front];
    this.front += 1;

    return item;
  }

  print() {
    let output = "";
    let seperator = "";

    for (let i = this.front; i < this.back; i++) {
      output += "<--" + this.items[i];
    }
    return output;
  }

  isEmpty(){
    return this.front == this.back
  }

  size(){
    return this.back - this.front
  }

  first(){
    return this.items[this.front]
  }
}

const sms = new Queue();

## List (Linked List)

A linked list is a linear data structure in which elements, called nodes, are linked using pointers. Each node contains two parts: the data and a reference (or pointer) to the next node in the sequence. Unlike arrays, linked lists do not use contiguous memory locations and can grow or shrink dynamically.

In a singly linked list, each node points only to the next node. In a doubly linked list, each node also points to the previous node, allowing bidirectional traversal and in a circular linked list, the first item points to the last and the last points to the first.

**Time Complexity of Linked List Operations:**

In general, linked lists provide constant time complexity O(n) for insertions and deletions at the beginning of the list. However, access time for a specific element and search operations are linear in complexity O(n), meaning they become slower as the list grows in size.

Example in JavaScript:

class PlayList {
  constructor() {
    this.playList = [];
    this.currentSong = 0;
    this.isPlaying = false;
  }

  addPlaylist(title, artist) {
    const added = {
      artist,
      title,
    };

    this.playList.push(added);

    return `${added.title} by ${added.artist} was added to playlist`;
  }

  play(index) {

    if(this.playList.length === 0){
        return 'no song to play'
    }

    if (index) {
        this.currentSong = index
        this.isPlaying = true
      return this.playList[index];
      
      
    }

    return this.playList[this.currentSong];
  }

  stop() {
    if(this.playList.length === 0){
        return 'no song in playlist'
    }
    if(this.isPlaying == true){
return this.playList[this.currentSong];
    }else{
return 'no song playing';

    }

    
  } 


  next(){
    if(this.playList.length === 0){
        return 'no song to play'
    }

    this.currentSong += 1;

    if(this.currentSong == this.playList.length){
        this.currentSong = 0

        return this.playList[this.currentSong]
    }

    return this.playList[this.currentSong];
  }

  prev() {
    if(this.playList.length === 0){
        return 'no song to play'
    }
    this.currentSong -= 1;

    if(this.currentSong == 0){
        this.currentSong = this.playList.length -1

        return this.playList[this.currentSong]
    }

    return this.playList[this.currentSong];
  }
}

const music = new PlayList();

## Conclusion

Week-1 of cohort3 of the Blockfuse labs web£ programm has opened my mind to Understanding how data structures handle data input and access and how it is critical for writing efficient software. Stacks, queues, and linked lists are foundational structures that every developer should be familiar with. Each has its own set of principles regarding how data is entered, stored, and retrieved. Learning these concepts well provides a solid base for exploring more advanced algorithms and structures in programming.