Stos

Stos (ang. stack) – liniowa struktura danych, w której dane dokładane są na wierzch stosu i z wierzchołka stosu są pobierane. Aby ściągnąć elementy stosu poniżej wierzchołka, trzeba najpierw po kolei ściągnąć to, co jest nad nimi.

Stos jest używany w systemach komputerowych na wszystkich poziomach funkcjonowania systemów informatycznych. Stosowany jest przez procesory do chwilowego zapamiętywania rejestrów procesora, do przechowywania zmiennych lokalnych, a także w programowaniu wysokopoziomowym.

Podstawowe operacje na stosie

• push – odłożenie obiektu na stos
• pop – ściągnięcie obiektu ze stosu

Odwrotna notacja polska (ONP, ang. reverse Polish notation, RPN)

Sposób zapisu wyrażeń arytmetycznych, w którym znak wykonywanej operacji umieszczony jest po operandach, a nie pomiędzy nimi jak w konwencjonalnym zapisie algebraicznym lub przed operandami jak w zwykłej notacji polskiej. Zapis ten pozwala na całkowitą rezygnację z użycia nawiasów w wyrażeniach, jako że jednoznacznie określa kolejność wykonywanych działań.

ONP bardzo ułatwia wykonywanie na komputerze obliczeń z nawiasami i zachowaniem kolejności działań. Zarówno algorytm konwersji notacji konwencjonalnej na odwrotną notację polską, jak i algorytm obliczania wartości wyrażenia danego w ONP są bardzo proste i wykorzystują stos.

Przykłady zapisu wyrażeń

Zadanie

Zapisz w ONP wyrażenia:

• 2(x - 3y)
• (x - y)(x + y)
• 7 + 6 ⋅ 5 ⋅ (4 - 3)