Stosy i kolejki

Stosy i kolejki to liniowe struktury danych używane do przechowywania danych i zarządzania nimi.

W tej lekcji dowiedzą się Państwo:

• Jak działają stosy (LIFO — ostatni wchodzi, pierwszy wychodzi).
• Jak działają kolejki (FIFO — pierwszy wchodzi, pierwszy wychodzi).
• Jak implementować stosy i kolejki w języku C.

Stos działa zgodnie z zasadą ostatni wchodzi, pierwszy wychodzi (LIFO).

Operacje:

• Push - Dodaje element na wierzchołek stosu.
• Pop - Usuwa element ze szczytu stosu.
• Peek - Wyświetla element na szczycie bez usuwania go.

Ten program pokazuje operacje na stosie za pomocą tablicy.

#include <stdio.h>
#define MAX 5

int stack[MAX], top = -1;

void push(int value) {
    if (top == MAX - 1) {
        printf("Stack Overflow\n");
    } else {
        stack[++top] = value;
    }
}

int pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
        return -1;
    } else {
        return stack[top--];
    }
}

int main() {
    push(10);
    push(20);
    printf("Popped: %d\n", pop());
    return 0;
}

Kolejka działa zgodnie z zasadą pierwszy wchodzi, pierwszy wychodzi (FIFO).

Operacje:

• Enqueue - Dodaje element na końcu kolejki.
• Dequeue - Usuwa element z początku kolejki.
• Peek - Wyświetla pierwszy element bez usuwania go.

Ten program pokazuje operacje na kolejce za pomocą tablicy.

#include <stdio.h>
#define MAX 5

int queue[MAX], front = -1, rear = -1;

void enqueue(int value) {
    if (rear == MAX - 1) {
        printf("Queue Overflow\n");
    } else {
        if (front == -1) front = 0;
        queue[++rear] = value;
    }
}

int dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue Underflow\n");
        return -1;
    } else {
        return queue[front++];
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    printf("Dequeued: %d\n", dequeue());
    return 0;
}

Kolejka cykliczna eliminuje ograniczenia zwykłej kolejki, ponownie wykorzystując wolne miejsce.

Operacje pozostają takie same, ale zawijają się na końcu tablicy i zaczynają ponownie od jej początku.

Ten program pokazuje implementację kolejki cyklicznej.

#include <stdio.h>
#define MAX 5

int queue[MAX], front = -1, rear = -1;

void enqueue(int value) {
    if ((rear + 1) % MAX == front) {
        printf("Queue Overflow\n");
    } else {
        if (front == -1) front = 0;
        rear = (rear + 1) % MAX;
        queue[rear] = value;
    }
}

int dequeue() {
    if (front == -1) {
        printf("Queue Underflow\n");
        return -1;
    }
    int data = queue[front];
    if (front == rear) {
        front = rear = -1;
    } else {
        front = (front + 1) % MAX;
    }
    return data;
}

int main() {
    enqueue(10);
    enqueue(20);
    printf("Dequeued: %d\n", dequeue());
    return 0;
}

Stosy są używane do:

• Zarządzania wywołaniami funkcji (rekurencja).
• Obsługi operacji cofania i ponawiania.
• Obliczania wartości wyrażeń.

Kolejki są używane do:

• Planowania zadań w systemach operacyjnych.
• Zarządzania żądaniami na serwerach internetowych.
• Przesyłania danych w sieciach.

W tej lekcji poznali Państwo:

• Jak działają stosy i kolejki.
• Jak implementować operacje na stosach i kolejkach.
• Zastosowania stosów i kolejek.

W następnej części przyjrzymy się drzewom i grafom w języku C!