Course Content
C Tutorial
About Lesson

Stacks and Queues

Data structures form the backbone of computer science, enabling efficient storage and retrieval of information. Among these structures, stacks and queues stand out as fundamental concepts with diverse applications. In C programming, understanding these abstract data types is pivotal for developing optimized algorithms and systems.

What are Stacks?

A stack represents a collection of elements with a Last-In, First-Out (LIFO) structure. Picture a stack of plates—the last plate placed becomes the first one to be removed. In C, stacks are commonly implemented using arrays or linked lists. The key operations on a stack include push (to add elements) and pop (to remove elements).

Implementation of Stacks in C

In C, an array-based implementation of a stack involves declaring an array and manipulating its elements using stack-specific functions. Meanwhile, a linked list-based implementation utilizes pointers to create a dynamic structure.

Code Example: Stack Implementation in C Using Arrays

#define MAX_SIZE 100

typedef struct {
int items[MAX_SIZE];
int top;
} Stack;

void initialize(Stack *s) {
s->top = -1;
}

int isFull(Stack *s) {
return s->top == MAX_SIZE - 1;
}

int isEmpty(Stack *s) {
return s->top == -1;
}

void push(Stack *s, int value) {
if (isFull(s)) {
printf("Stack overflown");
return;
}
s->items[++s->top] = value;
}

int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack underflown");
return -1;
}
return s->items[s->top--];
}

What are Queues?

On the other hand, queues follow the First-In, First-Out (FIFO) principle, resembling a line of people waiting. The element that enters first is the first one to be removed. In C, queues can be implemented similarly to stacks, using arrays or linked lists.

Implementation of Queues in C

Queue implementations involve enqueue (adding elements) and dequeue (removing elements) operations. In C programming, arrays and linked lists can both facilitate efficient queue structures.

Code Example: Queue Implementation in C Using Arrays

#define MAX_SIZE 100

typedef struct {
int items[MAX_SIZE];
int front, rear;
} Queue;

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

int isFull(Queue *q) {
return (q->rear == MAX_SIZE - 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 fulln");
return;
}
if (isEmpty(q)) {
q->front = 0;
}
q->items[++q->rear] = value;
}

int dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is emptyn");
return -1;
}
int item = q->items[q->front++];
if (q->front > q->rear) {
q->front = q->rear = -1;
}
return item;
}

Applications of Stacks and Queues

Both stacks and queues find extensive applications in various computing fields. Stacks are crucial in parsing expressions, managing function calls in recursion, and undo functionality in text editors. Queues are indispensable in scheduling tasks, managing resources in operating systems, and implementing breadth-first search algorithms