Блог

Мне нужна структура данных , которая содержит 3 операции: 1. push , 2. pop 3. has . Это похоже на стек с поиском элементов, подобных набору. has Операция должна возвращать значение true, если стек содержит аргумент. Мне нужна has быстрая операция, как ее выполнить?

Примеры:

1. нажмите(1), нажмите(2), нажмите(1), нажмите(). // Ожидайте, что(1) будет истинным.

Ну, вы могли бы привести аргумент, что, если вам нужен has/contains метод, он, вероятно, не должен быть стеком. Однако, если бы мне нужна была такая функциональность (и это был объектно-ориентированный язык), я бы просто унаследовал от фактического стека, а затем перехватил push pop вызовы и для поддержки другой альтернативной коллекции (например, отсортированного вектора с возможностью изменения размера, или отсортированного списка, или набора подсчетов, другого подходящего).

Каждый раз, когда что-то нажималось, я также добавлял это в альтернативную коллекцию. При появлении он также будет удален из альтернативной коллекции.

Затем ваши push pop операции и становятся (надеюсь, только) незначительно медленнее, и ваш has метод использует альтернативную коллекцию, которая, по-видимому, намного быстрее, чем был бы базовый стек (используя метод изучения каждого элемента в стеке, чтобы увидеть, есть ли там элемент).

И да, у вас могут быть дубликаты данных, но оптимизация часто является компромиссом между пространством и временем. В любом случае, вы могли бы в основном избежать какого-либо реального воздействия, используя указатели (ссылки) на элементы стека в альтернативной коллекции.

Поскольку вы не указали язык, а Python в любом случае является идеальным псевдокодом: -), вот как я бы подошел к нему на этом языке. Сначала базовый класс стека, в котором нет ничего, кроме push/pop :

 class Stack:
    def __init__(self):
        self.stack = []                 # Empty list to start.

    def push(self, item):
        self.stack.append(item)         # Add to list end.

    def pop(self):
        item = self.stack[-1]           # Get list end,
        self.stack = self.stack[:-1]    #   shorten list by one,
        return item                     #   and return it.
 

Класс, который наследуется от этого, вызывает базовый класс для каждого элемента, но также поддерживает словарь (ассоциативный массив), который сопоставляет элемент с числом (фактически набором подсчета).

 class AltStack(Stack):
    def __init__(self):
        super().__init__()               # Defer to base but
        self.alternate = {}              # also create alternate.

    def push(self, item):
        super().push(item)               # Defer to base but
        try:                             # also increment in
            self.alternate[item]  = 1    # alternate, creating if
        except KeyError:                 # not yet set.
            self.alternate[item] = 1

    def pop(self):
        item = super().pop()             # Defer to base. Then
        if self.alternate[item] == 1:    # decrement in alternate,
            del self.alternate[item]     # deleting item from
        else:                            # alternate when count
            self.alternate[item] -= 1    # reaches zero.
        return item

    def has(self, item):
        return item in self.alternate    # Use alternate for "has".
 

Тогда все, что вам нужно, — это простейшие тестовые ремни безопасности:

 my_stack = AltStack()

# Push 0, two each of 1-6, and 7.

for i in range(7):
    my_stack.push(i)
    my_stack.push(i 1)

# Pop each, displaying both it and whether stack has specific item.

for i in range(14):
    print("Popping", my_stack.pop(), "has(4)? =", my_stack.has(4))
 

Как вы можете видеть из (аннотированного) вывода, это работает так, как ожидалось:

 Popping 7 has(4)? = True  <-- 4 was pushed twice, has(4) true.
Popping 6 has(4)? = True
Popping 6 has(4)? = True
Popping 5 has(4)? = True
Popping 5 has(4)? = True
Popping 4 has(4)? = True  <-- first 4 popped, has(4) still true.
Popping 4 has(4)? = False <-- final 4 popped, has(4) now false.
Popping 3 has(4)? = False
Popping 3 has(4)? = False
Popping 2 has(4)? = False
Popping 2 has(4)? = False
Popping 1 has(4)? = False
Popping 1 has(4)? = False
Popping 0 has(4)? = False <-- and stay false forever.
 

Имейте в виду, что это пример, показывающий, как это можно сделать как концепцию. Я не принимаю решения о том, являются ли словари более эффективными, чем список, хотя подозреваю, что они предназначены для средних и больших структур. Поэтому постарайтесь запомнить природу этой концепции, прежде чем начнете поднимать вопросы о том, как я все делал.

Почему бы и нет, можно расширить класс структуры данных стека в java и добавить функциональность, чтобы реализовать указанный вами метод has/contains по мере необходимости. Если вы хотите, чтобы эта идея сработала, я могу написать для нее необходимый код.