时间戳

首页 > 解决方案 > 创建一个不能有重复值的堆栈

python - 创建一个不能有重复值的堆栈

问题描述

我刚接触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. """

我有更多的变化与堆栈有关，但如果有人对如何开始这个基础有任何想法/提示，我会接受它们！

标签： pythonstack

解决方案

这是一种使用 aset来跟踪堆栈中已经存在哪些元素的方法。要点：

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

推荐阅读