Assignment: Stack and Queue

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

#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:

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

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

#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:

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

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.

#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.

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.