CODEWITHSUNDEEP
c++classstackqueuedeque
Austin
Austin

Reputation: 7319

Which data structure is best for basic stacks and queues in C++?

I'm doing some newbie HackerRank problems in C++ and I'm finding that there seems to be several ways to solve this problem and I'm wondering which way is most widely used and/or most efficient. The problem requires creating a class that contains both stack and queue variables as well as stack_push/stack_pop and queue_push/queue_pop functions for them.

From what I've googled it seems I could either use std::vector, std::stack and std::queue, or std::deque, and maybe others.

I'm not sure how to determine which is best to use. Any suggestions?

EDIT: I implemented using std::vector for both and then using std::stack along with std::queue and I saw the same exact performance with both for a small-ish test case. EDIT2: With a much bigger test case it looks like std:stack/std:queue outperforms std:vector. I'm guessing this is because of the FIFO queue half not being efficient with a vector, but I'll need to test this out more.

Upvotes: 2

Views: 1901

Answers (2)

Manish
Manish

Reputation: 11

The thumb rule is, first, identify all your requirements and then use the simplest data structure which meets all of them. Since you don't have a search requirement, the best will be to implement a C-style linked list. For the Stack, you need only one pointer to the front element, but for the Queue, you will have to maintain 2 pointers to keep track of the front element as well as the last element. This will probably be the fastest implementation.

Upvotes: 1

Arun
Arun

Reputation: 20383

std::stack uses std::deque as the underlying container. So does std::queue. See http://en.cppreference.com/w/cpp/container/stack and http://en.cppreference.com/w/cpp/container/queue

From the referenced page

template<
    class T,
    class Container = std::deque<T>
> class stack;

Container - The type of the underlying container to use to store the elements. The container must satisfy the requirements of SequenceContainer. Additionally, it must provide the following functions with the usual semantics: back() push_back() pop_back() The standard containers std::vector, std::deque and std::list satisfy these requirements.

If the situation permits, I would use std::stack or std::queue without bothering about the underlying details. If I have to take more control, I would choose std::deque.

Upvotes: 3

Related Questions