class Maillon :
    def __init__(self) :
        self.valeur = None
        self.suivant = None
        
class PileChainee :
    def __init__(self) :
        self.tete = None

    def empile(self, e):
        m = Maillon()
        m.valeur = e
        m.suivant = self.tete
        self.tete = m
    
    def pile_vide(self):
        return self.tete is None # https://stackoverflow.com/questions/3257919/what-is-the-difference-between-is-none-and-none
        
    def depile(self):
        if self.pile_vide():
            return None
        else:
            m = self.tete
            self.tete = self.tete.suivant
            return m.valeur
            
    def getSommet(self):
        if self.pile_vide():
            return None
        else:
            return self.tete.valeur
    
    def __repr__(self):
        s = ''
        m = self.tete
        while m is not None:
            s += '|' + str(m.valeur) + '|\n'
            m = m.suivant
        return s
        
p =  PileChainee()
p.empile(1)
p.empile(2)
p.empile(3)
print(p)
a = p.depile()
print(p)
p.empile(4)
p.empile(a)
print(p)

class MaillonDouble :
    def __init__(self) :
        self.valeur = None
        self.suivant = None
        self.precedent = None
        
class FileChainee :
    def __init__(self) :
        self.tete = None
        self.queue = None
        
    def enfile(self, e):
        m = MaillonDouble()
        m.valeur = e
        if self.file_vide():
            self.tete = self.queue = m
        else:
            m.suivant = self.queue
            self.queue.precedent = m
            self.queue = m
        
    def file_vide(self):
        return self.tete is None
        
    def defile(self):
        if self.file_vide():
            return None
        else:
            v = self.tete.valeur
            if self.tete == self.queue:
                self.tete = self.queue = None
            else:
                self.tete = self.tete.precedent
                self.tete.suivant = None
            return v
            
    def tete(self):
        return self.tete.valeur 
    
    def __repr__(self):
        s = ''
        m = self.queue
        while m is not None:
            s += str(m.valeur)
            m = m.suivant
            if m is not None :
                s += '->'
        return s
    
f =  FileChainee()
f.enfile(1)
f.enfile(2)
f.enfile(3)
print(f)    # 3->2->1
a = f.defile()
print(f)    # 3->2
f.enfile(4)
f.enfile(a)
print(f)    # 1->4->3->2