Arbeta med stackar

Datastrukturer och algoritmer i Python

Miriam Antona

Software Engineer

Stackar

  • LIFO: Last-In First-Out
    • Det senast tillagda elementet tas bort först

En bild på en stapel böcker.

Datastrukturer och algoritmer i Python

Stackar

  • LIFO: Last-In First-Out
    • Det senast tillagda elementet tas alltid bort först
  • Kan bara lägga till i toppen
    • Push till stacken

En bild på en stapel böcker med en ny bok lagd på toppen av stapeln.

Datastrukturer och algoritmer i Python

Stackar

  • LIFO: Last-In First-Out
    • Det senast tillagda elementet tas alltid bort först
  • Kan bara lägga till i toppen
    • Push till stacken
  • Kan bara ta från toppen
    • Pop från stacken

En bild på en stapel böcker där en bok tas från toppen av stapeln.

Datastrukturer och algoritmer i Python

Stackar

  • LIFO: Last-In First-Out
    • Det senast tillagda elementet tas alltid bort först
  • Kan bara lägga till i toppen
    • Push till stacken
  • Kan bara ta bort från toppen
    • Pop från stacken
  • Kan bara läsa det sista elementet
    • Peek på stacken

En bild på en stapel böcker med en pil som pekar på omslaget av boken längst upp i stapeln.

Datastrukturer och algoritmer i Python

Stackar – verkliga användningsområden

  • Ångra-funktionalitet

En stack med ett element.

Datastrukturer och algoritmer i Python

Stackar – verkliga användningsområden

  • Ångra-funktionalitet
    • push varje knapptryckning

En stack med ett nytt element lagt på toppen av stacken.

Datastrukturer och algoritmer i Python

Stackar – verkliga användningsområden

  • Ångra-funktionalitet
    • push varje knapptryckning

En stack med ett nytt element lagt på toppen av stacken.

Datastrukturer och algoritmer i Python

Stackar – verkliga användningsområden

  • Ångra-funktionalitet
    • push varje knapptryckning

En stack med ett nytt element lagt på toppen av stacken.

Datastrukturer och algoritmer i Python

Stackar – verkliga användningsområden

  • Ångra-funktionalitet
    • push varje knapptryckning

En stack med ett nytt element lagt på toppen av stacken.

Datastrukturer och algoritmer i Python

Stackar – verkliga användningsområden

  • Ångra-funktionalitet
    • push varje knapptryckning
    • pop senast tillagda knapptryckning

En stack där ett element har tagits bort från toppen av stacken.

Datastrukturer och algoritmer i Python

Stackar – verkliga användningsområden

  • Symbolkontroll: ( [ { } ] )
    • push öppningssymboler

En stack med en öppningssymbol.

Datastrukturer och algoritmer i Python

Stackar – verkliga användningsområden

  • Symbolkontroll: ( [ { } ] )
    • push öppningssymboler

En stack med en ny öppningssymbol lagd på toppen av stacken.

Datastrukturer och algoritmer i Python

Stackar – verkliga användningsområden

  • Symbolkontroll: ( [ { } ] )
    • push öppningssymboler

En stack med en ny öppningssymbol lagd på toppen av stacken.

Datastrukturer och algoritmer i Python

Stackar – verkliga användningsområden

  • Symbolkontroll: ( [ { } ] )
    • push öppningssymboler
    • kontrollera stängningssymbol

En stack med öppningssymboler och texten "check "}"".

Datastrukturer och algoritmer i Python

Stackar – verkliga användningsområden

  • Symbolkontroll: ( [ { } ] )
    • push öppningssymboler
    • kontrollera stängningssymbol
    • pop matchande öppningssymbol

En stack där en öppningssymbol har tagits bort från toppen av stacken.

Datastrukturer och algoritmer i Python

Stackar – verkliga användningsområden

  • Funktionsanrop
    • push minnesblock
    • pop när körningen avslutas
Datastrukturer och algoritmer i Python

Stackar – implementation med enkellänkade listor

En stack representerad som en länkad lista.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None
Datastrukturer och algoritmer i Python

Stackar – implementation med enkellänkade listor

En stack representerad som en länkad lista med namnen på nodernas delar.

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

class Stack:
  def __init__(self):
    self.top = None
Datastrukturer och algoritmer i Python

Stackar – implementation med enkellänkade listor

En stack representerad som en länkad lista med texten "TOP" som pekar på toppen av stacken.

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

class Stack:
  def __init__(self):
    self.top = None
Datastrukturer och algoritmer i Python

Stackar – push

En representation av en tom stack och en stack med element.

def push(self, data):
Datastrukturer och algoritmer i Python

Stackar – push

En representation av en tom stack och en stack med element, där en ny nod ska infogas.

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

  if self.top:
Datastrukturer och algoritmer i Python

Stackar – push

En representation av en tom stack och en stack med element, där den nya noden kopplas till elementet längst upp i stacken.

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

    new_node.next = self.top
Datastrukturer och algoritmer i Python

Stackar – push

En representation av en tom stack och en stack med element där den nya noden har infogats.

def push(self, data): 
  new_node = Node(data)
  if self.top:
    new_node.next = self.top
  self.top = new_node
Datastrukturer och algoritmer i Python

Stackar – pop

def pop(self):

  if self.top is None:

    return None

  else:

En representation av en stack med texten "TOP" som pekar på noden längst upp.

Datastrukturer och algoritmer i Python

Stackar – pop

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

En representation av en stack med texten "popped_node" som pekar på noden längst upp i stacken.

Datastrukturer och algoritmer i Python

Stackar – pop

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

En representation av en stack med texten "popped_node" som pekar på noden längst upp och texten "TOP" som pekar på den andra noden.

Datastrukturer och algoritmer i Python

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

En representation av en stack med texten "popped_node" som pekar på en nod frånkopplad från stacken och texten "TOP" som pekar på noden längst upp i stacken.

Datastrukturer och algoritmer i Python

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

En representation av en stack med texten "TOP" som pekar på noden längst upp i stacken.

Datastrukturer och algoritmer i Python

Stackar – peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None
Datastrukturer och algoritmer i Python

LifoQueue i Python

  • LifoQueue:
    • Pythons queue-modul
    • fungerar som en stack
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
Datastrukturer och algoritmer i Python

Nu kör vi en övning!

Datastrukturer och algoritmer i Python

Preparing Video For Download...