Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Podstawowe pojęcia dotyczące stosów

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Stos (ang. stack) jest sekwencyjną strukturą danych. Najprościej możemy go sobie wyobrazić jako stos książek na biurku. Nowe książki układamy na szczycie stosu (ang. stack top), wtedy stos rośnie w górę

obrazek

Ze stosu pobieramy książki znajdujące się na samej górze, wtedy stos maleje. Zwróć uwagę, że książki zawsze zdejmujesz ze stosu w kolejności odwrotnej do ich umieszczania – jako pierwszą zdejmiesz ostatnią książkę na stosie.

obrazek

Wracając do świata komputerów, stos jest taką strukturą danych, z której odczytujemy elementy w kolejności odwrotnej do ich wstawiania. Struktura ta nosi nazwę LIFO (ang. Last In – First Out – wszedł ostatni, a wyszedł pierwszy).

Rozróżniamy następujące operacje dla stosu:

  • Sprawdzenie, czy stos jest pusty – operacja empty zwraca true, jeśli stos nie zawiera żadnego elementu, w przeciwnym razie zwraca false.
  • Odczyt stosu – operacja top zwraca element znajdujący się tuż pod szczytem stosu, sam element pozostaje wciąż na stosie.
  • Zapis na stos – operacja push umieszcza na szczycie stosu nowy element.
  • Usunięcie ze stosu – operacja pop usuwa ze  stosu element znajdujący się tuż pod szczytem.

Stosy możemy realizować za pomocą tablic lub list jednokierunkowych. Realizacja tablicowa jest bardzo prosta i szybka. Stosujemy ją wtedy, gdy dokładnie wiemy, ile maksymalnie elementów będzie przechowywał stos – jest to potrzebne do przygotowania odpowiednio pojemnej tablicy na elementy stosu. Realizacja za pomocą listy jednokierunkowej jest przydatna wtedy, gdy nie znamy dokładnego rozmiaru stosu – listy dostosowują się dobrze do obszarów wolnej pamięci.


Tablica jako stos

Do utworzenia stosu w tablicy potrzebujemy dwóch zmiennych. Pierwszą z nich będzie tablica S, która przechowuje umieszczone na stosie elementy. Druga zmienna sptr służy do zapamiętywania pozycji szczytu stosu i nosi nazwę wskaźnika stosu (ang. stack pointer). Umawiamy się, że wskaźnik stosu zawsze wskazuje pustą komórkę tablicy, która znajduje się na szczycie stosu:

obrazek

Po utworzeniu tablicy zmienna sptr musi zawsze być zerowana. Stos jest pusty, gdy sptr wskazuje początek tablicy, czyli komórkę o indeksie zero. Ta własność jest wykorzystywana w operacji empty. Stos jest pełny, gdy sptr ma wartość równą liczbie n komórek tablicy. W takim przypadku na stosie nie można już umieszczać żadnych dalszych danych, gdyż trafiłyby poza obszar zarezerwowany w pamięci komputera na tablicę. Wady tej nie mają tablice dynamiczne o dynamicznym rozmiarze.

empty – algorytm sprawdzania, czy stos jest pusty

Wejście:

sptr : zmienna przechowująca wskaźnik stosu w tablicy.

Wyjście:

True, jeśli na stosie nie ma żadnego elementu, inaczej false.

Lista kroków:

K01: Jeśli sptr = 0,
     to zakończ z wynikiem true
K02: Zakończ z wynikiem false
Pascal
function empty() : boolean;
begin
  if sptr = 0 then empty := true
  else empty := false;
end;
C++
bool empty()
{
  return !sptr;
}
Basic
Function empty() As Integer
  If sptr = 0 Then Return 1
  Return 0
End Function
Python (dodatek)
def empty():
    return not bool(sptr)

top – algorytm odczytu stosu

Wejście:

sptr : zmienna przechowująca wskaźnik stosu tablicy.
: tablica przechowująca stos.

Wyjście:

