Реализация стека с помощью Python

Я оставил комментарий со ссылкой на http://docs.python.org/2/tutorial/datastructures.html#using-lists-as-stacks, но если вы хотите иметь собственный тип, который предоставляет вам удобные методы push, pop, is_empty и size, я d просто подкласс list.

class Stack(list):
    def push(self, item):
        self.append(item)
    def size(self):
        return len(self)
    def is_empty(self):
        return not self

Однако, как я сказал в комментариях, я бы, вероятно, просто придерживался здесь прямой list, так как все, что вы на самом деле делаете, — это псевдонимы существующих методов, которые обычно служат только для того, чтобы ваш код было труднее использовать в долгосрочной перспективе, поскольку он требует, чтобы люди, использующие его, изучали ваш псевдоним интерфейса поверх оригинала.

Правильная реализация также будет включать __iter__, поскольку стек должен быть в порядке LIFO.

class Stack:
    def __init__(self):
        self._a = []

    def push(self, item):
        self._a.append(item)

    def pop(self):
        return self._a.pop()

    def isEmpty(self):
        return len(self._a) == 0

    def __iter__(self):
        return reversed(self._a)

    def __str__(self):
        # return str(list(reversed(self._a)))
        return str(list(iter(self)))

def main():
    stack = Stack()
    stack.push('a')
    stack.push('b')
    stack.push('c')
    stack.pop()
    print(stack)
    if stack:
        print("stack not empty")
    stack.pop()
    stack.pop()
    if stack.isEmpty():
        print("stack empty")

if __name__ == '__main__':
    main()

Стек — это контейнер (линейная коллекция), в котором операции с динамическими множествами выполняются по принципу «последний пришел — первый ушел» (LIFO). Есть только один указатель — top, который и используется для выполнения этих операций.

Реализация стека CLRS с использованием массива:

class Stack:
    """
    Last in first out (LIFO) stack implemented using array.
    """
    def __init__(self, capacity=4):
        """
        Initialize an empty stack array with default capacity of 4.
        """
        self.data = [None] * capacity
        self.capacity = capacity
        self.top  = -1

    def is_empty(self):
        """
        Return true if the size of stack is zero.
        """
        if self.top == -1:
            return True
        return False

    def push(self, element):
        """
        Add element to the top.
        """
        self.top += 1
        if self.top >= self.capacity:
            raise IndexError('Stack overflow!')
        else:
            self.data[self.top] = element

    def pop(self):
        """
        Return and remove element from the top.
        """
        if self.is_empty():
            raise Exception('Stack underflow!')
        else:
            stack_top = self.data[self.top]
            self.top -= 1
            return stack_top

    def peek(self):
        """
        Return element at the top.
        """
        if self.is_empty():
            raise Exception('Stack is empty.')
            return None
        return self.data[self.top]

    def size(self):
        """
        Return the number of items present.
        """
        return self.top + 1

Тестирование реализации:

def main():
    """
    Sanity test
    """
    stack = Stack()

    print('Size of the stack is:', stack.size())
    stack.push(3)
    print('Element at the top of the stack is: ', stack.peek())
    stack.push(901)
    print('Element at the top of the stack is: ', stack.peek())
    stack.push(43)
    print('Element at the top of the stack is: ', stack.peek())
    print('Size of the stack is:', stack.size())
    stack.push(89)
    print('Element at the top of the stack is: ', stack.peek())
    print('Size of the stack is:', stack.size())
    #stack.push(9)    # Raises IndexError
    stack.pop()
    print('Size of the stack is:', stack.size())
    stack.pop()
    print('Size of the stack is:', stack.size())
    stack.pop()
    print('Size of the stack is:', stack.size())
    print('Element at the top of the stack is: ', stack.peek())
    stack.pop()
    #print('Element at the top of the stack is: ', stack.peek())    # Raises empty stack exception

if __name__ == '__main__':
    main()

Ваша проблема в том, что вы выскакиваете из начала списка, когда вы должны выскакивать из конца списка. Стек — это структура данных «последний пришел — первый вышел». Это означает, что когда вы что-то выталкиваете из него, это что-то будет тем, что вы вставили последним. Взгляните на свою функцию push — она добавляет элемент в список. Это означает, что он идет в конце списка. Однако когда вы вызываете .pop(0), вы удаляете первый элемент в списке, а не тот, который вы добавили последним. Удаление 0 из .pop(0) должно решить вашу проблему.

