A pila és una estructura de dades lineal que emmagatzema elements en a Darrer en entrar/primer en sortir (LIFO) o manera First In/Last-Out (FILO). A la pila, s'afegeix un element nou en un extrem i només s'elimina un element d'aquest extrem. Les operacions d'inserció i supressió sovint s'anomenen push i pop.

Les funcions associades a la pila són:

• buit() – Retorna si la pila està buida – Complexitat temporal: O(1)
• mida () – Retorna la mida de la pila – Complexitat temporal: O(1)
• amunt () / cop d'ull () – Retorna una referència a l'element superior de la pila – Complexitat temporal: O(1)
• empènyer (a) – Insereix l'element ‘a’ a la part superior de la pila – Complexitat temporal: O(1)
• pop() – Elimina l'element superior de la pila – Complexitat temporal: O(1)

Implementació:

Hi ha diverses maneres d'implementar una pila a Python. Aquest article tracta la implementació d'una pila utilitzant estructures de dades i mòduls de la biblioteca Python.
La pila a Python es pot implementar de les maneres següents:

• llista
• Col·leccions.deque
• queue.LifoQueue

Implementació mitjançant llista:

La llista d'estructura de dades integrada de Python es pot utilitzar com a pila. En lloc de push(), append() s'utilitza per afegir elements a la part superior de la pila mentre que pop() elimina l'element en ordre LIFO.
Malauradament, la llista té algunes mancances. El problema més gran és que pot tenir problemes de velocitat a mesura que creix. Els elements de la llista s'emmagatzemen un al costat de l'altre a la memòria, si la pila creix més que el bloc de memòria que la conté actualment, llavors Python ha de fer algunes assignacions de memòria. Això pot provocar que algunes trucades a append() triguin molt més que altres.

# Python program to # demonstrate stack implementation # using list stack = [] # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack ['a', 'b', 'c'] Elements popped from stack: c b a Stack after elements are popped: []>

Implementació mitjançant collections.deque:

La pila de Python es pot implementar mitjançant la classe deque del mòdul de col·leccions. Deque es prefereix a la llista en els casos en què necessitem operacions d'afegir i pop més ràpides des dels dos extrems del contenidor, ja que deque proporciona una complexitat de temps O(1) per a les operacions d'afegir i pop en comparació amb la llista que proporciona O (n) complexitat temporal.

S'utilitzen els mateixos mètodes de deque que es veuen a la llista, append() i pop().

# Python program to # demonstrate stack implementation # using collections.deque from collections import deque stack = deque() # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack:') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack: deque(['a', 'b', 'c']) Elements popped from stack: c b a Stack after elements are popped: deque([])>

Implementació mitjançant mòdul de cua

El mòdul de cua també té una cua LIFO, que bàsicament és una pila. Les dades s'insereixen a la cua mitjançant la funció put() i get() treu les dades de la cua.

Hi ha diverses funcions disponibles en aquest mòdul:

• mida màxima – Nombre d'elements permesos a la cua.
• buit() – Retorna True si la cua està buida, False en cas contrari.
• ple () – Retorna True si n'hi ha mida màxima elements de la cua. Si la cua s'ha inicialitzat amb maxsize=0 (per defecte), aleshores full() no retorna mai True.
• aconseguir() – Eliminar i tornar un element de la cua. Si la cua està buida, espereu fins que hi hagi un element disponible.
• get_nowait() – Retorna un element si n'hi ha un disponible immediatament, en cas contrari, puja QueueEmpty.
• posar (element) – Posa un article a la cua. Si la cua està plena, espereu fins que hi hagi un espai lliure abans d'afegir l'element.
• put_nowait(element) – Posa un article a la cua sense bloquejar. Si no hi ha cap ranura lliure disponible immediatament, augmenta QueueFull.
• qsize() – Retorna el nombre d'elements de la cua.

# Python program to # demonstrate stack implementation # using queue module from queue import LifoQueue # Initializing a stack stack = LifoQueue(maxsize=3) # qsize() show the number of elements # in the stack print(stack.qsize()) # put() function to push # element in the stack stack.put('a') stack.put('b') stack.put('c') print('Full: ', stack.full()) print('Size: ', stack.qsize()) # get() function to pop # element from stack in # LIFO order print('
Elements popped from the stack') print(stack.get()) print(stack.get()) print(stack.get()) print('
Empty: ', stack.empty())>

0 Full: True Size: 3 Elements popped from the stack c b a Empty: True>

Implementació mitjançant una llista enllaçada individualment:

La llista enllaçada té dos mètodes addHead(item) i removeHead() que s'executen en temps constant. Aquests dos mètodes són adequats per implementar una pila.

• getSize() – Obteniu el nombre d'elements de la pila.
• està buit() – Retorna True si la pila està buida, False en cas contrari.
• ullada() – Retorna l'element superior de la pila. Si la pila està buida, planteja una excepció.
• push(valor) – Introduïu un valor al capçal de la pila.
• pop() – Eliminar i retornar un valor al capçal de la pila. Si la pila està buida, planteja una excepció.

A continuació es mostra la implementació de l'enfocament anterior:

# Python program to demonstrate # stack implementation using a linked list. # node class class Node: def __init__(self, value): self.value = value self.next = None class Stack: # Initializing a stack. # Use a dummy node, which is # easier for handling edge cases. def __init__(self): self.head = Node('head') self.size = 0 # String representation of the stack def __str__(self): cur = self.head.next out = '' while cur: out += str(cur.value) + '->' cur = cur.next return out[:-2] # Obteniu la mida actual de la pila def getSize(self): return self.size # Comproveu si la pila està buida def isEmpty(self): return self.size = = 0 # Obteniu l'element superior de la pila def peek(self): # Comprovació sanitària per veure si # estem mirant una pila buida. if self.isEmpty(): retorna Cap retorn self.head.next.value # Introdueix un valor a la pila. def push(self, value): node = Node (valor) node.next = self.head.next # Feu que el nou node apunti al cap actual self.head.next = node #!!! # Actualitza el cap per ser el nou node self.size += 1 # Elimina un valor de la pila i torna. def pop(self): if self.isEmpty(): genera l'excepció ('Sortant d'una pila buida') remove = self.head.next self.head.next = remove.next #!!! s'ha canviat self.size -= 1 retorna remove.value # Codi del controlador if __name__ == '__main__': stack = Stack() for i in range(1, 11): stack.push(i) print(f' Pila: {pila}') per a _ dins l'interval (1, 6): valor_superior = stack.pop() print(f'Pop: {valor_superior}') # el nom de la variable ha canviat print(f'Pila: { pila}')>>> 
    Sortida    
 Les piles són estructures de dades simples amb un conjunt d'operacions ben definit, que les fa fàcils d'entendre i utilitzar.
Les piles són eficients per afegir i eliminar elements, ja que aquestes operacions tenen una complexitat temporal de O(1).
Per invertir l'ordre dels elements utilitzem l'estructura de dades de la pila.
Les piles es poden utilitzar per implementar funcions de desfer/refer a les aplicacions.
    Inconvenients de Stack:    
La restricció de mida a la pila és un inconvenient i si estan plenes, no podeu afegir més elements a la pila.
Les piles no proporcionen accés ràpid a elements que no siguin l'element superior.
Les piles no admeten cerques eficients, ja que heu d'explotar els elements un per un fins que trobeu l'element que busqueu.