Podstawowe pojęcia dotyczące stosów


Tematy pokrewne   Podrozdziały
Podstawowe operacje na tablicach
Podstawowe pojęcia dotyczące list
Reprezentacja list w pamięci komputera
Operacje na listach jednokierunkowych
Operacje na listach dwukierunkowych
Stosy
Podstawowe pojęcia dotyczące stosów
Przeliczanie liczb na zapis w innym systemie pozycyjnym
Odwrotna Notacja Polska
Sortowanie przez wstawianie za pomocą stosów
  Tablica jako stos
Lista jako stos

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ę.

 

 

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.

 

 

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:

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, 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ę tuż ponad szczytem 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 komórek tablicy. W takim przypadku na stosie nie można już umieszczać żadnych dalszych danych. gdyż trafiłyby poza obszar zarezerwowany na tablicę.

 

Stos w tablicy – algorytm sprawdzania, czy stos jest pusty

Wejście
sptr    zmienna przechowująca wskaźnik stosu 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

 

Lazarus Code::Blocks Free Basic
function empty : boolean;
begin
  if sptr = 0 then empty := true
  else empty := false;
end;
bool empty(void)
{
  return !sptr;
}
Function empty() As Integer
  If sptr = 0 Then Return 1
  Return 0
End Function

 

Stos w tablicy – algorytm odczytu szczytu stosu

Wejście
sptr    zmienna przechowująca wskaźnik stosu tablicy
n  – rozmiar tablicy
S  – tablica przechowująca stos
Wyjście:

Zawartość szczytu stosu lub wartość specjalna, jeśli stos jest pusty.

Lista kroków:
K01 Jeśli sptr = 0, to zakończ z wynikiem wartość specjalną
K02: Zakończ z wynikiem S[sptr - 1]

 

Lazarus
function top : typ_danych;
begin
  if sptr = 0 then top := wartość_specjalna
  else top := S[sptr - 1];
end;
Code::Blocks
typ_danych top(void)
{
  if(sptr) return S[sptr - 1);
  return wartość_specjalna
}
Free Basic
Function top() As typ_danych
  If sptr = 0 Then Return wartość_specjalna
  Return S(sptr - 1)
End Function

 

Stos w tablicy – 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 stosie zostaje zapisana wartość v, jeśli jest na to miejsce. W przeciwnym razie v nie będzie zapisane.

Lista kroków:
K01 Jeśli sptr = n, to zakończ ; stos jest pełny i nie ma miejsca na nową wartość
K02: S[sptr] ← v ; umieszczamy v ponad szczytem stosu
K03: sptrsptr + 1 ; zwiększamy wskaźnik stosu
K04: Zakończ  

 

Lazarus Code::Blocks Free Basic
procedure push(v : typ_danych);
begin
  if sptr < n then
  begin
    S[sptr] := v;
    Inc(sptr);
  end;
end;
void push(typ_danych v)
{
  if(sptr < n) S[sptr++] = v;
}
Sub push(v As typ_danych)
  If sptr < n Then
    S(sptr) = v
    sptr += 1
  End If
End Sub

 

Stos w tablicy – algorytm usuwania ze stosu

Wejście
sptr    zmienna przechowująca wskaźnik stosu tablicy
S  – tablica przechowująca stos
Wyjście:

Ze szczytu stosu zostaje usunięty element.

Lista kroków:
K01 Jeśli sptr > 0, to sptrsptr - 1 ; jeśli stos coś zawiera, to usuwamy element na szczycie stosu
K02: Zakończ  

 

Lazarus Code::Blocks Free Basic
procedure pop;
begin
  if sptr > 0 then dec(sptr);
end;
void pop(void)
{
  if(sptr) sptr--;
}
Sub pop()
  If sptr > 0 Then sptr -= 1
End Sub

Program

Ważne:

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.

 

Lazarus
// Stos w tablicy
// Data: 13.08.2012
// (C)2012 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.
Code::Blocks
// Stos w tablicy
// Data: 13.08.2012
// (C)2012 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();
  }
}
Free Basic
' Stos w tablicy
' Data: 13.08.2012
' (C)2012 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
    S    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
  S = New Integer [x]
  sptr = 0
End Constructor

' Destruktor - zwalnia tablicę dynamiczną
'----------------------------------------
Destructor stack()
  Delete [] S
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 S[sptr - 1]
End Function

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

' Usuwa ze stosu
'---------------
Sub stack.pop()
  If sptr > 0 Then sptr -= 1
End Sub
Wynik
10
9
8
7
6
5
4
3
2
1

 

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:

 
Lazarus Code::Blocks Free Basic
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    data  : typ_danych;
  end;
struct slistEl
{
  slistEl * next;
  typ_danych data;
};
Type slistEl
  next As slistEl Ptr
  data As typ_danych
End Type

 

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

 
Lazarus Code::Blocks Free Basic
...
var stack : PslistEl;
...
...
slistEl * stack;
...
...
Dim stack As slistEl Ptr
...

 

Przed pierwszym użyciem wskaźnik stack musi być odpowiednio wyzerowany:

 
Lazarus Code::Blocks Free Basic
...
stack := NIL;
...
...
stack = NULL;
...
...
stack = 0
...

 

