Я читаю структуры данных и вижу стек и очередь, но я не получаю достаточных примеров в компьютерных системах или веб-разработке или особых проблемах, когда я должен использовать стек или очередь или дерево и т. Д.Использование стека и очереди?
Стеки используются большинством (всех?) Языков программирования, чтобы отслеживать состояние программы при вызове подпрограмм.
Пояснение: Код вашей программы хранится в основной памяти. CPU имеет указатель инструкции, который всегда указывает на следующую команду, которая будет выполнена. Когда инструкция выполнена, этот указатель увеличивается на единицу, указывая на следующую команду.
Когда ваша программа входит в подпрограмму, указатель инструкции переходит к другому адресу. Когда эта процедура закончена, она должна знать, откуда она. Итак, последний адрес перед скачком помещается в стек. Когда функция закончена, самым верхним элементом в стеке будет этот адрес.
Это также является причиной того, что чрезмерная рекурсия может привести к переполнению стека. Слишком много вложенных вызовов приводит к тому, что многие обратные адреса помещаются в стек, но ни один из них не удаляется.
Подробнее о Wikipedia.
Деревья могут использоваться для многих вещей, например binary search trees.
Можете ли вы, пожалуйста, описать «отслеживать состояние программы при вызове подпрограмм» –
@sushil: добавлено объяснение и ссылка для вызовов-стеков. –
Очереди являются общими, для обработки по принципу «первым пришел-первым-служите». Сетевые пакеты, запросы ввода-вывода и т. Д.
Вам нужен стек, когда вам нужно повторно использовать последний элемент, который вы положили на него снова. Я не могу найти хороший пример с верхней части шляпы, но он используется, например. в преобразовании нормальных математических выражений в RPN или для хранения узлов при выполнении поиска по глубине в графе.
Queue - First In First Out, используемый для последовательной обработки данных. Может использоваться для обработки задач в том порядке, в котором они были установлены. Стек - это противоположность очереди - Last In First Out, наиболее часто используемый пример - стек вызовов метода.
вы можете разработать сложный стек вызовов метода? –
@sushil - Как насчет более простого примера LIFO? Подумайте о функции отмены в текстовом процессоре. Вам нужно сохранить каждую вещь, которую вы сделали, чтобы ее можно было отменить позже, и когда вы ее открываете, вы хотите начать с последнего элемента (сверху стека) и вернуться назад к первому элементу. – JohnFx
@JohnFx - отличный пример! – dexter
В стеке удаление и вставка выполняются на одном конце. Так называется Last In First Out. В стеке используется только один указатель, который называется TOP.No потери памяти.
В случае удаления и вставки очереди выполняется на двух концах. Таким образом, он называется First In First Out. В очереди два указателя, называемые FRONT и REAR.Wastage пространства памяти.
Было ли ваше задание привести примеры использования стека, очередей или деревьев, возможно? –
нет заданий, мне просто интересно. Кроме того, я не студент колледжа. –
ха-ха-1 за то, что вам интересно. Anways по крайней мере у меня есть ответ. –