Lucrul cu stive

Structuri de date și algoritmi în Python

Miriam Antona

Software Engineer

Stive

LIFO: Last-In First-Out
- Ultimul element inserat va fi primul eliminat

O imagine a unei stive de cărți.

Stive

LIFO: Last-In First-Out
- Ultimul element inserat este întotdeauna primul eliminat
Se poate doar adăuga la vârf
- Pushing pe stivă

O imagine a unei stive de cărți cu o carte nouă adăugată la vârf.

Stive

LIFO: Last-In First-Out
- Ultimul element inserat este întotdeauna primul eliminat
Se poate doar adăuga la vârf
- Pushing pe stivă
Se poate doar extrage din vârf
- Popping din stivă

O imagine a unei stive de cărți cu o carte luată din vârf.

Stive

LIFO: Last-In First-Out
- Ultimul element inserat este primul eliminat
Se poate doar adăuga la vârf
- Pushing pe stivă
Se poate doar elimina din vârf
- Popping din stivă
Se poate doar citi ultimul element
- Peeking din stivă

O imagine a unei stive de cărți cu o săgeată care indică coperta cărții din vârf.

Stive - utilizări reale

Funcționalitate Undo

O stivă cu un singur element.

Stive - utilizări reale

Funcționalitate Undo
- push pentru fiecare tastă apăsată

O stivă cu un element nou adăugat la vârf.

Stive - utilizări reale

Funcționalitate Undo
- push pentru fiecare tastă apăsată

O stivă cu un element nou adăugat la vârf.

Stive - utilizări reale

Funcționalitate Undo
- push pentru fiecare tastă apăsată

O stivă cu un element nou adăugat la vârf.

Stive - utilizări reale

Funcționalitate Undo
- push pentru fiecare tastă apăsată

O stivă cu un element nou adăugat la vârf.

Stive - utilizări reale

Funcționalitate Undo
- push pentru fiecare tastă apăsată
- pop pentru ultima tastă apăsată

O stivă din care a fost eliminat un element din vârf.

Stive - utilizări reale

Verificator de simboluri: ( [ { } ] )
- push pentru simboluri de deschidere

O stivă cu un simbol de deschidere.

Stive - utilizări reale

Verificator de simboluri: ( [ { } ] )
- push pentru simboluri de deschidere

O stivă cu un nou simbol de deschidere adăugat la vârf.

Stive - utilizări reale

Verificator de simboluri: ( [ { } ] )
- push pentru simboluri de deschidere

O stivă cu un nou simbol de deschidere adăugat la vârf.

Stive - utilizări reale

Verificator de simboluri: ( [ { } ] )
- push pentru simboluri de deschidere
- check simbolul de închidere

O stivă cu simboluri de deschidere și cuvântul "check" lângă "}".

Stive - utilizări reale

Verificator de simboluri: ( [ { } ] )
- push pentru simboluri de deschidere
- check simbolul de închidere
- pop simbolul de deschidere corespunzător

O stivă din care a fost eliminat un simbol de deschidere din vârf.

Stive - utilizări reale

Apeluri de funcții
- push bloc de memorie
- pop după finalizarea execuției

Stive - implementare cu liste simplu înlănțuite

O stivă reprezentată ca listă înlănțuită.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

Stive - implementare cu liste simplu înlănțuite

O stivă reprezentată ca listă înlănțuită cu denumirile părților nodurilor.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

Stive - implementare cu liste simplu înlănțuite

O stivă reprezentată ca listă înlănțuită cu cuvântul "TOP" indicând vârful stivei.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

Stive - push

O reprezentare a unei stive goale și a unei stive cu elemente.

def push(self, data):

Stive - push

O reprezentare a unei stive goale și a unei stive cu elemente, unde urmează să fie inserat un nod nou.

def push(self, data): 
  new_node = Node(data)

  if self.top:

Stive - push

O reprezentare a unei stive goale și a unei stive cu elemente, unde noul nod este conectat la elementul din vârf.

def push(self, data): 
  new_node = Node(data)
  if self.top:

    new_node.next = self.top

Stive - push

O reprezentare a unei stive goale și a unei stive cu elemente, unde noul nod a fost inserat.

def push(self, data): 
  new_node = Node(data)
  if self.top:
    new_node.next = self.top
  self.top = new_node

Stive - pop

def pop(self):

  if self.top is None:

    return None

  else:

O reprezentare a unei stive cu cuvântul "TOP" indicând nodul din vârf.

Stive - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top

O reprezentare a unei stive cu cuvântul "popped_node" indicând nodul din vârf.

Stive - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next

O reprezentare a unei stive cu "popped_node" indicând nodul din vârf și "TOP" indicând al doilea nod.

Stive - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None

O reprezentare a unei stive cu "popped_node" indicând un nod deconectat din stivă și "TOP" indicând nodul din vârf.

Stive - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None
    return popped_node.data

O reprezentare a unei stive cu cuvântul "TOP" indicând nodul din vârf.

Stive - peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None

LifoQueue în Python

LifoQueue:
- Modulul queue din Python
- se comportă ca o stivă

import queue


my_book_stack = queue.LifoQueue(maxsize=0)

my_book_stack.put("The misunderstanding")
my_book_stack.put("Persepolis")
my_book_stack.put("1984")


print("The size is: ", my_book_stack.qsize())

The size is: 3

print(my_book_stack.get())
print(my_book_stack.get())
print(my_book_stack.get())

1984
Persepolis
The misunderstanding

print("Empty stack: ", my_book_stack.empty())

Empty stack: True

Lass uns üben!

Structuri de date și algoritmi în Python