Stos na liście – algorytm sprawdzania, czy stos jest pusty

Wejście
p    wskaźnik szczytu stosu
Wyjście:

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

Lista kroków:
K01 Jeśli p = nil, to zakończ z wynikiem true
K02: Zakończ z wynikiem false

 

Lazarus
function empty(p : PslistEl) : boolean;
begin
  if p = nil then empty := true
  else empty := false;
end;
Code::Blocks
bool empty(slistEl * p)
{
  return !p;
}
Free Basic
Function empty(p As slistEl Ptr) As Integer
  If p = 0 Then Return 1
  Return 0
End Function

 

Stos na liście – algorytm odczytu szczytu stosu

Wejście
p    wskaźnik szczytu stosu
Wyjście:

Zwraca wskazanie elementu, który jest bieżącym szczytem stosu lub nil, jeśli stos jest pusty

Lista kroków:
K01: Zakończ z wynikiem p
 
Lazarus
function top(p : PslistEl) : PslistEl;
begin
  top := p;
end;
Code::Blocks
slist * top(slistEl * p)
{
  return p;
}
Free Basic
Function top(p As slistEl Ptr) As slistEl Ptr
  Return p
End Function

 

Stos na liście – algorytm zapisu na stos

Wejście
p    wskaźnik szczytu stosu
v  – zapisywana wartość
Wyjście:

Na stosie zostaje zapisana wartość v, jeśli jest na to miejsce. Inaczej nic nie zostaje zapisane.

Dane pomocnicze:
e    wskaźnik elementu listy
Lista kroków:
K01 Utwórz element listy i umieść jego adres w e  
K02: edatav ; dane umieszczamy w polu data
K03: enextp ; następnikiem będzie bieżący szczyt stosu
K04: pe ; szczytem stosu staje się dodany element
K05: Zakończ  

 

Lazarus
procedure push(var p : PslistEl; v : typ_danych);
var
  e : PslistEl;
begin
  new(e);
  e^.data := v;
  e^.next := p;
  p := e;
end;
Code::Blocks
void push(slistEl * & p, typ_danych v)
{
  slistEl * e = new slistEl;
  e->data = v;
  e->next = p;
  p = e;
}
Free Basic
Sub push(ByRef p As slistEl Ptr, v As typ_danych)
  Dim e As slistEl Ptr
  e = New slistEl
  e->data = v
  e->next = p
  p = e
End Sub

 

Stos na liście – algorytm usuwania ze stosu

Wejście
p    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 p = nil, to zakończ ; stos jest pusty
K02: ep ; zapamiętujemy szczyt stosu
K03 ppnext ; usuwamy ze stosu bieżący szczyt
K04: Usuń z pamięci element wskazany przez e  
K05: Zakończ  

 

Lazarus
procedure pop(var p : PslistEl);
var
  e : PslistEl;
begin
  if p <> nil then
  begin
    e := p;
    p := p^.next;
    dispose(e);
  end
end;
Code::Blocks
void pop(slistEl * & p)
{
  if(p)
  {
    slistEl * e = p;
    p = p->next;
    delete e;
  }  
}
Free Basic
Sub pop(ByVal p as slistEl Ptr)
  Dim e As slistEl Ptr
  If p Then
    e = p
    p = p->next
    Delete e
  End If  
End Sub

 

Program

Ważne:

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.

 

Lazarus
// Stos na liście jednokierunkowej
// Data: 13.08.2012
// (C)2012 mgr Jerzy Wałaszek
//------------------------------

program slist_stack;

// Typ elementów listy
//--------------------
type
  PslistEl = ^slistEl;

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

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

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

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

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

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

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

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

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

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

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

// Zwraca wskazanie do szczytu stosu
//----------------------------------

function stack.top : PslistEl;
begin
  top := S;
end;

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

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

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

procedure stack.pop;
var
  e :PslistEl;
begin
  if S <> NIL then
  begin
    e := S;
    S := S^.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^.data);
    S.pop;
  end;

  S.destroy;
end.
Code::Blocks
// Stos na liście jednokierunkowej
// Data: 13.08.2012
// (C)2012 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>

using namespace std;

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

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

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

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

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

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

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

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

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

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

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

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

slistEl * stack::top(void)
{
  return S;
}

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

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

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

void stack::pop(void)
{
  if(S)
  {
    slistEl * e = S;
    S = S->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()->data << endl;
    S.pop();
  }
}
Free Basic
' Stos na liście jednokierunkowej
' Data: 13.08.2012
' (C)2012 mgr Jerzy Wałaszek
'------------------------------

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

Type slistEl
  next As slistEl Ptr
  data As Integer
End Type

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

  Public:

    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function top As slistEl Ptr
    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()->Data
  S.pop()
Wend

End

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

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

Constructor stack()
  S = 0
End Constructor

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

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

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

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

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

Function stack.top() As slistEl Ptr
  top = S
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 = S
  S = e
End Sub

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

Sub stack.pop()
  Dim e As slistEl Ptr
  If S Then
  	 e = S
  	 S = S->Next
  	 Delete e
  End If
End Sub
Wynik
10
9
8
7
6
5
4
3
2
1

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2019 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

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

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe