Computer Algorithms - Stacks and Queues

1. Data Structures

Computer programs store large amounts of data, retrieve it in the required order, and process it.
- A data structure is a structure that defines how data is stored and managed.
Data structures are fundamental tools for implementing algorithms.
If an algorithm is a procedure for solving a problem, a data structure is the method for holding and organizing data during that process.
Even with the same algorithm, processing speed and implementation details can vary depending on which data structure is used.

1.1. Stacks and Queues

Stacks and queues are linear data structures that store and retrieve data in order.
- A linear data structure is a structure in which data has an order, as if it were connected in a single line.

Stacks and queues are among the most basic linear data structures and form the foundation for many data structures and algorithms.

2. Stack

A stack is a data structure shaped like data piled up one item on top of another.
New data is added on top of existing data, and data is also removed starting from the item at the top.

2.1. LIFO (Last In, First Out)

The method in which the data that enters last comes out first is called last-in, first-out (LIFO, Last In, First Out).
It is easy to understand if you imagine books or plates stacked upward.
When several plates are stacked, it is difficult to take out a plate from the bottom directly, so you must remove the plate on top first.

2.2. Implementation Code

#include <stdbool.h>
#include <stdio.h>
 
#define MAX_SIZE    5
 
// Defines the stack structure.
typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;
 
// Initializes the stack.
void init_stack(Stack *s) {
    s->top = -1;
}
 
// Checks whether the stack is full.
bool is_full(Stack *s) {
    return s->top == MAX_SIZE - 1;
}
 
// Checks whether the stack is empty.
bool is_empty(Stack *s) {
    return s->top == -1;
}
 
// Adds an element to the stack.
bool push(Stack *s, int value) {
    if (is_full(s)) {
        return false;
    }
    s->top = s->top + 1;
    s->items[s->top] = value;
    printf("Pushed: %d\n", value);
    return true;
}
 
// Removes an element from the stack.
int pop(Stack *s) {
    if (is_empty(s)) {
        return -1;
    }
    int poppedValue = s->items[s->top];
    s->top = s->top - 1;
 
    printf("Popped: %d\n", poppedValue);
    return poppedValue;
}
 
// Returns the top element of the stack.
int peek(Stack *s) {
    if (is_empty(s)) {
        return -1;
    }
    return s->items[s->top];
}
 
// Prints the elements inside the stack.
void display(Stack *s) {
    if (is_empty(s)) {
        return;
    }
    printf("Stack: ");
    for (int i = 0; i <= s->top; i++) {
        printf("%d ", s->items[i]);
    }
    printf("\n");
}
 
int main(void) {
    Stack s;
    init_stack(&s);
 
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    display(&s);
 
    printf("Top element is %d\n", peek(&s));
 
    pop(&s);
    display(&s);
 
    push(&s, 40);
    push(&s, 50);
    push(&s, 60);
    push(&s, 70);
    display(&s);
 
    return 0;
}

Pushed: 10
Pushed: 20
Pushed: 30
Stack: 10 20 30
Top element is 30
Popped: 30
Stack: 10 20
Pushed: 40
Pushed: 50
Pushed: 60
Stack: 10 20 40 50 60

Function	Description
`init_stack()`	Initializes the stack to an empty state.
`is_full()`	Checks whether the stack is full.
`is_empty()`	Checks whether the stack is empty.
`push()`	Adds data to the top of the stack.
`pop()`	Removes and deletes the data at the top of the stack.
`peek()`	Checks the data at the top of the stack.
`display()`	Prints the data stored in the stack in order.

2.3. Characteristics

It is a structure (LIFO) that retrieves the most recently stored data first.
Data is added and removed only at the top of the stack.
It is difficult to directly retrieve data from the middle or bottom.
It is suitable for storing recently performed operations or previous states.

3. Queue

A queue is a linear data structure that stores and processes data in order.
Data is added at the rear of the queue and removed from the front.

In a queue, the following two positions are important.

Term	Description
`front`	The position of the data that will be removed first.
`rear`	The position where new data is added.

3.1. FIFO (First In, First Out)

A queue follows a first-in, first-out (FIFO, First In, First Out) method, where data that enters first leaves first.
It is a processing method in which the data that arrived first comes out first.
It is easy to understand if you imagine people waiting in line.
The person who lines up first receives service first, while those who line up later wait behind them.

