<h1
style="
display: flex;
align-items: center;
justify-content: center;"
>
DSaA Lab 5 - Stacks and Queues
</h1>

<h4 style="text-align: center;">
The Islamic University of Gaza<br>
Engineering Faculty<br>
Department of Computer Engineering
</h4>

<font color="#ec53c4">
Prepared by:
Eng. Ahmad Albarasy
</font>
<br>
<font color="#ec53c4">
Under the supervision of:
Prof. Ahmad Mahdi
</font>

---

In this lab, we are going to explore stacks and queues, which are two fundemental linear data structures used to organize data in two different fashions, leading to each one being suitable for solving a distinct set of problems. We will also learn about and compare the different ways of implementing them.

## What is an ADT?

**An Abstract Data Type** is a mathematical model for a data structure that specifies what operations can be performed on the data and what their expected behavior is, without specifying how the data or operations are implemented.

In Java, we use interfaces to define the expected behavior of a data structure without specifying its implemenation. For instace, take a look at the [List](https://docs.oracle.com/javase/8/docs/api/java/util/List.html) interface in Java, which is used to represent an ordered collection of elements.

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/S1P-mTa-bl.png" alt="image">
</div>

## The Stack

A stack is a linear data structure that follows the **LIFO (Last-In, First-Out)** principle, where the last element that's pushed onto the stack is the first element that gets removed. A real world analogy would be a pile of plates placed on top of each other, where you can only place or remove plates from the top.

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/B1G0vnaZZg.png" alt="image">
</div>

### The Stack ADT

/*
 * A collection of objects that are inserted and removed 
 * according to the last-in first-out principle.
 * Although similar in purpose, this interface differs from
 ∗ java.util.Stack
 */
public interface Stack<E> {
  /* returns the number of elements in the stack */
  int size();
  /* return true if the stack is empty, false otherwise */
  boolean isEmpty();
  /* returns the top element without removing it (or null if empty) */
  E top();
  /* pushes an element on top of the stack */
  void push(E element);
  /* removes and returns the top element (or null if empty)*/
  E pop();
}

### Implementation

To implement a stack, we commonly rely on two fundamental data structures: either an array or a linked list. Each implementation comes with its own advantages and disadvantages, and your choice will heavily rely on the nature of the problem you are trying to solve.

For instance, an array-based implementation would be inefficient in cases where the size of the stack grows over time, as that would be expensive due to the cost of resizing the array (moving all elements to the new larger one). On the contrary, a linked list-based implementation would allow the stack to grow and shrink dynamically with no need for resizing, but it introduces an additional memory overhead due to the storage of pointers.

#### Array-based Implementation

public class ArrayStack<E> implements Stack<E> {
  public static final int CAPACITY = 1000; // default array capacity
  private E[] data; // generic array used for storage
  private int t = -1; // index of the top element in stack

  public ArrayStack() {
    this(CAPACITY); // constructs stack with default capacity
  }

  public ArrayStack(int capacity) { // constructs stack with given capacity
    data = (E[]) new Object[capacity]; // safe cast; compiler may give warning
  }

  public int size() {
    return t + 1;
  }

  public boolean isEmpty() {
    return t == -1;
  }

  public void push(E e) throws IllegalStateException {
    if (size() == data.length) throw new IllegalStateException("Stack is full");
    data[++t] = e; // increment t before storing new item
  }

  public E top() {
    if (isEmpty()) return null;
    return data[t];
  }

  public E pop() {
    if (isEmpty()) return null;
    E answer = data[t];
    data[t] = null; // dereference to help garbage collection
    t--;
    return answer;
  }
}

#### Linked List-based Implementation

public class LinkedStack<E> implements Stack<E> {
  private SinglyLinkedList<E> list = new SinglyLinkedList<>(); // an empty list

  public LinkedStack() {
    // new stack relies on the initially empty list
  }

  public int size() {
    return list.size();
  }

  public boolean isEmpty() {
    return list.isEmpty();
  }

  public void push(E element) {
    list.addFirst(element);
  }

  public E top() {
    return list.first();
  }

  public E pop() {
    return list.removeFirst();
  }
}

### Usage

Stacks are widely used due to their simple **FIFO** storage fashion, which makes them ideal for problems where the most recent item needs to be processed first. Some common applications of stacks include:

1. **Undo/Redo operations in editors:** Programs like text editors use stacks to keep track of user actions. When the user performs an action, it is pushed onto the undo stack. If the user presses Undo, the action is popped from the undo stack and pushed onto a redo stack, allowing it to be redone later:

import java.util.Stack;

Stack<Action> undoStack = new Stack<>();
Stack<Action> redoStack = new Stack<>();

void perform(Action a) {
  a.apply();
  undoStack.push(a);
  redoStack.clear();
}

void undo() {
  if (!undoStack.isEmpty()) {
    Action a = undoStack.pop();
    a.reverse();
    redoStack.push(a);
  }
}

void redo() {
  if (!redoStack.isEmpty()) {
    Action a = redoStack.pop();
    a.apply();
    undoStack.push(a);
  }
}

2. **Naive path finding algorithms:** A stack can be used to keep track of the positions to explore when implementing a simple path-finding algorithm. For instance, the following algorithm explores a maze and finds the exit by backtracking whenever it reaches a dead end:

import java.util.Stack;

class Position {
  int row, col;
  Position(int r, int c) { row = r; col = c; }
}

public class MazeSolver {

  public static boolean simpleMazeSolver(int[][] maze) {
    int rows = maze.length;
    int cols = maze[0].length;

    Stack<Position> stack = new Stack<>();
    stack.push(new Position(0, 0)); // start at top-left
    boolean[][] visited = new boolean[rows][cols];

    while (!stack.isEmpty()) {
      Position p = stack.pop();
      int r = p.row;
      int c = p.col;

      // Check boundaries, walls, and visited cells
      if (r < 0 || r >= rows || c < 0 || c >= cols) continue;
      if (maze[r][c] == 1 || visited[r][c]) continue;

      visited[r][c] = true;

      printMaze(maze, p);

      // Check if we reached the exit (bottom-right)
      if (r == rows - 1 && c == cols - 1) {
        System.out.println("Maze solved!");
        return true;
      }

      // Push adjacent positions (up, down, left, right)
      stack.push(new Position(r + 1, c));
      stack.push(new Position(r - 1, c));
      stack.push(new Position(r, c + 1));
      stack.push(new Position(r, c - 1));
    }

    System.out.println("No path found.");
    return false;
  }

  public static void printMaze(int [][] maze, Position p){
    for(int i = 0; i < maze.length; i++){
      for(int j = 0; j < maze[0].length; j++){
        if(i == p.row && j == p.col)
          System.out.print("m "); // indicates current position
        else
          System.out.print(maze[i][j] + " ");
      }
      System.out.println(); // end of row
    }
    System.out.println(); // end of grid
  }
  
  public static void main(String[] args) {
    // 0 = path, 1 = wall/block
    int[][] maze = {
      {0, 0, 1, 0},
      {1, 0, 1, 0},
      {0, 0, 0, 1},
      {0, 1, 0, 0}
    };

    simpleMazeSolver(maze);
  }
}

## The Queue

A queue is a linear data structure that follows the **FIFO (First-In, First-Out) principle**, where the first element that’s added to the queue is the first element that gets removed. A real-world analogy would be people standing in line, where the person who arrives first is the first one to be served.

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/rJZIVXXG-g.png" alt="image">
</div>

### The Queue ADT:

/*
 * A collection of objects that are inserted and removed 
 * according to the first-in first-out principle.
 * Although similar in purpose, this interface  
 * slightly differs from java.util.Queue
 */

public interface Queue<E> {
  /** Returns the number of elements in the queue. */
  int size();

  /** Tests whether the queue is empty. */
  boolean isEmpty();

  /** Inserts an element at the rear of the queue. */
  void enqueue(E e);

  /** Returns, but does not remove,
   * the first element of the queue (null if empty).
   */
  E first();

  /** Removes and returns the first element of the queue (null if empty). */
  E dequeue();
}

### Implementation

To implement a queue, we also have 2 options: either implementing it using an array of a linked list. The choice depends on the nature of the problem we are trying to solve, as each option comes with its own advantages and disadvantages.

An array-based implementation is relatively simple and offers constant access times, but it may require resizing as our queue grows in size and careful index management are needed. On the other hand, a linked list–based implementation provides more flexibility in size and avoids resizing, though it uses extra memory due to additional pointers.

#### Array-based Implementation

/** Implementation of the queue ADT using a fixed-length array. */
public class ArrayQueue<E> implements Queue<E> {

  // instance variables
  private E[] data;   // generic array used for storage
  private int f = 0;  // index of the front element
  private int sz = 0; // current number of elements

  // constructors
  public ArrayQueue() {
    this(CAPACITY);
  }

  public ArrayQueue(int capacity) {
    data = (E[]) new Object[capacity]; // safe cast; compiler may give warning
  }

  // methods

  /** Returns the number of elements in the queue. */
  public int size() {
    return sz;
  }

  /** Tests whether the queue is empty. */
  public boolean isEmpty() {
    return (sz == 0);
  }

  /** Inserts an element at the rear of the queue. */
  public void enqueue(E e) throws IllegalStateException {
    if (sz == data.length)
      throw new IllegalStateException("Queue is full");
    int avail = (f + sz) % data.length; // use modular arithmetic
    data[avail] = e;
    sz++;
  }

  /** Returns, but does not remove,
   * the first element of the queue (null if empty).*/
  public E first() {
    if (isEmpty())
      return null;
    return data[f];
  }

  /** Removes and returns the first element of the queue (null if empty). */
  public E dequeue() {
    if (isEmpty())
      return null;
    E answer = data[f];
    data[f] = null; // dereference to help garbage collection
    f = (f + 1) % data.length;
    sz--;
    return answer;
  }
}

#### Linked List-based Implementation

/** Realization of a FIFO queue as an adaptation of a SinglyLinkedList. */

public class LinkedQueue<E> implements Queue<E> {

  private LinkedList<E> list = new SinglyLinkedList<>(); // an empty list

  public LinkedQueue() {
  } // new queue relies on the initially empty list

  public int size() {
    return list.size();
  }

  public boolean isEmpty() {
    return list.isEmpty();
  }

  public void enqueue(E element) {
    list.addLast(element);
  }

  public E first() {
    return list.first();
  }

  public E dequeue() {
    return list.removeFirst();
  }
}

### Usage
Queues are used in a variety of problems where data need to processed in the exact order in which they arrive. This is useful in situations where requests or tasks should be processed fairly, one after another, without skipping earlier ones. Some common applications of queues include:

1. **Buffering arriving packets in a router:** When a router receives network packets faster than it can process or forward them, the packets are temporarily stored in a queue. Packets are then forwarded in the order they arrive, ensuring organized and fair handling of network traffic.

2. **Server joining queues in multiplayer games:** Queues are used in online games multiplayer servers to moderate the number of players currently in the server to prevent overloading it. Players who requested to join the server while full are placed in a wait queue and are allowed in once someone leaves the server, thus making room for others to join.

## Tasks

### Task 1 (4 points)

You are given a string `s`.

Your task is to remove all digits by doing this operation repeatedly:

Question link on [LeetCode](https://leetcode.com/problems/clear-digits/)

* Delete the first digit and the closest non-digit character to its left.
Return the resulting string after removing all digits.

**Note** that the operation cannot be performed on a digit that does not have any non-digit character to its left.

Example 1:

> Input: s = `"abc"`
> Output: `"abc"`
> Explanation:
> There is no digit in the string.

Example 2:

>Input: s = `"cb34"`
>Output: `""`
>Explanation:
>First, we apply the operation on `s[2]`, and `s` becomes `"c4"`.
>Then we apply the operation on `s[1]`, and s becomes `""`.

**Constraints:**

* `1` <= `s.length` <= `100`
* `s` consists only of lowercase English letters and digits.
* The input is generated such that it is possible to delete all digits.

---

### Task 2 (6 points)

Implement a **last-in-first-out (LIFO)** stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Question link on [LeetCode](https://leetcode.com/problems/implement-stack-using-queues/)

Implement the `MyStack` class:

* `void push(int x)` Pushes element x to the top of the stack.
* `int pop()` Removes the element on the top of the stack and returns it.
* `int top()` Returns the element on the top of the stack.
* `boolean empty()` Returns `true` if the stack is empty, `false` otherwise.

**Notes:**

* You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
* Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

**Constraints:**

* `1` <= `x` <= `9`
* At most 100 calls will be made to `push`, `pop`, `top`, and `empty`.
* All the calls to `pop` and `top` are valid.

---
### Tasks Submission Guide

You will solve both problems on LeetCode and you have to make sure that your solution passes all test cases and that LeetCode accepts it. Once you are done, its time to submit your solution on GradeScope.

Firstly, make sure to submit **only** two files:
**1. TaskOne.java**
**2. MyStack.java**

Secondly, for each question, you have to follow these steps to make sure GradeScope's autograder runs without issues:

#### For Task 1:

1. Copy your whole solution into a file named `TaskOne.java`
2. Change the class name from `Solution` to `TaskOne`, and make sure that the class is public
3. add the following package identifier to the beginning of the file, make sure to copy it and **don't write it manually to avoid typos**:

package com.gradescope.labFive;

Here's an example solution for reference:

package com.gradescope.labFive;

public class TaskOne {
    public String clearDigits(String s) {
        // your solution here
    }
    /* if any helper methods are needed, make sure to include them */
}

#### For Task 2:

1. Copy your whole solution into a file named `MyStack.java`
2. Make sure that the class is public and named `MyStack`
3. add the following package identifier to the beginning of the file, make sure to copy it and **don't write it manually to avoid typos**:

package com.gradescope.labFive;

Here's an example solution for reference:

package com.gradescope.labFive;

public class MyStack {

    public MyStack() {
        // your implementation goes here
    }
    
    public void push(int x) {
        // your implementation goes here
    }
    
    public int pop() {
        // your implementation goes here
    }
    
    public int top() {
        // your implementation goes here
    }
    
    public boolean empty() {
        // your implementation goes here
    }
}

---

<div
style="display: flex;
align-items: center;
justify-content: center;"
>
Happy Coding 🙂
</div>