Поиск определенного элемента в стеке

Question

Я заинтересован в портировании этого кода Python на C ++. В качестве части порта я использую std::stack из заголовка <stack>. Как я могу определить, содержится ли какой-либо символ в stack<char>? Например:

std::stack<char> myStack

if (!('y' is included in myStack)) // I know that this is wrong
{
}

Answer 1

C ++ stack не поддерживает произвольный доступ, поэтому нет прямого способа использовать stack для проверки наличия элемента.Однако вы можете сделать копию стека и затем непрерывно pop снимать этот стек до тех пор, пока не будет найден элемент.

В качестве альтернативы, если вам нужно выполнить поиск по stack, вы можете вместо этого использоватьdeque, который поддерживает произвольный доступ.Например, вы можете использовать алгоритм find на deque для поиска элемента:

find(myDeque.begin(), myDeque.end(), myValue);

Если вам нужны частые поиски stack, попробуйте сохранить параллель set вдольс stack, в котором хранятся те же элементы, что и stack.Таким образом, вы можете просто использовать set::find, чтобы проверить (эффективно), существует ли элемент.

Надеюсь, это поможет!

Answer 2

Если вам нужно найти элемент в вашем контейнере, по определению stack - это неправильный контейнер для ваших нужд.С крайне минимальным количеством информации, которую вы предоставили, либо vector, либо deque звучат так, будто они предоставят необходимый вам интерфейс (std::find(c.begin(), c.end(), item);).

Answer 3

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

stack<int> st; 
set<int> s;  


//push 
st.push(2);s.insert(2);

//pop
s.erase(st.top()); st.pop();

//find (what your main objective was)
bool ispresent = s.find(2)!=s.end() ; // on failure the iterator = s.end()

Answer 4

Поскольку вы хотите реализовать DFS и BFS, использование std::stack (для DFS) и std::queue (для BFS) действительно целесообразно, чтобы сохранить еще не посещенные узлы, и вам нужно только использовать push() и * 1004. * методы этих контейнеров.

Но стека и очереди недостаточно для сохранения посещенных узлов. Я бы предпочел использовать ассоциативный контейнер, например, std::set, еще лучше unordered_set, если он есть у вашего компилятора C ++, потому что поиск произвольного значения в ассоциативном контейнере выполняется быстрее, чем в последовательности, такой как vector или deque (если данные не отсортированы там).