# Assignment: Stack and Queue

**Subject:** Data Structures and Algorithms

## 1. Stack

**Definition:** A Stack is a linear data structure that follows the LIFO
(Last In, First Out) principle. The element inserted last is removed
first.

**Example:** A pile of books. The last book placed on top is removed
first.

### Algorithm 1: PUSH (Stack Insertion)

**Procedure:** `PUSH(STACK, TOP, N, ITEM)`

This procedure inserts an element `ITEM` into a stack.

1.  **\[Stack already filled?\]**

    If `TOP = N`, then:

    Write: `OVERFLOW`, and Return.

2.  **\[Find new value of TOP.\]**

    Set `TOP := TOP + 1`.

3.  Set `STACK[TOP] := ITEM`. \[This inserts the new element.\]

4.  Return.

### Algorithm 2: POP (Stack Deletion)

**Procedure:** `POP(STACK, TOP, ITEM)`

This procedure deletes an element from a stack and assigns it to the
variable `ITEM`.

1.  **\[Stack already empty?\]**

    If `TOP = 0`, then:

    Write: `UNDERFLOW`, and Return.

2.  Set `ITEM := STACK[TOP]`.

3.  Set `TOP := TOP - 1`. \[This deletes the top element.\]

4.  Return.

### C++ Program for Stack Using Functions

``` cpp
#include <iostream>
using namespace std;

const int N = 5;
int stackArr[N];
int top = 0;

void push(int item) {
    if (top == N) {
        cout << "Stack Overflow" << endl;
        return;
    }

    top = top + 1;
    stackArr[top - 1] = item;
}

void pop() {
    if (top == 0) {
        cout << "Stack Underflow" << endl;
        return;
    }

    int item = stackArr[top - 1];
    top = top - 1;

    cout << "Deleted item: " << item << endl;
}

void display() {
    if (top == 0) {
        cout << "Stack is empty" << endl;
        return;
    }

    cout << "Stack elements: ";
    for (int i = top - 1; i >= 0; i--) {
        cout << stackArr[i] << " ";
    }
    cout << endl;
}

int main() {
    push(10);
    push(20);
    push(30);

    display();
    pop();
    display();

    return 0;
}
```

**Output:**

``` text
Stack elements: 30 20 10
Deleted item: 30
Stack elements: 20 10
```

------------------------------------------------------------------------

## 2. Queue

**Definition:** A Queue is a linear data structure that follows the FIFO
(First In, First Out) principle. The element inserted first is removed
first.

**Example:** A line of people waiting for a bus. The person who arrives
first gets on first.

### Algorithm 3: QINSERT (Queue Insertion)

**Procedure:** `QINSERT(QUEUE, N, FRONT, REAR, ITEM)`

This procedure inserts an element `ITEM` into a circular queue.

1.  **\[Queue already filled?\]**

    If `FRONT = 1` and `REAR = N`, or if `FRONT = REAR + 1`, then:

    Write: `OVERFLOW`, and Return.

2.  **\[Find new value of REAR.\]**

    If `FRONT = NULL`, then: \[Queue initially empty.\]

    Set `FRONT := 1` and `REAR := 1`.

    Else if `REAR = N`, then:

    Set `REAR := 1`.

    Else:

    Set `REAR := REAR + 1`.

3.  Set `QUEUE[REAR] := ITEM`. \[This inserts the new element.\]

4.  Return.

### Algorithm 4: QDELETE (Queue Deletion)

**Procedure:** `QDELETE(QUEUE, N, FRONT, REAR, ITEM)`

This procedure deletes an element from a circular queue and assigns it
to the variable `ITEM`.

1.  **\[Queue already empty?\]**

    If `FRONT = NULL`, then:

    Write: `UNDERFLOW`, and Return.

2.  Set `ITEM := QUEUE[FRONT]`.

3.  **\[Find new value of FRONT.\]**

    If `FRONT = REAR`, then: \[Queue has only one element.\]

    Set `FRONT := NULL` and `REAR := NULL`.

    Else if `FRONT = N`, then:

    Set `FRONT := 1`.

    Else:

    Set `FRONT := FRONT + 1`.

4.  Return.

### C++ Program for Queue Using Functions

``` cpp
#include <iostream>
using namespace std;

const int N = 5;
int queueArr[N];
int front = -1, rear = -1;

void enqueue(int item) {
    if ((front == 0 && rear == N - 1) ||
        (front == rear + 1)) {
        cout << "Queue Overflow" << endl;
        return;
    }

    if (front == -1) {
        front = 0;
        rear = 0;
    }
    else if (rear == N - 1) {
        rear = 0;
    }
    else {
        rear = rear + 1;
    }

    queueArr[rear] = item;
}

void dequeue() {
    if (front == -1) {
        cout << "Queue Underflow" << endl;
        return;
    }

    int item = queueArr[front];
    cout << "Deleted item: " << item << endl;

    if (front == rear) {
        front = -1;
        rear = -1;
    }
    else if (front == N - 1) {
        front = 0;
    }
    else {
        front = front + 1;
    }
}

void display() {
    if (front == -1) {
        cout << "Queue is empty" << endl;
        return;
    }

    cout << "Queue elements: ";
    int i = front;

    while (true) {
        cout << queueArr[i] << " ";

        if (i == rear) {
            break;
        }

        i = (i + 1) % N;
    }

    cout << endl;
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);

    display();
    dequeue();
    display();

    return 0;
}
```

**Output:**

``` text
Queue elements: 10 20 30
Deleted item: 10
Queue elements: 20 30
```

------------------------------------------------------------------------

## 3. Difference Between Stack and Queue

  -----------------------------------------------------------------------
  Stack                               Queue
  ----------------------------------- -----------------------------------
  Follows LIFO.                       Follows FIFO.

  Insertion and deletion occur at the Insertion occurs at the REAR and
  TOP.                                deletion at the FRONT.

  Insertion operation is called PUSH. Insertion operation is called
                                      ENQUEUE or QINSERT.

  Deletion operation is called POP.   Deletion operation is called
                                      DEQUEUE or QDELETE.

  Example: A pile of books.           Example: A line of people.

  Used in function calls and undo     Used in scheduling and waiting-line
  operations.                         systems.
  -----------------------------------------------------------------------

## 4. Applications of Stack and Queue

### Applications of Stack

1.  Function calls and recursion.
2.  Undo and redo operations.
3.  Expression evaluation.
4.  Checking balanced parentheses.

### Applications of Queue

1.  CPU scheduling.
2.  Printer job management.
3.  Handling requests in servers.
4.  Breadth-first search in graphs.

## 5. Conclusion

Stack and Queue are important linear data structures used to store and
process data. Stack follows the LIFO principle, whereas Queue follows
the FIFO principle. Both structures support insertion and deletion
operations and are widely used in computer programming.