3.2. Implementation Code

#include <stdbool.h>
#include <stdio.h>
 
#define MAX_SIZE    5
 
// Defines the queue structure.
typedef struct {
    int items[MAX_SIZE];
    int front;
    int rear;
} Queue;
 
// Initializes the queue.
void init_queue(Queue *q) {
    q->front = -1;
    q->rear  = -1;
}
 
// Checks whether the queue is full.
bool is_full(Queue *q) {
    return q->rear == MAX_SIZE - 1;
}
 
// Checks whether the queue is empty.
bool is_empty(Queue *q) {
    return q->front == -1 || q->front > q->rear;
}
 
// Adds an element to the queue.
bool enqueue(Queue *q, int value) {
    if (is_full(q)) {
        return false;
    }
    if (q->front == -1) {
        q->front = 0;
    }
    q->rear = q->rear + 1;
    q->items[q->rear] = value;
    printf("Enqueued: %d\n", value);
    return true;
}
 
// Removes an element from the queue.
int dequeue(Queue *q) {
    if (is_empty(q)) {
        return -1;
    }
    int value = q->items[q->front];
    q->front = q->front + 1;
 
    if (q->front > q->rear) {
        q->front = -1;
        q->rear  = -1;
    }
 
    printf("Dequeued: %d\n", value);
    return value;
}
 
// Returns the front element of the queue.
int peek(Queue *q) {
    if (is_empty(q)) {
        return -1;
    }
    return q->items[q->front];
}
 
// Prints the elements inside the queue.
void display(Queue *q) {
    if (is_empty(q)) {
        return;
    }
    printf("Queue: ");
    for (int i = q->front; i <= q->rear; i++) {
        printf("%d ", q->items[i]);
    }
    printf("\n");
}
 
int main(void) {
    Queue q;
    init_queue(&q);
 
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    display(&q);
 
    printf("Front element is %d\n", peek(&q));
 
    dequeue(&q);
    display(&q);
 
    enqueue(&q, 40);
    enqueue(&q, 50);
    enqueue(&q, 60);
    enqueue(&q, 70);
    display(&q);
 
    return 0;
}

Enqueued: 10
Enqueued: 20
Enqueued: 30
Queue: 10 20 30
Front element is 10
Dequeued: 10
Queue: 20 30
Enqueued: 40
Enqueued: 50
Queue: 20 30 40 50

Function	Description
`init_queue()`	Initializes the queue to an empty state.
`is_full()`	Checks whether the queue is full.
`is_empty()`	Checks whether the queue is empty.
`enqueue()`	Adds data to rear, the back of the queue.
`dequeue()`	Removes and deletes data from front, the front of the queue.
`peek()`	Checks the data at the front of the queue.
`display()`	Prints the data stored in the queue in order from the front.

3.3. Characteristics

A queue is a first-in, first-out (FIFO) structure, where the data that enters first comes out first.
Data is added at rear , the rear of the queue, and removed from front , the front.
It is used in cases that process items in order, such as waiting lines, printer output, and task scheduling.

4. Stacks and Queues in Practice

So far, we have covered the concepts and behavior of stacks and queues, along with basic implementation methods using arrays.
Now, through example source code, we will look at how stacks and queues are implemented and used in actual programs.
In practice, instead of directly implementing linked-list insertion, deletion, and traversal, verified data-structure macros are often used to keep code concise and consistent.

4.1. Data Structure Macros

Linux's <sys/queue.h> provides various linked-list data structures and related macros that can be used to implement stacks and queues.
Using it allows you to manage data structures efficiently without directly implementing linked-list insertion, deletion, and traversal from scratch.

SLIST: singly linked list
STAILQ: singly linked list with a tail pointer
LIST: doubly linked list
TAILQ: doubly linked list with a tail pointer

4.2. Stack Implementation Using SLIST

SLIST is used in this example to implement a stack as a linked list.
Data is added to the front through push(), and the most recently added data is removed first through pop().
Dynamically created nodes are released through free() and cleanup() to prevent memory leaks.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <sys/queue.h>
 
/* Defines a stack node. */
struct entry {
    int value;
    SLIST_ENTRY(entry) entries;
};
 
/* Defines the stack head type. */
SLIST_HEAD(stackhead, entry);
 
