Создание стека, который не может иметь повторяющиеся значения

Question

Я только вхожу в python, но у меня проблемы с концепцией стеков! У меня есть задание, которое требует от меня создания уникального стека, в котором не может быть двух одинаковых значений, однако я не совсем понимаю, как проходить через стек, чтобы проверить это.

from stack import Stack

 class UniqueStack(Stack):

    """ UniqueStack has the same methods and functionality as Stack, but will only store one copy of a particular item at a time. If push is called with an item that is already in the UniqueStack, a ValueError should be raised with an appropriate error message. If push is called where item equals None, a TypeError should be raised like in the base class. Define and implement the relevant methods from the base Stack class to enable the behavior described above. New versions of __init__(), push(), and pop() should be sufficient. Hint: One option to implement this is to maintain an internal set() alongside the internal list. """

У меня есть еще много вариантов, связанных со стеками, но если у кого-нибудь есть какие-либо мысли / советы о том, как запустить эту базовую, я возьму их!

Answer 1

Вот один подход, который использует set для отслеживания того, какие элементы уже находятся в стеке. Основные моменты:

1) При добавлении элемента проверяйте набор. И добавьте в стек и установите оба.

2) При удалении элемента обязательно удалите и из набора.

class UniqueStack(object):

    def __init__(self):
        self._seen = set()
        self._stack = list()

    def push(self, val):
        if val in self._seen:
            raise ValueError('Already in stack')
        self._stack.append(val)
        self._seen.add(val)

    def pop(self):
        if not self._stack:
            raise ValueError('stack is empty')
        retval = self._stack.pop(-1)
        self._seen.remove(retval)
        return retval

    def __str__(self):
        return '/'.join(map(str, self._stack))


if __name__ == '__main__':
    stack = UniqueStack()
    for i in range(5):
        stack.push(i)
    print(stack)
    try:
        stack.push(4) # Error
    except:
        print("Got error")
        pass
    print(stack.pop())
    stack.push(4)
    print(stack)

Выход:

0/1/2/3/4
Got error
4
0/1/2/3/4