Topics - [Queue]- [Stack]

Queue

A Queue Data Structure is a fundamental concept in computer science used for storing and managing data in a specific order. It follows the principle of “First in, First out” (FIFO), where the first element added to the queue is the first one to be removed.

In order to understand it in a simple manner we can visualize a counter line in a shopping mall . We can see that the 1st person in the line leaves the line first and the person who join the line last will leave the line last. This methodology defines the term “First in, First out” (FIFO),

Structure of a Queue:

1. A queue can be defined as an ordered list which enables insert operations to be performed at one end called REAR and delete operations to be performed at another end called FRONT.

2. Queue is referred to be as First In First Out list.

3. For example, people waiting in line for a rail ticket form a queue.

Applications of Queue:

1. Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.

2. Queues are used in asynchronous transfer of data (where data is not being transferred at the same rate between two processes) for eg. pipes, file IO, sockets.

3. Queues are used as buffers in most of the applications like MP3 media player, CD player, etc.

4. Queue are used to maintain the play list in media players in order to add and remove the songs from the play-list.

5. Queues are used in operating systems for handling interrupts.

Types of Queue

• Simple Queue or Linear Queue

• Circular Queue

• Priority Queue

• Double Ended Queue (or Deque)

  Simple Queue or Linear Queue

  In Linear Queue, an insertion takes place from one end while the deletion occurs from another end. The end at which the insertion takes place is known as the rear end, and the end at which the deletion takes place is known as front end. It strictly follows the FIFO rule.

  

  Circular Queue

  In Circular Queue, all the nodes are represented as circular. It is similar to the linear Queue except that the last element of the queue is connected to the first element. It is also known as Ring Buffer, as all the ends are connected to another end. The representation of circular queue is shown in the below image -

  

  Priority Queue

  It is a special type of queue in which the elements are arranged based on the priority. It is a special type of queue data structure in which every element has a priority associated with it.

  Suppose some elements occur with the same priority, they will be arranged according to the FIFO principle. The representation of priority queue is shown in the below image -

  

  Deque (or, Double Ended Queue)

  In Deque or Double Ended Queue, insertion and deletion can be done from both ends of the queue either from the front or rear. It means that we can insert and delete elements from both front and rear ends of the queue. Deque can be used as a palindrome checker means that if we read the string from both ends, then the string would be the same.

  Deque can be used both as stack and queue as it allows the insertion and deletion operations on both ends. Deque can be considered as stack because stack follows the LIFO (Last In First Out) principle in which insertion and deletion both can be performed only from one end. And in deque, it is possible to perform both insertion and deletion from one end, and Deque does not follow the FIFO principle.

  

Implementation of Queue In C

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

typedef struct {
    int data[MAX];
    int front;
    int rear;
} Queue;

void initializeQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

int isFull(Queue *q) {
    return q->rear == MAX - 1;
}

int isEmpty(Queue *q) {
    return q->front == -1 || q->front > q->rear;
}

void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full. Cannot enqueue %d\n", value);
        return;
    }
    if (q->front == -1) {
        q->front = 0;
    }
    q->data[++q->rear] = value;
    printf("%d enqueued to queue\n", value);
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty. Cannot dequeue\n");
        return -1;
    }
    int value = q->data[q->front++];
    if (q->front > q->rear) {
        q->front = q->rear = -1; // Reset queue if empty
    }
    printf("%d dequeued from queue\n", value);
    return value;
}

void displayQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return;
    }
    printf("Queue elements: ");
    for (int i = q->front; i <= q->rear; i++) {
        printf("%d ", q->data[i]);
    }
    printf("\n");
}

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    displayQueue(&q);

    dequeue(&q);
    displayQueue(&q);

    enqueue(&q, 40);
    displayQueue(&q);

    return 0;
}

Stack

A Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). LIFO implies that the element that is inserted last, comes out first and FILO implies that the element that is inserted first, comes out last.

In order to understand the stack data structure we can take a example of a bucket fill with plates one after one if we want to remove the bottom most plate in the bucket we have to remove the top most plate in the Bucket. Here the bottom most plate in the bucket is the first plate which is put in the bucket and top most plate in the bucket is the last plate added in the bucket. This condition represent the situation of LIFO(Last In First Out) or FILO(First In Last Out).

Basic operations performed in a Stack

• Push: Add an element to the top of a stack

• Pop: Remove an element from the top of a stack

• IsEmpty: Check if the stack is empty

• IsFull: Check if the stack is full

• Peek: Get the value of the top element without removing it

Working of Stack

The operations work as follows:

1. A pointer called TOP is used to keep track of the top element in the stack.

2. When initializing the stack, we set its value to -1 so that we can check if the stack is empty by comparing TOP == -1.

3. On pushing an element, we increase the value of TOP and place the new element in the position pointed to by TOP.

4. On popping an element, we return the element pointed to by TOP and reduce its value.

5. Before pushing, we check if the stack is already full

6. Before popping, we check if the stack is already empty

   

Stack Implementation

// Stack implementation in C

#include <stdio.h>
#include <stdlib.h>

#define MAX 10

int count = 0;

// Creating a stack
struct stack {
  int items[MAX];
  int top;
};
typedef struct stack st;

void createEmptyStack(st *s) {
  s->top = -1;
}

// Check if the stack is full
int isfull(st *s) {
  if (s->top == MAX - 1)
    return 1;
  else
    return 0;
}

// Check if the stack is empty
int isempty(st *s) {
  if (s->top == -1)
    return 1;
  else
    return 0;
}

// Add elements into stack
void push(st *s, int newitem) {
  if (isfull(s)) {
    printf("STACK FULL");
  } else {
    s->top++;
    s->items[s->top] = newitem;
  }
  count++;
}

// Remove element from stack
void pop(st *s) {
  if (isempty(s)) {
    printf("\n STACK EMPTY \n");
  } else {
    printf("Item popped= %d", s->items[s->top]);
    s->top--;
  }
  count--;
  printf("\n");
}

// Print elements of stack
void printStack(st *s) {
  printf("Stack: ");
  for (int i = 0; i < count; i++) {
    printf("%d ", s->items[i]);
  }
  printf("\n");
}

// Driver code
int main() {
  int ch;
  st *s = (st *)malloc(sizeof(st));

  createEmptyStack(s);

  push(s, 1);
  push(s, 2);
  push(s, 3);
  push(s, 4);

  printStack(s);

  pop(s);

  printf("\nAfter popping out\n");
  printStack(s);
}