Check that element belongs to std::stack

Question

I have a problem to write code / function that will check that number which provides user belongs to std::stack or not. I tried making it in different ways but I haven't found any working solutions.

I tried:

std::stack<int> myStack;
const bool isInStack = myStack.find(userNumber) != myStack.end();

I tried also:

std::stack<int> myStack;
if (myStack.count(userNumber)) {
   // x is in the set, count is 1
} else {
   // count zero, i.e. x not in the set
}

I tried also to write own template but I couldn't and it also wasn't working. I don't have any idea how can I make it working.

I get errors like class std::stack<int, std::deque<int, std::allocator<int>>>" has no member "find"

Can anyone help me? I'm really getting annoyed with it.

When getting error about using a standard library component, [check the reference](https://en.cppreference.com/w/cpp/container/stack) first to make sure you are using it correctly. As you can see in the link, `std::stack` doesn't have a `find` or `count` function. Are you sure you should be using a `std::stack` and not a `std::set`? — NathanOliver, Jun 07 '21 at 14:02
`std::stack` provides a stack interface, that it, you can push a new element onto the top of the stack, and you can pop the top element. If you need more operations than that, `std::stack is not the appropriate container. `std::vector` provides `push_back` and `pop_back`, so it can be used as a stack, and it gives access to all of its elements. — Pete Becker, Jun 07 '21 at 14:04
I know that I can do it with vector but my job is to do it using stack... I don't have any ideas how can I do this. Maybe I can create helper stack or sth but I don't know how — Oliwier Piasecki, Jun 07 '21 at 14:05
`std::stack` should work as a stack so `Last In First Out` functionality. This template provides minimal API to fulfill LIFO requirements. Random or sequential access to elements are not allowed. So basically you should replace `std::stack` with other container. If your task say something else, maybe you could provide full description, so we could have clear understanding why you have this strange requirement. — Marek R, Jun 07 '21 at 14:05
You are asking how to screw in a screw using a hammer. `std::stack` is not the right tool for this. If you *have* to use `std::stack` then you probably need to empty out the stack to inspect each element, for example move out each element of the stack to another stack, inspecting each element to see if it is the one you are looking for. Strictly speaking, it is possible to derive from `std::stack` to access the `protected` member `c` you can access the underlying container directly. But this is usually a very contrived solution. The right solution is to not use `std::stack` for this. — François Andrieux, Jun 07 '21 at 14:08
is this an assignment that impose you to use std::stack? if so, you cannot do much else than copy and stack an pop it until you find your element or empty it. Pretty inefficient but there is no other way with std::stack — Alessandro Teruzzi, Jun 07 '21 at 14:09
@OliwierPiasecki -- *Can anyone help me? I'm really getting annoyed with it* -- Maybe the person giving you this assignment knows that there is no `find` function, and it's your job to figure out how to manipulate the stack to check if the item exists. So "being annoyed by it" was the intention of the assignment. — PaulMcKenzie, Jun 07 '21 at 14:48

mattlangford · Accepted Answer · 2021-06-07T14:09:20.553

As others have noted, a std::stack is probably not the best thing to be using, but assuming you have no other option then you'll have to go through the stack one by one and check each element:

bool found_in_stack(int to_find, std::stack<int> stack) {
    while (!stack.empty()) {
        if (stack.top() == to_find) return true;
        stack.pop();
    }
    return false;
}

Notice that I take the stack by value so that a copy is made, this way the original stack isn't changed at all.

Another option would be to mutate the original if you don't want to make a copy, this would require temporarily storing popped elements:

bool found_in_stack(int to_find, std::stack<int>& stack) {
    // keep track of elements we've popped here, we'll add them back at the end
    std::stack<int> tmp;

    bool done = false;
    while (!stack.empty()) {
        if (stack.top() == to_find) {
            done = true;
            break;
        }
        
        tmp.push(stack.top());
        stack.pop();
    }

    // add popped elements back
    while (!tmp.empty()) {
        stack.push(tmp.top());
        tmp.pop();
    }
    return done;
}

The second solution has the advantage that it works with non-copyable types too, and might be faster for types that may be slow to copy like large containers or strings. However, the big trade-off is that it is not exception safe. For example is `tmp.push` throws then `stack` will not have its original value. — François Andrieux, Jun 07 '21 at 14:15

silverfox · Answer 2 · 2021-06-07T14:15:20.687

There're no find in std::stack, but you can use std::deque, which provides the same functionality. Use push_back() for push() and pop_back() for pop(). std::vector also provides such functionalities.

Example code:

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

int main()
{
    deque<int> x;
    for (int i = 1; i <= 5; i++) {x.push_back(i);}

    if (find(x.begin(), x.end(), 5) != x.end()) {cout << "Yes";} else {cout << "No";} 
    cout << "\n";
    if (find(x.begin(), x.end(), 7) != x.end()) {cout << "Yes";} else {cout << "No";}
}

Output:

Yes
No

Edit : std::deque is a container template, and std::stack is built upon it (as @François Andrieux mentioned):

template<
    class T,
    class Container = std::deque<T>
> class stack;
//Defined in header <stack>

Documentation:

The std::stack class is a container adapter that gives the programmer the functionality of a stack - specifically, a LIFO (last-in, first-out) data structure.

In general it'll have essentially the same functionality. More info here.

The OP is required to use a `stack` – NathanOliver Jun 07 '21 at 14:09 — NathanOliver, Jun 07 '21 at 14:09

Mestkon · Answer 3 · 2021-06-07T14:21:26.827

std::stack has no public interface to check what exists in the stack without popping every element and check them.

What it does have is a protected member variable of the underlying container.

So if you must use std::stack, the only way is to inherit from it and access the underlying container

template<class T>
class my_stack : private std::stack<T>
{
public:
    using std::stack<T>::stack;
    using std::stack<T>::operator=;

    using std::stack<T>::top;
    using std::stack<T>::empty;
    using std::stack<T>::size;
    using std::stack<T>::push;
    using std::stack<T>::emplace;
    using std::stack<T>::pop;
    using std::stack<T>::swap;
    
    using typename std::stack<T>::const_reference;

    bool contains(const_reference val) const
    {
        return std::find(this->c.begin(), this->c.end(), val) != this->c.end();
    }
};

Check that element belongs to std::stack

3 Answers3