#006 DS&A - Stacks and queues

Introduction

Nothing to say more than hello 👋,
In Case your wondering who is this man in the banner it's the Khwarizmi the inventor of algorithms concept.
Make sure to follow because I will start more advanced series in future.

Stacks and queues

Implementation of Stack using arrays

the problem of arrays that we should know the max number of elements we need to use, If you can't predict the size go with linkedlist.

A stack mean that we can only get last element and first input is last output.

int stack[max];
int top = -1; // mean stack is empty
void push(int item) 
{
    if (top == max-1) printf("overflow");
    else stack[++top] = item; // ++top will increment top first
    return;
}

int pop()
{
    int temp
    if(top == -1) 
    {
        printf("underflow");
        return -1;
    }
    else temp = stack[top--];
    return temp;
}

Linked List implementation of stack

he head will link to the new node.

struct node
{
    int i;
    struct node *link;
};

void push(int item)
{
    struct node *p = (struct node*)malloc(sizeof(struct node));
    if(p == NULL)
    {
        printf("error of malloc");
        return;
    }
    p->data = item;
    p->link = head;
    head = p;
}

pushing time is O(1)

int pop()
{
    int item;
    struct node *p;
    if(head == NULL)
    {
        printf("underflow");
        return -1;
    }
    item = head->i;
    p = head;
    head = head->next;
    free(p);
    return item;
}

pop is O(1)

Queue using circular array

even if a circular array we visualize it as an circular array.

front and rear will both be pointing to the 0 element. let's say we have an array of 4 integers

first type I need to put an element the rear will move +1 when the rear is already reach n-1 again I need to put it at n-1 so I will use (rear+1) mod n , dashed rear it mean it pass from here it start from 0 to n-1

// delete element
int dequeue()
{
    if(front==rear)
    {
        printf("Q is empty");
        return -1;
    }
    else
    {
        front = (front+1) mod n;
        item = q[front];
        return item;
    }
}

// insert element
void enqueue(item)
{
    rear = (rear+1) mod n;
    if(front == rear)
    {
        printf("Q is full");
        if(rear == 0 ) rear = n-1;
        else rear = rear-1;
        return;
    }
    else
    {
        q[rear] = item;
        return;
    }
}

Queue will be full if

(rear+1) mod n == front

Queue will be empty if

rear == front