Introduction to Stacks and Queues

---

Stack

---

A stack is an ordered list (Data Structure) in which all insertion and deletion are done at one end. It is a First In Last Out (FILO). Top is a pointer pointing to the top most element of the stack.

Applications of Stack

1. Recursion
2. Post fix evaluation of expression
3. infix to prefix/postfix
4. Tower of Hanoi
5. Fibonacci sequence and series
6. Permutation
7. Symbol balancing

Stack Operations

Operations related to a Stack Data Structure are : PUSH(), POP(), IsEmpty(), IsFull() etc.

Let S be the stack, N be max stack size and item be the element to be inserted.

Push:

push (S, Top, N, item){

    // is_full check
    if (Top == N-1){
        printf("Stack Overflow");
        exit(1);
    }

    Top++;
    S[Top] = item;
}

Pop:

pop (S, Top, N){
    int temp;

    // is_empty check
    if (Top == -1){
        printf("UnderFlow or Stack is Empty");
        exit(1);
    }

    temp = S[Top];
    Top --;
    return temp;

}

---

Queue

---

It is First-In-First-Out(FIFO). Item which gets in first gets out first. Insertion side is Rear and Deletion side is Front.

Applications of Queue

1. Multi-programming in OS
2. CPU Scheduling in OS
3. Breadth First Search Algorithm
4. Prefix expressions evaluation

Types of Queue

1. Single ended: Insertion at one and deletion at other end.
2. Double ended: Insertion and deletion on both the ends
3. Priority Queue: Serve elements a/c to the priority assigned to them.
4. Restricted Queue: Restrictions only on one end i.e, either on insertion or deletion

Queue Operations

Operations on queue are Enqueue(Insertion) and Dequeue(Deletion).

Implementation of a queue – using two Stacks.

Enqueue:

enqueue(Q, N, front, rear, item){

    // is_full check
    if ((front==0 && rear==N-1) or (rear==front-1)){
        printf("Queue Overflow or Queue is Full");
        exit(1);
    }

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

    Q[rear] = item;
    exit(1);
}

Dequeue:

dequeue(Q, N, front, rear){

    // is_empty check
    if (front == -1){
        printf("Queue is Empty or Underflow");
        exit(1);
    }

    item = Q[front];

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

    exit(1);
}

---