Создание очереди FIFO в C

Question

Возможно ли создать FIFO-стек в C без использования 2 стеков?

Спасибо!

(Извините тем, кто ответил на предыдущий. Я думал LIFO и имел в виду FIFO.)

Answer 1

Это очень просто. Просто реализуйте двусвязный список, удерживая указатель на последний элемент в списке.

Чтобы добавить в очередь, создайте новый узел в начале, связав его с предыдущим началом. (обычная вставка списка)

Чтобы удалить из очереди, отмените указатель на последний элемент, измените указатель на указатель предыдущего элемента и верните последний элемент ... (Вот почему список с двойной связью. Другой вариант - односвязный список и итерация всего списка для получения указателей на последние два элемента).

Answer 2

Разве это не просто стандартный связанный список, за исключением того, что вы определяете только функции, которые вытягивают элемент head и помещают материал в элемент tail? Вы можете даже сделать это в односвязном списке с указателем хвоста, а не в полностью двусвязном списке.

Answer 3

Звучит так, будто вы пытаетесь создать очередь, в которую вы вставляете с одного конца и вытягиваете с другого.

Один из способов сделать это с помощью связанного списка. Вы можете хранить указатели на голову и хвост. Когда вы вставляете, добавляете новую запись в хвост, и когда вы вытаскиваете что-то из очереди, вы берете узел, на который указывает указатель головы. (Или наоборот, это не имеет большого значения)

Answer 4

Хотя правильные решения уже предложены, я просто хотел бы исправить, что FIFO на самом деле не стек.

Этот вопрос часто встречается в классе «Алгоритмы», где вас просят построить один с использованием стеков и доказать, что амортизированная стоимость для вставки и удаления равна O (1).

FIFO могут быть построены с использованием двусвязного списка, массива / вектора с указателем начала и конца, с круговыми массивами и т. Д. И т. Д. *

Answer 5

Вы также можете реализовать очередь с круговым массивом .

Answer 6

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

Answer 7

Я думаю, что ОП хотел знать, как с этим справиться, если у него есть только стеки, по какой-то непонятной причине. Хитрость заключается в том, что нужно помнить, что если положить вещи в стек, а затем вытащить их, обратный порядок элементов меняется, так что вы можете использовать два стека, чтобы перевернуть его дважды.

Входящие элементы помещаются в стек1 и все попадают в стек2, когда стек2 пуст. Таким образом, первый элемент помещается в stack1, сразу же извлекается и помещается в stack2, готовый к выводу. Последующие элементы складываются в стеке 1 до тех пор, пока стек 2 не будет извлечен, после чего последний элемент помещается в стек 2, затем следующий за последним и т. Д., Пока стек 1 снова не опустеет. Теперь все элементы пересортированы в стек2, причем самые новые находятся внизу, а самые старые - вверху. Новые толчки продолжают накапливаться в stack1, ожидая, пока stack2 снова станет пустым, и stack2 просто создает элементы в исходном порядке, пока не опустеет, после чего мы повторяем процесс unstack-restck.

Я не буду комментировать эффективность и т. Д .; это просто "вы могли бы сделать это таким образом". Меня спросили об этом в интервью, и мой немедленный ответ был: «Какой идиот будет делать это? Просто создайте реальную очередь и покончите с этим» - я не думаю, что это был ответ, который они ищем хоть.