Стек – абстрактная структура данных, представляющий из себя список элементов, организованных по принципу LIFO – Last In First Out Интерфейс:
- Добавление (Push)
- Извлечение (Pop). Извлекается элемент, который добавляется последним.
Стек можно реализовать с помощью массива, списка и динамического массива
Очередь – абстрактная структура данных, представляющий из себя список элементов, организованных по принципу FIFO – First In First Out Интерфейс:
- Вставка (Enqueue)
- Извлечение (Dequeue). Извлекается элемент, который добавляется первым.
Очередь можно реализовать с помощью массива, списка, динамического массива, односвязного списка с указателем tail, с помощью двух стеков. Интересная реализация с помощью зацикленного массива
http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/8-List/array-queue2.html
Стек - все сложности константные.
очеред. Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим O(n) времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с O(1) истинного времени на операцию.