Ваш стек представляет собой массив...

class stacked(): # Nodes in the stack
    def __init__(self,obj,next):
        self.obj = obj
        self.next = next
    def getObj(self):
        return(self.obj)
    def getNext(self):
        return(self.next)

class stack(): # The stack itself
    def __init__(self):
        self.top=None
    def push(self,obj):
        self.top = stacked(obj,self.top)
    def pop(self):
        if(self.top == None):
            return(None)
        r = self.top.getObj()
        self.top = self.top.getNext()
        return(r)

Ниже приведена простая реализация стека в python. Кроме того, он возвращает средний элемент в любой момент времени.

  class Stack:
        def __init__(self):
            self.arrList = []

        def isEmpty(self):
            if len(self.arrList):
                return False
            else:
                return True

        def push(self, val):
            self.arrList.append(val)

        def pop(self):
            if not self.isEmpty():
                self.arrList[len(self.arrList)-1]
                self.arrList = self.arrList[:len(self.arrList)-1]
            else:
                print "Stack is empty"

        def returnMiddle(self):
            if not self.isEmpty():
                mid = len(self.arrList)/2
                return self.arrList[mid]
            else:
                print "Stack is empty"

        def listStack(self):
            print self.arrList

    s = Stack()
    s.push(5)
    s.push(6)
    s.listStack()
    print s.returnMiddle()
    s.pop()
    s.listStack()
    s.push(20)
    s.push(45)
    s.push(435)
    s.push(35)
    s.listStack()
    print s.returnMiddle()
    s.pop()
    s.listStack()

Выход:

[5, 6]
6
[5]
[5, 20, 45, 435, 35]
45
[5, 20, 45, 435]

Реализация стека в Python из книги "Решение проблем с помощью алгоритмов и Структуры данных

Ниже моя реализация

class Stack:
    def __init__(self):
        self.items = list()
    def is_empty(self):
        return self.items == []
    def peek(self):
        if self.is_empty():
            print('Cannot peek empty stack')
            return
        else:
            return self.items[-1]
    def pop(self):
        if self.is_empty():
            print('Cannot pop an empty stack')
            return
        else:
            return self.items.pop()
    def size(self):
        return len(self.items)
    def push(self,data):
        self.items.append(data)

Я хотел бы поделиться своей версией реализации стека, которая наследует список Python. Я считаю, что итерация в стеке должна происходить в порядке LIFO. Кроме того, должна быть предусмотрена итерация pop-all() для итерации при извлечении всех элементов. Я также добавил stack.clear() для очистки стека (как в deque.clear() в модуле коллекций). Я также переопределил __repr__ для целей отладки:

class Stack(list):

    def push(self, item):
        self.append(item)

    def top(self):
        return self[-1]

    def size(self):
        return len(self)

    def isempty(self):
        return self.size() == 0

    def __iter__(self):
        """ iter in lifo """
        return super(Stack, self).__reversed__()

    def __reversed__(self):
        return super(Stack, self).__iter__()

    def popall(self):
        try:
            while True:
                yield self.pop()
        except IndexError:
            pass

    def clear(self):
        del self[:]

    def __repr__(self):
        if not self:
            return '%s()' % self.__class__.__name__
        return '%s(%s)' % (self.__class__.__name__, super(Stack, self).__repr__())

Вот как вы можете его использовать:

stack = Stack(range(5))
print "stack: ", stack  # stack:  Stack([0, 1, 2, 3, 4])

print "stack.pop() => ", stack.pop() # stack.pop() =>  4
print "stack.push(20) " # stack.push(20) 
stack.push(20)
for item in stack:
    print item  # prints 20, 3, 2... in newline
print "stack: ", stack # stack:  Stack([0, 1, 2, 3, 20])
print "stack pop all..."
for item in stack.popall(): # side effect to clear stack
    print item
print "stack: ", stack # stack:  Stack()

Прежде всего, я реализовал его для решения проблемы программирования следующий больший элемент< /а>.