/* Pushes an element onto the stack. */
bool push(struct stackhead *head, int value) {
    struct entry *e = malloc(sizeof(struct entry));
    if (e == NULL) {
        return false;
    }
    e->value = value;
    SLIST_INSERT_HEAD(head, e, entries);
    printf("Pushed: %d\n", value);
    return true;
}
 
/* Pops an element from the stack. */
int pop(struct stackhead *head) {
    if (SLIST_EMPTY(head)) {
        return -1;
    }
    struct entry *temp = SLIST_FIRST(head);
    int value = temp->value;
    SLIST_REMOVE_HEAD(head, entries);
    free(temp);
    printf("Popped: %d\n", value);
    return value;
}
 
/* Prints all elements in the stack. */
void display(struct stackhead *head) {
    if (SLIST_EMPTY(head)) {
        return;
    }
    printf("Stack: ");
    struct entry *temp;
    SLIST_FOREACH(temp, head, entries) {
        printf("%d ", temp->value);
    }
    printf("\n");
}
 
/* Frees all entries in the stack. */
void cleanup(struct stackhead *head) {
    struct entry *temp;
    while (!SLIST_EMPTY(head)) {
        temp = SLIST_FIRST(head);
        SLIST_REMOVE_HEAD(head, entries);
        free(temp);
    }
}
 
/* Runs a simple SLIST stack example. */
int main(void) {
    struct stackhead head;
    SLIST_INIT(&head);
 
    push(&head, 10);
    push(&head, 20);
    push(&head, 30);
    display(&head);
 
    pop(&head);
    display(&head);
 
    cleanup(&head);
 
    return 0;
}

4.3. Queue Implementation Using STAILQ

STAILQ is used in this example to implement a queue as a linked list.
Data is added to the rear through enqueue(), and the earliest added data is removed first through dequeue().
Nodes remaining in the queue are deleted in order in cleanup() to release the allocated memory.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <sys/queue.h>
 
/* Defines a queue node. */
struct entry {
    int value;
    STAILQ_ENTRY(entry) entries;
};
 
/* Defines the queue head type. */
STAILQ_HEAD(queuehead, entry);
 
/* Adds an element to the tail of the queue. */
bool enqueue(struct queuehead *head, int value) {
    struct entry *e = malloc(sizeof(struct entry));
    if (e == NULL) {
        return false;
    }
    e->value = value;
    STAILQ_INSERT_TAIL(head, e, entries);
    printf("Enqueued: %d\n", value);
    return true;
}
 
/* Removes an element from the front of the queue. */
int dequeue(struct queuehead *head) {
    if (STAILQ_EMPTY(head)) {
        printf("Queue is empty! Cannot dequeue\n");
        return -1;
    }
    struct entry *temp = STAILQ_FIRST(head);
    int value = temp->value;
    STAILQ_REMOVE_HEAD(head, entries);
    free(temp);
    printf("Dequeued: %d\n", value);
    return value;
}
 
/* Prints all elements in the queue. */
void display(struct queuehead *head) {
    if (STAILQ_EMPTY(head)) {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue: ");
    struct entry *temp;
    STAILQ_FOREACH(temp, head, entries) {
        printf("%d ", temp->value);
    }
    printf("\n");
}
 
/* Frees all entries in the queue. */
void cleanup(struct queuehead *head) {
    struct entry *temp;
    while (!STAILQ_EMPTY(head)) {
        temp = STAILQ_FIRST(head);
        STAILQ_REMOVE_HEAD(head, entries);
        free(temp);
    }
}
 
/* Runs a simple STAILQ queue example. */
int main(void) {
    struct queuehead head;
    STAILQ_INIT(&head);
 
    enqueue(&head, 10);
    enqueue(&head, 20);
    enqueue(&head, 30);
    display(&head);
 
    dequeue(&head);
    display(&head);
 
    cleanup(&head);
 
    return 0;
}

Search This Blog

Dear Son (EN)

Computer Algorithms - Stacks and Queues

1. Data Structures

1.1. Stacks and Queues

2. Stack

2.1. LIFO (Last In, First Out)

2.2. Implementation Code

2.3. Characteristics

3. Queue

3.1. FIFO (First In, First Out)

3.2. Implementation Code

3.3. Characteristics

4. Stacks and Queues in Practice

4.1. Data Structure Macros

4.2. Stack Implementation Using SLIST

4.3. Queue Implementation Using STAILQ