Python Stack Implementation

performance.py

from timer import Timer

from stack import Stack as S
from stack_optimized import Stack as SO


with Timer() as tstack:
    st = S(100)
    (st.push(i) for i in range(100, 200))
    (st.pop() for i in range(99))

print "=> Normal elasped lpush: %s s" % tstack.secs

with Timer() as tstackop:
    stop = SO(100)
    (stop.push(i) for i in range(100, 200))
    (stop.pop() for i in range(99))
print "=> Optimized elasped lpop: %s s" % tstackop.secs

stack.py

class StackOverflow(Exception):
    pass


class Stack(object):

    def __init__(self, size):
        self.stack = {}
        self.size = size

    def is_empty(self):
        if self.stack == {}:
            return True
        else:
            return False

    def push(self, element):
        counter = 0
        for e in self.stack:
            counter = counter + 1
        if counter > self.size:
            raise StackOverflow('The stack is full!')
        else:
            self.stack[counter] = element

    def pop(self):
        if self.is_empty():
            raise IndexError('The stack is is_empty')
        else:
            counter = 0
            for e in self.stack:
                counter = counter + 1
            counter = counter - 1
            if self.is_empty():
                raise IndexError('The stack is is_empty')
            else:
                element = self.stack[counter]
                del self.stack[counter]
                return element

stack_optimized

class StackOverflow(Exception):
    pass


class Stack(object):

    def __init__(self, size):
        self.stack = {}
        self.size = size

    def is_empty(self):
        return not self.stack and True or False

    def push(self, element):
        counter = sum((1 for e in self.stack))
        if counter > self.size:
            raise StackOverflow('The stack is full.')
        self.stack[counter] = element

    def pop(self):
        if self.is_empty():
            raise IndexError('The stack is_empty.')
        counter = sum((1 for e in self.stack)) - 1
        element = self.stack[counter]
        del self.stack[counter]
        return element

test_stack.py

import unittest
from stack import Stack, StackOverflow


class TestStack(unittest.TestCase):

    def test_create_stack_should_succeed(self):
        self.assertTrue(isinstance(Stack(1), Stack))

    def test_create_stack_wrongly_should_fail(self):
        with self.assertRaises(TypeError):
            Stack()

    def test_stack_emptiness_should_succeed(self):
        stack = Stack(1)
        self.assertTrue(stack.is_empty())

    def test_stack_push_should_succeed(self):
        stack = Stack(1)
        stack.push(1)
        self.assertFalse(stack.is_empty())

    def test_stack_overflow_should_succeed(self):
        with self.assertRaises(StackOverflow):
            stack = Stack(1)
            stack.push(1)
            stack.push(2)
            stack.push(3)

    def test_pop_a_non_empty_stack_should_succeed(self):
        stack = Stack(1)
        stack.push(1)
        stack.pop()
        self.assertTrue(stack.is_empty())

    def test_pop_an_empty_stack_should_fail(self):
        with self.assertRaises(IndexError):
            stack = Stack(1)
            stack.pop()

if __name__ == '__main__':
    unittest.main()

Implementação de stack em Python usando como referencia o artigo de Robert I. Pitts.

A implementação base utiliza somente construções e básicas da linguagem e conceitos simples do paradigma estruturado. Entretanto, pensei em seguir uma linha diferente do que usar a implementação funcional de stack que o Python já tem (listas) e usei dicionários para que poder explorar a manipulação manual dos índices da stack em nível de implementação.

Posterirormente criei uma versão "otimizada" do algoritmo, porém a otimização via só no nome pois não usa usa só construções padrões e com isso se torna mais lento. Uma possibilidade de ganho de performance real seria usar a estrutura padrão do Python que corresponderia a stacks, as listas.