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

SPIS TREŚCI W KONSERWACJI

Wstęp
Przedziały liczbowe i liczby
Tablice – wektory
Łańcuchy znakowe
Macierze
Listy
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
Kolejki
Drzewa
Zbiory
Grafy
Sieci przepływowe

Tematy pomocnicze

Podrozdziały

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ę

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 szczytu stosu – operacja top zwraca element (zwykle jest to wskaźnik) znajdujący się na szczycie 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 szczytu stosu znajdujący się tam element.

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.

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:

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

Pascal

function empty : boolean;
begin
  if sptr = 0 then empty := true
  else empty := false;
end;

C++

bool empty (void)
{
  return !sptr;
}

Basic

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, o 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

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:	sptr ← sptr + 1	zwiększamy wskaźnik 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

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 sptr ← sptr - 1	jeśli stos coś zawiera, to usuwamy element na szczycie 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

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

Na początek: podrozdziału 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
  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

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

Pascal

…
var stack : PslistEl;
…

C++

…
slistEl * stack;
…

Basic

…
Dim stack As slistEl Ptr
…

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

Pascal

…
stack := NIL;
…

C++

…
stack = NULL;
…

Basic

…
stack = 0
…

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

Wejście:

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

Pascal

function empty (p : PslistEl) : boolean;
begin
  if p = nil then empty := true
  else empty := false;
end;

C++

bool empty (slistEl * p)
{
  return !p;
}

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:

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

Pascal

function top (p : PslistEl) : PslistEl;
begin
  top := p;
end;

C++

slist * top (slistEl * p)
{
  return p;
}

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:

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 ← p	następnikiem będzie bieżący szczyt stosu
K04:	p ← e	szczytem stosu staje się dodany element
K05:	Zakończ

Pascal

procedure push (var p : PslistEl; v : typ_danych);
var
  e : PslistEl;
begin
  new (e);
  e^.data := v;
  e^.next := p;
  p := e;
end;

C++

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

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:

wskaźnik szczytu stosu

Wyjście:

Ze szczytu stosu zostaje usunięty element.

Dane pomocnicze:

wskaźnik elementu listy

Lista kroków:

K01	Jeśli p = nil, to zakończ	stos jest pusty
K02:	e ← p	zapamiętujemy szczyt stosu
K03	p ← p→next	usuwamy ze stosu bieżący szczyt
K04:	Usuń z pamięci element wskazany przez e
K05:	Zakończ

Pascal

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

C++

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

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

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;

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

C++

// Stos na liście jednokierunkowej
// Data: 13.08.2012
// (C)2020 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();
  }
}

Basic

' Stos na liście jednokierunkowej
' Data: 13.08.2012
' (C)2020 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

Na początek: podrozdziału 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

Tablica jako stos

Stos w tablicy – algorytm sprawdzania, czy stos jest pusty

Wejście:

Wyjście:

Stos w tablicy – algorytm odczytu szczytu stosu

Wejście:

Wyjście:

Stos w tablicy – algorytm zapisu na stos

Wejście:

Wyjście:

Stos w tablicy – algorytm usuwania ze stosu

Wejście:

Wyjście:

Przykładowe programy

Lista jako stos

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

Wejście:

Wyjście:

Stos na liście – algorytm odczytu szczytu stosu

Wejście:

Wyjście:

Stos na liście – algorytm zapisu na stos

Wejście:

Wyjście:

Dane pomocnicze:

Stos na liście – algorytm usuwania ze stosu

Wejście:

Wyjście:

Dane pomocnicze:

Przykładowe programy