Element tuż spod szczytu stosu lub wartość specjalna, jeśli stos jest pusty.

Lista kroków:

K01: Jeśli sptr = 0, 
     to zakończ z wynikiem wartość_specjalna
K02: Zakończ z wynikiem S[sptr-1]
Pascal
function top : typ_danych;
begin
  if sptr = 0 then top := wartość_specjalna
  else top := S[sptr-1];
end;
C++
typ_danych top(void)
{
  if(sptr) return S[sptr-1);
  return wartość_specjalna
}
Basic
Function top() As typ_danych
  If sptr = 0 Then Return wartość_specjalna
  Return S(sptr-1)
End Function
Python (dodatek)
def top():
    if sptr: return S[sptr-1]
    return wartość_specjalna

push – algorytm zapisu na stos

Wejście:

sptr : zmienna przechowująca wskaźnik stosu tablicy.
n : rozmiar tablicy.
S : tablica przechowująca stos.
v : zapisywana wartość.

Wyjście:

Na szczycie stosu zostaje zapisana wartość v, jeśli jest na to miejsce. W przeciwnym razie v nie będzie zapisane na stosie. Po zapisie szczyt stosu przemieszcza się tak, aby zapisany element znalazł się tuż pod nowym szczytem.

Lista kroków:

K01: Jeśli sptr = n, ; stos jest pełny i nie ma
     to zakończ      ; miejsca na nową wartość
K02: S[sptr] ← v ; umieszczamy v na szczycie stosu
K03: sptr ← sptr+1 ; nowy szczyt stosu
K04: Zakończ
Pascal
procedure push(v : typ_danych);
begin
  if sptr < n then
  begin
    S[sptr] := v;
    Inc(sptr);
  end;
end;
C++
void push(typ_danych v)
{
  if(sptr < n) S[sptr++] = v;
}
Basic
Sub push(v As typ_danych)
  If sptr < n Then
    S(sptr) = v
    sptr += 1
  End If
End Sub
Python (dodatek)
def push(v):
    if sptr < n:
        S[sptr] = v
        sptr += 1

pop – algorytm usuwania ze stosu

Wejście:

sptr : zmienna przechowująca wskaźnik stosu tablicy.
S : tablica przechowująca stos.

Wyjście:

Jeśli stos jest niepusty, to spod szczytu stosu zostaje usunięty element. Szczyt stosu przemieszcza się tak, aby zajął pozycję usuniętego elementu.

Lista kroków:

K01: Jeśli sptr > 0,  ; jeśli stos coś zawiera,
     to sptrsptr-1 ; to usuwamy element spod szczytu stosu
K02: Zakończ
Pascal
procedure pop;
begin
  if sptr > 0 then dec(sptr);
end;
C++
void pop(void)
{
  if(sptr) sptr--;
}
Basic
Sub pop()
  If sptr > 0 Then sptr -= 1
End Sub
Python (dodatek)
def pop():
    if sptr: sptr -= 1

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Poniższy program przedstawia sposób implementacji stosu w tablicy. Tworzy on obiekt zawierający tablicę liczb całkowitych, wskaźnik stosu oraz metody obsługi tej struktury. Rozmiar tablicy jest określany przy tworzeniu obiektu. Na stosie zostaje zapisanych 10 liczb, a następnie są one odczytywane i  wyświetlane.
Pascal
// Stos w tablicy
// Data: 13.08.2012
// (C)2020 mgr Jerzy Wałaszek
//------------------------------

program arrstack;

  type
    Tinteger = array of integer;

// Definicja typu obiektowego stack
//---------------------------------
  stack = object
    private
      n    : integer;   // rozmiar tablicy
      sptr : integer;   // wskaźnik stosu
      S    : Tinteger;  // tablica dynamiczna

    public
      constructor init(x : integer);
      destructor destroy;
      function empty : boolean;
      function top : integer;
      procedure push(v : integer);
      procedure pop;
  end;

//---------------------
// Metody obiektu stack
//---------------------

