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
Top comments (0)