Какая структура данных лучше всего подходит для базовых стеков и очередей на C++?

Question

Я делаю некоторые проблемы HackerRank для новичков в C++, и я нахожу, что, кажется, существует несколько способов решения этой проблемы, и мне интересно, какой путь наиболее широко используется и/или наиболее эффективен. Задача требует создания класса, который содержит как переменные stack, так и queue, а также stack_push/stack_pop и queue_push/queue_pop функции для них.

Из того, что я гугле, кажется, я мог бы использовать либо std::vector, std::stack и std::queue или std::deque, и, возможно, другие.

Я не уверен, как определить, какой из них лучше всего использовать. Какие-либо предложения?

EDIT: я реализовал с помощью std::vector для обоих, а затем с помощью std::stack вместе с std::queue и я видел точно такую ​​же производительность с как для небольшого иш теста. EDIT2: С гораздо большим тестовым случаем это выглядит как std:stack/std:queue превосходит std:vector. Я предполагаю, что это из-за того, что половина очереди FIFO не эффективна с вектором, но мне нужно будет это проверить.

Answer 1

std::stack использует std::deque в качестве основного контейнера. Также std::queue. См http://en.cppreference.com/w/cpp/container/stack и http://en.cppreference.com/w/cpp/container/queue

Из указанной странице

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

Container - тип базового контейнера, чтобы использовать для хранения элементов. Контейнер должен удовлетворять требованиям SequenceContainer. Кроме того, он должен предоставить следующие функции с обычной семантикой: back() push_back() pop_back() Стандартные контейнеры std :: vector, std :: deque и std :: list удовлетворяют требованиям этих требований.

Если позволяет ситуация, я хотел бы использовать std::stack или std::queue, не заботясь о базовых деталей. Если мне нужно больше контролировать, я бы выбрал std::deque.

Answer 2

Правило большого пальца - это, во-первых, определить все ваши требования, а затем использовать простейшую структуру данных, которая отвечает всем им. Поскольку у вас нет требования к поиску, лучше всего будет реализовать связанный список в стиле C. Для Stack вам нужен только один указатель на передний элемент, но для очереди вам нужно будет поддерживать 2 указателя, чтобы отслеживать передний элемент, а также последний элемент. Вероятно, это будет самая быстрая реализация.