// Konstruktor - tworzy tablicę dla stosu
//---------------------------------------
constructor stack.init(x : integer);
begin
  n := x;
  SetLength(S,x);
  sptr := 0;
end;

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------
destructor stack.destroy;
begin
  SetLength(S,0);
end;

// Sprawdza, czy stos jest pusty
//------------------------------
function stack.empty : boolean;
begin
  if sptr = 0 then empty := true
  else empty := false;
end;

// Zwraca szczyt stosu.
// Wartość specjalna to -MAXINT
//-----------------------------
function stack.top : integer;
begin
  if sptr = 0 then
    top := -MAXINT
  else
    top := S[sptr-1];
end;

// Zapisuje na stos
//-----------------
procedure stack.push(v : integer);
begin
  if sptr < n then
  begin
    S[sptr] := v;
    Inc(sptr);
  end;
end;

// Usuwa ze stosu
//---------------
procedure stack.pop;
begin
    if sptr > 0 then dec(sptr);
end;

//---------------
// Program główny
//---------------

var
  S : stack;
  i : integer;

begin
  S.init(10);

  for i := 1 to 10 do S.push(i);

  while not S.empty do
  begin
    writeln(S.top);
    S.pop;
  end;

  S.destroy;
end.
C++
// Stos w tablicy
// Data: 13.08.2012
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

const int MAXINT = -2147483647;

// Definicja typu obiektowego stack
//---------------------------------
class stack
{
  private:
    int n;    // rozmiar tablicy
    int sptr; // wskaźnik stosu
    int * S;  // tablica dynamiczna

