Czym jest stos w programowaniu? Podstawowe działania, implementacja w języku C i zastosowania

Stos to jedna z podstawowych struktur danych w programowaniu, której zrozumienie jest kluczowe dla każdego programisty. W tym wpisie na blogu omówimy, czym jest stos, jakie są podstawowe działania na stosie, pokażemy implementację stosu w języku C oraz opiszemy jego zastosowania w praktyce.

Czym jest stos?

Stos to dynamiczna struktura danych, która przechowuje elementy w określonym porządku. Działa na zasadzie LIFO (Last In, First Out), co oznacza, że ostatni dodany element zostaje usunięty jako pierwszy. Stos można porównać do stosu talerzy: możemy dodawać talerze na górę stosu, ale zdejmujemy tylko ten, który jest na szczycie.

  ¹

Podstawowe działania na stosie:

1. Push (dodawanie elementu): Polega na umieszczeniu nowego elementu na szczycie stosu.
2. Pop (usuwanie elementu): Polega na usunięciu elementu ze szczytu stosu.
3. Peek (podglądanie elementu): Polega na sprawdzeniu, jaki element znajduje się na szczycie stosu, bez jego usuwania.
4. IsEmpty (sprawdzanie, czy stos jest pusty): Funkcja zwraca wartość logiczną, która informuje, czy stos jest pusty.

Implementacja stosu w języku C:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 10

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

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

bool isEmpty(Stack *stack) {
    return stack->top == -1;
}

bool isFull(Stack *stack) {
    return stack->top == MAX_SIZE - 1;
}

void push(Stack *stack, int value) {
    if (isFull(stack)) {
        printf("Stos jest pełny.\n");
        return;
    }
    stack->top++;
    stack->data[stack->top] = value;
}

int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stos jest pusty.\n");
        return -1;
    }
    int value = stack->data[stack->top];
    stack->top--;
    return value;
}

int peek(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stos jest pusty.\n");
        return -1;
    }
    return stack->data[stack->top];
}

int main() {
    Stack stack;
    initialize(&stack);

    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);

    printf("Peek: %d\n", peek(&stack));
    printf("Pop: %d\n", pop(&stack));
    printf("Peek: %d\n", peek(&stack));

    return 0;
}

Zastosowania stosu

Stos jest używany w różnych aspektach programowania, takich jak:

1. Wywołanie funkcji: Stos jest używany do przechowywania informacji o wywołaniach funkcji, takich jak zmienne lokalne i adres powrotu. Gdy funkcja jest wywołana, jej zmienne lokalne i adres powrotu są umieszczane na stosie, a po zakończeniu wywołania są one usuwane.
2. Rekurencja: Stos jest używany w rekurencyjnych algorytmach do przechowywania informacji o kolejnych wywołaniach funkcji rekurencyjnej. Rekurencja często wykorzystuje stos do rozwiązania problemów, takich jak obliczanie silni, ciągu Fibonacciego czy rozwiązywanie problemu wież Hanoi.
3. Nawiasy: Stos jest przydatny w algorytmach, które sprawdzają poprawność nawiasów w wyrażeniach matematycznych czy kodzie programów. Na stosie umieszczane są otwierające nawiasy, a gdy napotykany jest zamykający nawias, odpowiedni otwierający nawias jest usuwany ze stosu.
4. Odwracanie kolejności: Stos może być używany do odwrócenia kolejności elementów, na przykład słów w zdaniu lub cyfr w liczbie. Elementy są umieszczane na stosie, a następnie zdejmowane w odwrotnej kolejności.
5. Analiza składniowa i obliczanie wyrażeń: Stos jest wykorzystywany w analizie składniowej i obliczaniu wartości wyrażeń matematycznych, na przykład w algorytmie shunting yard czy stosie maszynowej przy stosowaniu odwrotnej notacji polskiej (ONP).

  ¹

Podsumowanie

Stos to podstawowa struktura danych w programowaniu, która umożliwia przechowywanie i zarządzanie elementami w porządku LIFO. Istnieje wiele zastosowań stosu w różnych dziedzinach programowania, co sprawia, że jego zrozumienie jest niezbędne dla każdego programisty. Wprowadziliśmy podstawowe działania na stosie, implementację w języku C oraz omówiliśmy kilka praktycznych zastosowań stosu.