Algorytmy i Struktury Danych - Podstawowe pojęcia dotyczące stosów

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 będzie wskazywał pustą komórkę tablicy, która znajduje się na szczycie stosu:

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 sptr

top – algorytm odczytu stosu

Wejście:

sptr : zmienna przechowująca wskaźnik stosu tablicy.
S : 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 sptr ← sptr-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):
        self.s = None


    # 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
#---------------

# Tworzymy stos na 10 elementów
s = Stack(10)
for i in range(10):
    s.push(i+1)
while not s.empty():
    print(s.top())
    s.pop()

Wynik:

do podrozdziału do strony

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
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    Data: typ_danych;
  end;

C++

struct SLel
{
  SLel * next;
  typ_danych data;
};

Basic

Type SLel
  next As SLel Ptr
  data As typ_danych
End Type

Python (dodatek)

class SLel:


    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 : PSLel;
…

C++

…
SLel * sptr;
…

Basic

…
Dim sptr As SLel 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 : PSLel) : boolean;
begin
  if sptr = nil then empty := true
  else empty := false;
end;

C++

bool empty(SLel * sptr)
{
  return !sptr;
}

Basic

Function empty(sptr As SLel Ptr_
               As Integer
  If sptr = 0 Then _
    Return 1
  Return 0
End Function

Python (dodatek)

# klasa elementu listy
class SLel:


    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 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 sptr→data

Pascal

function top(sptr : PSLel)
             : typ_danych;
begin
  if sptr = nil then
    top = wartość_specjalna
  else
    top := sptr^.data;
end;

C++

slist * top (SLel * sptr)
{
  if(sptr) return sptr->data;
  else return wartość_specjalna; 
}

Basic

Function top(sptr As SLel Ptr)_
             As typ_danych
  If sptr Then
    Return sptr->data
  Else
    Return wartość_specjalna
  End If
End Function

Python (dodatek)

# klasa elementu listy
class SLel:


    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: e→data ← v ; dane umieszczamy w polu data
K03: e→next ← 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 : PSLel;
               v : typ_danych);
var
  e : PSLel;
begin
  new(e);
  e^.Data:= v;
  e^.next := sptr;
  sptr := e;
end;

C++

void push(SLel * & sptr, 
          typ_danych v)
{
  SLel * e = new SLel;
  e->data = v;
  e->next = sptr;
  sptr = e;
}

Basic

Sub push(ByRef sptr As SLel Ptr, _
         ByVal v As typ_danych)
  Dim e As SLel Ptr
  e = New SLel
  e->data = v
  e->next = sptr
  sptr = e
End Sub

Python (dodatek)

# klasa elementu listy
class SLel:


    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 = SLel(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 ← sptr→next ; usuwamy ze stosu bieżący szczyt
K04: Usuń z pamięci element wskazany przez e
K05: Zakończ

Pascal

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

C++

void pop(SLel * & sptr)
{
  if(p)
  {
    SLel * e = sptr;
    sptr = sptr->next;
    delete e;
  }
}

Basic

Sub pop(ByRef sptr as SLel Ptr)
  Dim e As SLel Ptr
  If sptr Then
    e = sptr
    sptr = sptr->next
    Delete e
  End If  
End Sub

Python (dodatek)

# klasa elementu listy
class SLel:


    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:
            self.sptr = self.sptr.next

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
  PSLel = ^SLel;

  SLel =  record
    next  : PSLel;
    Data: integer;
  end;

// Definicja typu obiektowego Stack
//---------------------------------

  Stack = object
    private
      sptr : PSLel;  // 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 : PSLel;
begin
  new (e);
  e^.Data:= v;
  e^.next := sptr;
  sptr := e;
end;

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

procedure Stack.pop;
var
  e :PSLel;
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 SLel
{
  SLel * next;
  int data;
};

class Stack
{
  private:
    SLel * 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)
{
  SLel * e = new SLel;
  e->data = v;
  e->next = sptr;
  sptr = e;
}

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

void Stack::pop(void)
{
  if(sptr)
  {
    SLel * 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 SLel
  next As SLel Ptr
  data As Integer
End Type

Type Stack
  Private:
    sptr As SLel 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

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 SLel Ptr
  e = New SLel
  e->Data = v
  e->Next = sptr
  sptr = e
End Sub

' Usuwa ze stosu
'---------------
Sub Stack.pop()
  Dim e As SLel 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 SLel:


    # 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 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 = SLel(v)
        e.next = self.sptr
        self.sptr = e


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


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

s = Stack()
for i in range(1, 11):
    s.push(i)
while not s.empty():
    print(s.top())
    s.pop()

Wynik:

do podrozdziału do strony

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.

Podstawowe pojęcia dotyczące stosów

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

Tablica jako stos

empty – algorytm sprawdzania, czy stos jest pusty

Wejście:

Wyjście:

Lista kroków:

top – algorytm odczytu stosu

Wejście:

Wyjście:

Lista kroków:

push – algorytm zapisu na stos

Wejście:

Wyjście:

Lista kroków:

pop – algorytm usuwania ze stosu

Wejście:

Wyjście:

Lista kroków:

Przykładowe programy

Lista jako stos

empty – algorytm sprawdzania, czy stos jest pusty

Wejście:

Wyjście:

Lista kroków:

top – algorytm odczytu szczytu stosu

Wejście:

Wyjście:

Lista kroków:

push – algorytm zapisu na stos

Wejście:

Wyjście:

Dane pomocnicze:

Lista kroków:

pop – algorytm usuwania ze stosu

Wejście:

Wyjście:

Dane pomocnicze:

Lista kroków:

Przykładowe programy