  public:
    stack(int x); // konstruktor
    ~stack();     // destruktor
    bool empty (void);
    int  top(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu stack
//---------------------

// Konstruktor - tworzy tablicę dla stosu
//---------------------------------------
stack::stack(int x)
{
  n = x;
  S = new int[x];
  sptr = 0;
}

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------
stack::~stack()
{
  delete [] S;
}

// Sprawdza, czy stos jest pusty
//------------------------------
bool stack::empty(void)
{
  return !sptr;
}

// Zwraca szczyt stosu.
// Wartość specjalna to -MAXINT
//-----------------------------
int stack::top(void)
{
  if(sptr) return S[sptr-1];
  return -MAXINT;
}

// Zapisuje na stos
//-----------------
void stack::push(int v)
{
  if(sptr < n) S[sptr++] = v;
}

// Usuwa ze stosu
//---------------
void stack::pop(void)
{
  if(sptr) sptr--;
}

//---------------
// Program główny
//---------------

int main()
{
  stack S(10); // tworzymy stos na 10 elementów
  int i;

  for(i = 1; i <= 10; i++) S.push(i);

  while(!S.empty())
  {
    cout << S.top() << endl;
    S.pop();
  }
}
Basic
' Stos w tablicy
' Data: 13.08.2012
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Const MAXINT = 2147483647

' Definicja typu obiektowego stack
'---------------------------------
Type stack
  Private:
    n    As Integer     ' rozmiar tablicy
    sptr As Integer     ' wskaźnik stosu
    Stk  As Integer Ptr ' tablica dynamiczna

  Public:

    Declare Constructor(ByVal x As Integer)
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function top As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------
' Program główny
'---------------
Dim S As stack = 10
Dim i As Integer

For i = 1 To 10: S.push (i): Next

While S.empty() = 0
  Print S.top()
  S.pop()
Wend
End

'---------------------
' Metody obiektu stack
'---------------------

' Konstruktor - tworzy tablicę dla stosu
'---------------------------------------
Constructor stack(ByVal x As Integer)
  n    = x
  Stk  = New Integer[x] 
  sptr = 0
End Constructor

' Destruktor - zwalnia tablicę dynamiczną
'----------------------------------------
Destructor stack()
  Delete [] Stk
End Destructor

' Sprawdza, czy stos jest pusty
'------------------------------
Function stack.empty() As Integer
  If sptr = 0 Then Return 1
  Return 0
End Function

' Zwraca szczyt stosu.
' Wartość specjalna to -MAXINT
'-----------------------------
Function stack.top() As Integer
  If sptr = 0 Then Return -MAXINT
  Return Stk[sptr-1] 
End Function

' Zapisuje na stos
'-----------------
Sub stack.push(ByVal v As Integer)
  If sptr < n Then
    Stk[sptr] = v
    sptr += 1
  End If
End Sub

' Usuwa ze stosu
'---------------
Sub stack.pop()
  If sptr > 0 Then sptr -= 1
End Sub
Python (dodatek)
# Stos w tablicy
# Data: 08.06.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

MAXINT = -2147483647

# Definicja typu obiektowego stack
class stack:

    # Konstruktor - tworzy tablicę dla stosu
    def __init__(self,x):
        self.n = x
        self.S = [0] * x
        self.sptr = 0

    # Destruktor - zwalnia tablicę dynamiczną
    def __del__(self):
        del self.S

    # Sprawdza, czy stos jest pusty
    def empty(self):
        return not self.sptr

    # Zwraca szczyt stosu
    # Wartość specjalna to -MAXINT
    def top(self):
        if self.sptr:
            return self.S[self.sptr-1]
        return -MAXINT

    # Zapisuje na stos
    def push(self,v):
        if self.sptr < self.n:
            self.S[self.sptr] = v
            self.sptr += 1

    # Usuwa ze stosu
    def pop(self):
        if self.sptr:
            self.sptr -= 1

#---------------
# Program główny
#---------------

S = stack(10) # Tworzymy stos na 10 elementów

for i in range(10):
    S.push(i+1)

while not S.empty():
    print(S.top())
    S.pop()

del S
Wynik:
10
9
8
7
6
5
4
3
2
1

Na początek:  podrozdziału   strony 

Lista jako stos

Do realizacji stosu możemy w prosty sposób wykorzystać listę jednokierunkową. Zapis na stos będzie wtedy polegał na umieszczaniu elementu na początku listy. Szczyt stosu będzie pierwszym elementem listy. Odczyt ze stosu będzie równoważny odczytowi pierwszego elementu listy, a usunięcie ze stosu będzie odpowiadało usunięciu elementu z początku listy. Realizacja listowa jest szczególnie wygodna wtedy, gdy nie znamy maksymalnego rozmiaru stosu – w przeciwieństwie do tablic listy mogą swobodnie rosnąć w pamięci, dopóki jest dla nich miejsce. W podanych niżej procedurach nie obsługujemy sytuacji braku pamięci – w każdym ze środowisk programowania można w takim przypadku wykorzystać mechanizmy wyłapywania błędów, które jednakże zaciemniają realizowane funkcje.

Każdy element listy jest następującą strukturą danych:

Pascal
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    data  : typ_danych;
  end;
C++
struct slistEl
{
  slistEl * next;
  typ_danych data;
};
Basic
Type slistEl
  next As slistEl Ptr
  data As typ_danych
End Type
Python (dodatek)
class slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

Do obsługi listy potrzebujemy wskaźnika, który wskazuje jej początek, czyli pierwszy element listy. Zdefiniujmy go następująco:

Pascal
...
var sptr : PslistEl;
...
C++
...
slistEl * sptr;
...
Basic
...
Dim sptr As slistEl Ptr
...
Python (dodatek)
class stack:
    def __init__(self):
        self.sptr = None

Przed pierwszym użyciem wskaźnik sptr musi być odpowiednio wyzerowany (w Pythonie robi to automatycznie konstruktor klasy stack):

Pascal
...
sptr := NIL;
...
C++
...
sptr = NULL;
...
Basic
...
sptr = 0
...

empty – algorytm sprawdzania, czy stos jest pusty

Wejście:

sptr : wskaźnik pierwszego elementu listy.

Wyjście:

True, jeśli na stosie nie ma żadnego elementu, inaczej false

Lista kroków:

K01: Jeśli sptr = nil, ; jeśli sptr nie wskazuje elementu listy,
     to zakończ z wynikiem true ; to stos jest pusty
K02: Zakończ z wynikiem false
Pascal
function empty(sptr : PslistEl) : boolean;
begin
  if sptr = nil then empty := true
  else empty := false;
end;
C++
bool empty(slistEl * sptr)
{
  return !sptr;
}
Basic
Function empty(sptr As slistEl Ptr_
               As Integer
  If sptr = 0 Then Return 1
  Return 0
End Function
Python (dodatek)
# klasa elementu listy
class slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa stosu
class stack:
    # Konstruktor
    def __init__(self):
        self.sptr = None

    # Spradza, czy stos pusty
    def empty(self):
        return not bool(self.sptr)

top – algorytm odczytu szczytu stosu

Wejście:

sptr : wskaźnik szczytu stosu.

Wyjście:

Zwraca wartość przechowywaną na szczycie stosu lub wartość specjalną, jeśli stos jest pusty.

Lista kroków:

K01: Jeśli sptr = nil,
     to zakończ zwracając wartość_specjalną
K02: Zakończ z wynikiem (sptrdata)
Pascal
function top(sptr : PslistEl)
             : typ_danych;
begin
  if sptr = nil then
    top = wartość_specjalna
  else
    top := sptr^.data;
end;
C++
slist * top (slistEl * sptr)
{
  if(sptr) return sptr->data;
  else return wartość_specjalna; 
}
Basic
Function top(sptr As slistEl Ptr)_
             As typ_danych
  If sptr Then
    Return sptr->data
  Else
    Return wartość_specjalna
  End If
End Function
Python (dodatek)
# klasa elementu listy
class slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa stosu
class stack:
    # Konstruktor
    def __init__(self):
        self.sptr = None

    # Zwraca daną ze szczytu stosu
    def top(self):
        if self.sptr:
            return self.sptr.data
        else:
            return wartość_specjalna

push – algorytm zapisu na stos

Wejście:

sptr : wskaźnik szczytu stosu.
v : zapisywana wartość

Wyjście:

Na stosie zostaje umieszczona wartość v.

Dane pomocnicze:

e : wskaźnik elementu listy.

Lista kroków:

K01: Utwórz element listy i umieść jego adres w e
K02: (edata) ← v    ; dane umieszczamy w polu data
K03: (enext) ← sptr ; następnikiem będzie bieżący szczyt stosu
K04: sptr ← e        ; szczytem stosu staje się dodany element
K05: Zakończ
Pascal
procedure push(var sptr : PslistEl;
               v : typ_danych);
var
  e : PslistEl;
begin
  new(e);
  e^.data := v;
  e^.next := sptr;
  sptr := e;
end;
C++
void push(slistEl * & sptr,
          typ_danych v)
{
  slistEl * e = new slistEl;
  e->data = v;
  e->next = sptr;
  sptr = e;
}
Basic
Sub push(ByRef sptr As slistEl Ptr,_
         ByVal v As typ_danych)
  Dim e As slistEl Ptr
  e = New slistEl
  e->data = v
  e->next = sptr
  sptr = e
End Sub
Python (dodatek)
# klasa elementu listy
class slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa stosu
class stack:
    # Konstruktor
    def __init__(self):
        self.sptr = None

    # Umieszcza daną na szczycie stosu
    def push(self,v):
        e = slistEl(v)
        e.next = self.sptr
        self.sptr = e

pop – algorytm usuwania ze stosu

Wejście:

sptr : wskaźnik szczytu stosu.

Wyjście:

Ze szczytu stosu zostaje usunięty element.

Dane pomocnicze:

e : wskaźnik elementu listy.

Lista kroków:

K01: Jeśli sptr = nil, ; stos jest pusty
     to zakończ
K02: e ← sptr ; zapamiętujemy szczyt stosu
K03  sptr ← (sptrnext) ; usuwamy ze stosu bieżący szczyt
K04: Usuń z pamięci element wskazany przez e
K05: Zakończ
Pascal
procedure pop(var sptr : PslistEl);
var
  e : PslistEl;
begin
  if sptr <> nil then
  begin
    e := sptr;
    sptr := sptr^.next;
    dispose(e);
  end
end;
C++
void pop(slistEl * & sptr)
{
  if(p)
  {
    slistEl * e = sptr;
    sptr = sptr->next;
    delete e;
  }
}
Basic
Sub pop(ByRef sptr as slistEl Ptr)
  Dim e As slistEl Ptr
  If sptr Then
    e = sptr
    sptr = sptr->next
    Delete e
  End If  
End Sub
Python (dodatek)
# klasa elementu listy
class slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa stosu
class stack:
    # Konstruktor
    def __init__(self):
        self.sptr = None

    # Usuwa daną ze szczytu stosu
    def pop(self):
        if self.sptr:
            e = self.sptr
            self.sptr =self.sptr.next
            del e

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Poniższy program przedstawia sposób implementacji stosu za pomocą listy jednokierunkowej. Tworzy on obiekt zawierający pustą listę liczb całkowitych oraz metody obsługi tej struktury. Na stosie zostaje zapisanych 10 liczb, a następnie są one odczytywane i wyświetlane.
Pascal
// Stos na liście jednokierunkowej
// Data: 13.08.2012
// (C)2020 mgr Jerzy Wałaszek
//------------------------------

program slist_stack;

// Wartość specjalna
//------------------

const SV = -maxint;

// Typ elementów listy
//--------------------

type
  PslistEl = ^slistEl;

  slistEl =  record
    next  : PslistEl;
    data  : integer;
  end;

// Definicja typu obiektowego stack
//---------------------------------

  stack = object
    private
      sptr : PslistEl;  // lista przechowująca stos
    public

      constructor init;
      destructor destroy;
      function empty : boolean;
      function top : integer;
      procedure push(v : integer);
      procedure pop;
  end;

//---------------------
// Metody obiektu slist
//---------------------

// Konstruktor
//------------

constructor stack.init;
begin
  sptr := nil;
end;

// Destruktor
//-----------

destructor stack.destroy;
begin
  while sptr <> nil do pop;
end;

// Sprawdza, czy stos jest pusty
//------------------------------

function stack.empty : boolean;
begin
  if sptr = nil then
    empty := true
  else
    empty := false;
end;

// Zwraca wartość ze szczytu stosu
//----------------------------------

function stack.top : integer;
begin
  if sptr = NIL then
    top := SV
  else
    top := sptr^.data;
end;

// Umieszcza dane na stosie
//-------------------------

procedure stack.push (v : integer);
var
  e : PslistEl;
begin
  new (e);
  e^.data := v;
  e^.next := sptr;
  sptr := e;
end;

// Usuwa dane ze stosu
//--------------------

procedure stack.pop;
var
  e :PslistEl;
begin
  if sptr <> NIL then
  begin
    e := sptr;
    sptr := sptr^.next;
    dispose (e);
  end;
end;

//---------------
// Program główny
//---------------

var
  S : stack;
  i : integer;

begin
  S.init;

  for i := 1 to 10 do S.push (i);

  while not S.empty do
  begin
    writeln(S.top);
    S.pop;
  end;

  S.destroy;

end.
C++
// Stos na liście jednokierunkowej
// Data: 13.08.2012
// (C)2020 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>

using namespace std;

// Wartość specjalna
//------------------

const int SV = -INT_MAX;

// Definicja typu obiektowego stack
//---------------------------------

struct slistEl
{
  slistEl * next;
  int data;
};

class stack
{
  private:
    slistEl * sptr;   // lista przechowująca stos

  public:
    stack();       // konstruktor
    ~stack();      // destruktor
    bool empty(void);
    int top(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu stack
//---------------------

// Konstruktor
//------------

stack::stack()
{
  sptr = NULL;
}

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------

stack::~stack()
{
  while(sptr) pop();
}

// Sprawdza, czy stos jest pusty
//------------------------------

bool stack::empty(void)
{
  return !sptr;
}

// Zwraca szczyt stosu
//--------------------

int stack::top(void)
{
  if(sptr) return sptr->data;
  return SV;
}

// Zapisuje na stos
//-----------------

void stack::push(int v)
{
  slistEl * e = new slistEl;
  e->data = v;
  e->next = sptr;
  sptr = e;
}

// Usuwa ze stosu
//---------------

void stack::pop(void)
{
  if(sptr)
  {
    slistEl * e = sptr;
    sptr = sptr->next;
    delete e;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  stack S;
  int i;

  for(i = 1; i <= 10; i++) S.push(i);

  while(!S.empty())
  {
    cout << S.top() << endl;
    S.pop();
  }
}
Basic
' Stos na liście jednokierunkowej
' Data: 13.08.2012
' (C)2020 mgr Jerzy Wałaszek
'------------------------------

' Wartość specjalna
'------------------

Const SV = -2147483647

' Definicja typu obiektowego stack
'---------------------------------

Type slistEl
  next As slistEl Ptr
  data As Integer
End Type

Type stack
  Private:
    sptr As slistEl Ptr  ' lista zawierająca stos

  Public:

    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function top() As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------
' Program główny
'---------------

Dim S As stack
Dim i As Integer

For i = 1 To 10: S.push (i): Next

While S.empty() = 0
  Print S.top()
  S.pop()
Wend
sleep
End

'---------------------
' Metody obiektu stack
'---------------------

' Konstruktor
'------------

Constructor stack()
  sptr = 0
End Constructor

' Destruktor
'-----------

Destructor stack()
  While sptr
    pop()
  Wend
End Destructor

' Sprawdza, czy stos jest pusty
'------------------------------

Function stack.empty() As Integer
  If sptr = 0 Then Return 1
  Return 0
End Function

' Zwraca szczyt stosu.
'------------------------------

Function stack.top() As Integer
  If sptr = 0 Then
    top = SV
  Else
    top = sptr->data
  End If
End Function

' Zapisuje na stos
'-----------------

Sub stack.push(ByVal v As Integer)
  Dim e As slistEl Ptr
  e = New slistEl
  e->Data = v
  e->Next = sptr
  sptr = e
End Sub

' Usuwa ze stosu
'---------------

Sub stack.pop()
  Dim e As slistEl Ptr
  If sptr Then
  	 e = sptr
  	 sptr = sptr->Next
  	 Delete e
  End If
End Sub
Python (dodatek)
# Stos na liście jednokierunkowej
# Data: 09.06.2024
# (C)2024 mgr Jerzy Wałaszek
#------------------------------

# Wartość specjalna
SV = -2147483648

# Definicja typu obiektowego stack
#---------------------------------

class slistEl:
    # Konstruktor
    def __init__(self,v):
        self.next = None
        self.data = v

class stack:
    # Konstruktor
    def __init__(self):
        self.sptr = None

    # Destruktor
    def __del__(self):
        while self.sptr:
            self.pop()

    # Sprawdza, czy stos jest pusty
    def empty(self):
        return not bool(self.sptr)

    # Zwraca szczyt stosu
    def top(self):
        if self.sptr:
            return self.sptr.data
        else:
            return SV

    # Zapisuje na stos
    def push(self,v):
        e = slistEl(v)
        e.next = self.sptr
        self.sptr = e

    # Usuwa ze stosu
    def pop(self):
        if self.sptr:
            e = self.sptr
            self.sptr = self.sptr.next
            del e

#---------------
# Program główny
#---------------

S = stack()
for i in range(1,11):
    S.push(i)

while not S.empty():
    print(S.top())
    S.pop()
Wynik:
10
9
8
7
6
5
4
3
2
1

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.