Каков эффективный способ реализовать очередь?
Каков эффективный способ реализовать очередь, inorder, чтобы изучить, как он реализован?
Править: Я изучил stl:: код очереди inorder для изучения около, как это реализовано, но код шаблона, мешающий понять. В конце концов, существует лучший эффективный путь, используется, чем наличие связанного списка.
9 ответов
Конечно, для любого производственного кода вы должны полагаться на надежную реализацию библиотеки, которая уже выдержала испытание временем.
Тем не менее, для самообучения может быть интересно написать его самостоятельно. Я делал это раньше.
Самый эффективный способ, который я знаю, - это использовать подход, аналогичный тому, что делают большинство коллекций с изменяемым размером внутри: хранить массив, размер которого увеличивается (обычно удваивается) по мере необходимости, когда размер коллекции достигает длины массива.
Очередь немного отличается от обычной коллекции, потому что вы хотите иметь возможность выталкиваться с противоположного конца, откуда элементы выталкиваются.
Очевидно, что удалить первый элемент и сдвинуть все остальные элементы на один индекс вниз было бы дорогостоящим и бессмысленным. Поэтому вместо этого вы сами отслеживаете начальный и конечный индексы. Когда коллекция достигает конца массива, вы используете % , чтобы начать возвращать элементы в начало.
Ключ просто вычисляет так, чтобы вы обрабатывали все случаи, например, правильно наращивать массив, когда очередь заполнена, правильно проверять границы, увеличивать начальный индекс (или возвращаться в цикл до 0) при каждом всплывающем сообщении. и т. д.
Очевидно, что описанный выше дизайн имеет множество ограничений: например, безопасность потоков. Но для простой, однопоточной и эффективной реализации это довольно хорошая отправная точка.
Удачи - и я также рекомендую опубликовать свой код, если / когда у вас есть тот, который, по вашему мнению, работает!
Самый эффективный способ - попросить кого-нибудь сделать это.
И C ++, и C # (и .NET и др.) Имеют его в своих собственных библиотеках.
Если вам нужна реализация очереди с поддержкой потоков, вы можете попробовать мою собственную библиотеку . Он еще не завершен, но хорошо задокументирован.
Редактировать: он дополнен связными списками.
В самом общем смысле, связный список будет вашим лучшим выбором, если вы поддерживаете передний и задний указатель. В этом случае вставка и удаление очереди является операцией O(1). Вы также можете реализовать такую операцию, используя массив и сохраняя индексы для передней и задней частей. Математика здесь несколько сложнее (при вставке и удалении нужно учитывать "обертывание", чтобы избежать выхода за границы).
Сколько потоков могут одновременно читать вашу очередь? Сколько потоков могут одновременно записывать ее? Может ли один поток читать, а другой записывать? Хотите ли вы заранее выделить место под максимальный размер очереди? Нужен ли вам способ блокировать читателя в ожидании данных или писателя, когда очередь переполнена? Сколько объектов в секунду будет проходить через очередь?
Оптимальный подход будет зависеть от ответов на эти вопросы.
Если вы можете принять максимальный размер очереди, то круговой буфер является суперэффективным. Поскольку библиотечные функции не могут принять максимальный размер, они не используют эту технику.
Если ваша основная цель - узнать, как это реализовано, вам следует работать со связанными списками. С ними весело работать, они действительно демонстрируют отличие от последовательных массивов и многому учит о памяти.
Понимаете ли вы как работает очередь?
Понимаете ли вы как работает очередь stl?
Понимаете ли вы, что "наиболее эффективный" - это абстрактная концепция, которая не может быть верна для каждого случая?
Если вы понимаете все это, то "наиболее эффективный алгоритм очереди c++" придет к вам
.