В чем разница между queue и deque и stack

В чем суть использования в C++ stack и queue, если можно использовать vector, deque или list?

Я только начал изучать C++, и у меня возник вопрос: зачем использовать stack и queue, если можно вместо них использовать vector, deque или list? Неужели так мешаются лишние функции или stack и queue работают быстрее?

Отслеживать
51.6k 204 204 золотых знака 67 67 серебряных знаков 251 251 бронзовый знак
задан 21 июл 2022 в 13:14
41 3 3 бронзовых знака

Да хотя бы потому, что использование какого-нибудь вектора будет тянуть за собой возможность его использования не как стека 🙂 Рассказывать в ответ о «самоограничении программиста» не стоит.

21 июл 2022 в 13:18
Для справки, что когда применять — stackoverflow.com/questions/10699265/…
21 июл 2022 в 13:27

Работают не быстрее. Чтобы оставить задел на смену используемого внутри контейнера? Но мне это всегда казалось сомнительной идеей.

21 июл 2022 в 17:04

@HolyBlackCat, это прекрасная идея. Например DFS и BFS — один и тот же алгоритм если менять стек на очередь.

22 июл 2022 в 10:08

Это не вопрос производительности. Это вопрос простоты и выразительности. Если в коде написано stack я не буду ждать что кто-то обратиться к его среднему элементу. Пока код прост — это не важно. Чем сложнее код, тем важнее чтобы кирпичики из которых он складывается были или казались простыми.

c++ deque vs queue vs stack

Queue and Stack are a structures widely mentioned. However, in C++, for queue you can do it in two ways:

#include #include

but for stack you can only do it like this

#include

My question is, what’s the difference between queue and deque, why two structures proposed? For stack, any other structure could be included?

1,220 4 4 gold badges 16 16 silver badges 28 28 bronze badges
asked Feb 11, 2010 at 21:51
25.5k 52 52 gold badges 150 150 silver badges 203 203 bronze badges

9 Answers 9

Moron/Aryabhatta is correct, but a little more detail may be helpful.

Queue and stack are higher level containers than deque, vector, or list. By this, I mean that you can build a queue or stack out of the lower level containers.

 std::stack > s; std::queue > q; 

Will build a stack of ints using a deque as the underlying container and a queue of doubles using a list as the underlying container.

You can think of s as a restricted deque and q as a restricted list.

All that is necessary is that the lower level container implements the methods needed by the higher level container. These are back() , push_back() , and pop_back() for stack and front() , back() , push_back() , and pop_front() for queue.

See stack and queue for more detail.

With respect to the deque, it is much more than a queue where you can insert at both ends. In particular, it has the random access operator[] . This makes it more like a vector, but a vector where you can insert and delete at the beginning with push_front() and pop_front() .

what is the basic difference between stack and queue?

What is the basic difference between stack and queue?? Please help me i am unable to find the difference. How do you differentiate a stack and a queue? I searched for the answer in various links and found this answer.. In high level programming, a stack is defined as a list or sequence of elements that is lengthened by placing new elements «on top» of existing elements and shortened by removing elements from the top of existing elements. It is an ADT[Abstract Data Type] with math operations of «push» and «pop». A queue is a sequence of elements that is added to by placing the new element at the rear of existing and shortened by removing elements in front of queue. It is an ADT[Abstract Data Type]. There is more to these terms understood in programming of Java, C++, Python and so on. Can i have an answer which is more detailed? Please help me.

8,506 11 11 gold badges 53 53 silver badges 68 68 bronze badges
asked Jun 11, 2012 at 5:39
Harish Rachakonda Harish Rachakonda
1,591 3 3 gold badges 12 12 silver badges 7 7 bronze badges

You seem to have answered your own question — a stack is a Last-In First-Out (LIFO) container, and a queue is a First-In First-Out (FIFO) container.

Jun 11, 2012 at 5:47

12 Answers 12

Stack is a LIFO (last in first out) data structure. The associated link to wikipedia contains detailed description and examples.

Queue is a FIFO (first in first out) data structure. The associated link to wikipedia contains detailed description and examples.

answered Jun 11, 2012 at 5:46
3,415 1 1 gold badge 17 17 silver badges 32 32 bronze badges

Imagine a stack of paper. The last piece put into the stack is on the top, so it is the first one to come out. This is LIFO. Adding a piece of paper is called «pushing», and removing a piece of paper is called «popping».

Imagine a queue at the store. The first person in line is the first person to get out of line. This is FIFO. A person getting into line is «enqueued», and a person getting out of line is «dequeued».

2,295 1 1 gold badge 14 14 silver badges 20 20 bronze badges
answered Jan 27, 2016 at 7:28
8,853 15 15 gold badges 60 60 silver badges 103 103 bronze badges

Pancake Stack (LIFO)

The only way to add one and/or remove one is from the top.

Line Queue (FIFO)

When one arrives they arrive at the end of the queue and when one leaves they leave from the front of the queue.

Fun fact: the British refer to lines of people as a Queue

1 1 1 silver badge
answered Aug 16, 2017 at 15:48
32k 42 42 gold badges 183 183 silver badges 285 285 bronze badges

Haha well sure this is a perfect description of Queue and Stack, but just for arguments sake, what if I want the first pancake added to the plate? I know this can be completed with a stack.size() vs. if(!stack.isEmpty()), but still that first pancake might be the best one :). Either way, nice answer and I agree this is the clearest. seems interesting that the British refer to lines as Queues though (if that is accurate), in non-programming language I would still consider that a line where the first entry gets to leave first (after exiting the line/queue)

Apr 11, 2018 at 23:05
Wait, they’re not called queues elsewhere?
Dec 2, 2019 at 16:22

You can think of both as an ordered list of things (ordered by the time at which they were added to the list). The main difference between the two is how new elements enter the list and old elements leave the list.

For a stack, if I have a list a, b, c , and I add d , it gets tacked on the end, so I end up with a,b,c,d . If I want to pop an element of the list, I remove the last element I added, which is d . After a pop, my list is now a,b,c again

For a queue, I add new elements in the same way. a,b,c becomes a,b,c,d after adding d . But, now when I pop, I have to take an element from the front of the list, so it becomes b,c,d .

It’s very simple!

answered Jun 11, 2012 at 5:47
cdesrosiers cdesrosiers
8,882 2 2 gold badges 28 28 silver badges 33 33 bronze badges

Queue

Queue is a ordered collection of items.

Items are deleted at one end called ‘front’ end of the queue.

Items are inserted at other end called ‘rear’ of the queue.

The first item inserted is the first to be removed (FIFO).

Stack

Stack is a collection of items.

It allows access to only one data item: the last item inserted.

Items are inserted & deleted at one end called ‘Top of the stack’.

It is a dynamic & constantly changing object.

All the data items are put on top of the stack and taken off the top

This structure of accessing is known as Last in First out structure (LIFO)

8,853 15 15 gold badges 60 60 silver badges 103 103 bronze badges
answered Oct 8, 2013 at 7:43
593 1 1 gold badge 10 10 silver badges 21 21 bronze badges

So basically a ‘queue’ is a «FIFO» — first in first out queue. While a ‘stack’ is a «LIFO» — last in first out queue. Am I correct?

May 28, 2017 at 14:47
@SebastianNielsen Yes correct as mention in the answer.
May 30, 2017 at 5:37
But what is the difference then between a linked list and a stack? Isn’t it the same?
May 30, 2017 at 8:05

@SebastianNielsen The stack is an ADT, which means it exposes an interface, which is the push and pop operation, but the underlying mechanism (implementation) is hidden from the end user. A stack can be implemented with an array or with a linked list.

Aug 21, 2018 at 20:38

STACK:

1. Stack is defined as a list of element in which we can insert or delete elements only at the top of the stack.
2. The behaviour of a stack is like a Last-In First-Out(LIFO) system.
3. Stack is used to pass parameters between function. On a call to a function, the parameters and local variables are stored on a stack.
4. High-level programming languages such as Pascal, c, etc. that provide support for recursion use the stack for bookkeeping. Remember in each recursive call, there is a need to save the current value of parameters, local variables, and the return address (the address to which the control has to return after the call).

QUEUE:

1. Queue is a collection of the same type of element. It is a linear list in which insertions can take place at one end of the list,called rear of the list, and deletions can take place only at other end, called the front of the list
2. The behaviour of a queue is like a First-In-First-Out (FIFO) system.

8,560 13 13 gold badges 52 52 silver badges 79 79 bronze badges
answered Apr 9, 2013 at 4:22
ASHUTOSH KUMAR ASHUTOSH KUMAR
131 1 1 silver badge 2 2 bronze badges

I’m pretty sure you can insert at the end or start of a stack too, I think the important thing to note here is the FIFO vs. LIFO

Jul 15, 2015 at 19:39

A stack is a collection of elements, which can be stored and retrieved one at a time. Elements are retrieved in reverse order of their time of storage, i.e. the latest element stored is the next element to be retrieved. A stack is sometimes referred to as a Last-In-First-Out (LIFO) or First-In-Last-Out (FILO) structure. Elements previously stored cannot be retrieved until the latest element (usually referred to as the ‘top’ element) has been retrieved.

A queue is a collection of elements, which can be stored and retrieved one at a time. Elements are retrieved in order of their time of storage, i.e. the first element stored is the next element to be retrieved. A queue is sometimes referred to as a First-In-First-Out (FIFO) or Last-In-Last-Out (LILO) structure. Elements subsequently stored cannot be retrieved until the first element (usually referred to as the ‘front’ element) has been retrieved.

answered Jun 11, 2012 at 5:46
Saurabh R S Saurabh R S
3,117 1 1 gold badge 35 35 silver badges 46 46 bronze badges

STACK: Stack is defined as a list of element in which we can insert or delete elements only at the top of the stack

Stack is used to pass parameters between function. On a call to a function, the parameters and local variables are stored on a stack.

A stack is a collection of elements, which can be stored and retrieved one at a time. Elements are retrieved in reverse order of their time of storage, i.e. the latest element stored is the next element to be retrieved. A stack is sometimes referred to as a Last-In-First-Out (LIFO) or First-In-Last-Out (FILO) structure. Elements previously stored cannot be retrieved until the latest element (usually referred to as the ‘top’ element) has been retrieved.

Queue is a collection of the same type of element. It is a linear list in which insertions can take place at one end of the list,called rear of the list, and deletions can take place only at other end, called the front of the list

A queue is a collection of elements, which can be stored and retrieved one at a time. Elements are retrieved in order of their time of storage, i.e. the first element stored is the next element to be retrieved. A queue is sometimes referred to as a First-In-First-Out (FIFO) or Last-In-Last-Out (LILO) structure. Elements subsequently stored cannot be retrieved until the first element (usually referred to as the ‘front’ element) has been retrieved.

answered Apr 17, 2013 at 15:09
shashimani shashimani
21 1 1 bronze badge

To try and over-simplify the description of a stack and a queue, They are both dynamic chains of information elements that can be accessed from one end of the chain and the only real difference between them is the fact that:

when working with a stack

• you insert elements at one end of the chain and
• you retrieve and/or remove elements from the same end of the chain

while with a queue

• you insert elements at one end of the chain and
• you retrieve/remove them from the other end

NOTE: I am using the abstract wording of retrieve/remove in this context because there are instances when you just retrieve the element from the chain or in a sense just read it or access its value, but there also instances when you remove the element from the chain and finally there are instances when you do both actions with the same call.

Also the word element is purposely used in order to abstract the imaginary chain as much as possible and decouple it from specific programming language terms. This abstract information entity called element could be anything, from a pointer, a value, a string or characters, an object. depending on the language.

In most cases, though it is actually either a value or a memory location (i.e. a pointer). And the rest are just hiding this fact behind the language jargon

A queue can be helpful when the order of the elements is important and needs to be exactly the same as when the elements first came into your program. For instance when you process an audio stream or when you buffer network data. Or when you do any type of store and forward processing. In all of these cases you need the sequence of the elements to be output in the same order as they came into your program, otherwise the information may stop making sense. So, you could break your program in a part that reads data from some input, does some processing and writes them in a queue and a part that retrieves data from the queue processes them and stores them in another queue for further processing or transmitting the data.

A stack can be helpful when you need to temporarily store an element that is going to be used in the immediate step(s) of your program. For instance, programming languages usually use a stack structure to pass variables to functions. What they actually do is store (or push) the function arguments in the stack and then jump to the function where they remove and retrieve (or pop) the same number of elements from the stack. That way the size of the stack is dependent of the number of nested calls of functions. Additionally, after a function has been called and finished what it was doing, it leaves the stack in the exact same condition as before it has being called! That way any function can operate with the stack ignoring how other functions operate with it.

Lastly, you should know that there are other terms used out-there for the same of similar concepts. For instance a stack could be called a heap. There are also hybrid versions of these concepts, for instance a double-ended queue can behave at the same time as a stack and as a queue, because it can be accessed by both ends simultaneously. Additionally, the fact that a data structure is provided to you as a stack or as a queue it does not necessarily mean that it is implemented as such, there are instances in which a data structure can be implemented as anything and be provided as a specific data structure simply because it can be made to behave like such. In other words, if you provide a push and pop method to any data structure, they magically become stacks!

Разница между queue, deque и stack

Ключевым аспектом разработки эффективных алгоритмов и программ является выбор правильной структуры данных, которая наилучшим образом подходит для решаемой задачи. Одним из главных вопросов при выборе структуры данных является выбор между queue, deque и stack, которые являются основными структурами данных в программировании.

Queue (очередь), deque (двусторонняя очередь) и stack (стек) — это абстрактные типы данных, которые предоставляют различные способы организации и хранения данных. Они различаются по способу добавления и удаления элементов, а также по порядку доступа к элементам.

Queue — это структура данных, которая основывается на принципе «первым пришел, первым вышел» (FIFO, First In First Out). Это означает, что элементы добавляются в конец очереди и извлекаются из начала очереди. Deque — это двусторонняя очередь, которая поддерживает добавление и удаление элементов как в начало, так и в конец структуры данных. Stack — это структура данных, которая основывается на принципе «последним пришел, первым вышел» (LIFO, Last In First Out). Это означает, что элементы добавляются и извлекаются только из одного конца стека.

Выбор между queue, deque и stack зависит от конкретной задачи и требований к эффективности операций добавления, удаления и доступа к элементам. Если необходимо обрабатывать элементы в том же порядке, в котором они были добавлены, то queue или deque будут наиболее подходящими структурами данных. Если же порядок обработки элементов не принципиален и необходимо быстро добавлять и извлекать элементы, то stack может быть более эффективным выбором.

Важно помнить, что выбор структуры данных имеет большое значение для эффективности программы, поэтому перед выбором структуры данных необходимо проанализировать требования и ограничения задачи.

Определение и общие принципы

Queue, deque и stack — это требуемые структуры данных, которые часто применяются при разработке программ и алгоритмов. Все они относятся к классу линейных структур данных, что означает, что элементы в них хранятся в определенном порядке.

Queue (очередь) — это структура данных, в которой добавление новых элементов происходит в конец очереди, а удаление — в начало. Иными словами, элементы в очереди располагаются в порядке их поступления и обрабатываются в том же порядке. Примеры применения включают моделирование систем обслуживания, обработку запросов пользователей и управление задачами в операционных системах.

Deque (двусторонняя очередь) — это структура данных, в которой добавление и удаление элементов может происходить как с начала, так и с конца очереди. Это делает деку более гибкой, чем обычную очередь, и позволяет использовать ее в различных сценариях. Например, дек используется при реализации алгоритмов обхода графов и обработке данных в обратном порядке.

Stack (стек) — это структура данных, в которой добавление новых элементов и удаление происходит только с одной стороны стека, называемой «вершиной». Последний добавленный элемент всегда является первым элементом, который будет удален (принцип LIFO — «последним вошел, первым вышел»). Стек используется во многих алгоритмах и программных решениях, включая рекурсию, обратную польскую нотацию и проверку сбалансированности скобок.

При выборе подходящей структуры данных следует учитывать требования и особенности конкретной задачи. Если вам необходимо обрабатывать элементы по принципу «первым пришел — первым обслужен», то лучше всего использовать очередь. Если вам нужно добавлять и удалять элементы как с начала, так и с конца, то дека станет лучшим выбором. Если же важен порядок обработки элементов в соответствии с принципом LIFO, то стек будет наиболее удобной структурой данных.

Queue

Очередь (queue) – это линейная структура данных, основанный на принципе «первым пришел — первым вышел» (FIFO – first in, first out). Данные добавляются в конец очереди, а извлекаются из начала.

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

В языке программирования Python очередь можно реализовать с помощью модуля collections и класса deque. Для создания очереди нужно импортировать модуль collections с помощью команды:

from collections import deque

Затем можно создать пустую очередь:

queue = deque()

Основные операции с очередью – это добавление элемента в конец очереди (enqueue) и удаление элемента с начала очереди (dequeue). Для добавления элемента в конец очереди используется метод append(), а для удаления элемента с начала – метод popleft().

queue.append(element) # добавление элемента в очередь
 
element = queue.popleft() # удаление элемента из очереди

Также очередь поддерживает другие операции, такие как просмотр элемента с начала очереди (peek) с помощью метода queue[0] и проверка на пустоту (empty) с помощью конструкции not queue.

Если вам понадобится реализовать структуру данных, в которой необходимо обрабатывать элементы в порядке их поступления, то использование очереди будет наиболее подходящим выбором.

Deque

Deque (Double Ended Queue) — это структура данных с двумя концами, которая позволяет добавлять и удалять элементы как с начала, так и с конца очереди. В отличие от обычной очереди (queue), которая работает по принципу «первым пришёл — первым вышел» (FIFO — First In First Out), deque может работать и как очередь, и как стек.

Основные операции, которые предоставляет deque:

1. Добавление элемента в начало очереди (push_front).
2. Добавление элемента в конец очереди (push_back).
3. Удаление элемента с начала очереди (pop_front).
4. Удаление элемента с конца очереди (pop_back).
5. Получение элемента из начала очереди (front).
6. Получение элемента из конца очереди (back).
7. Проверка на пустоту (empty).

Пример использования deque: реализация алгоритма обхода графа в ширину (BFS). Для BFS необходимо последовательно обрабатывать все вершины в ширину, начиная с некоторой стартовой вершины. В этом случае deque может быть использована для хранения текущих вершин, которые необходимо обработать.

Выбор между deque, queue и stack зависит от конкретной задачи и требований к программе. Если необходимо работать только с одним концом очереди и поддерживать порядок добавления элементов, то можно использовать обычную очередь (queue). Если же нужно поддерживать порядок добавления элементов и обеспечить возможность быстрого доступа к началу и концу очереди, то следует использовать deque. Если же требуется доступ только к последнему добавленному элементу, то выбор следует остановить на стеке (stack).

Stack

Stack (стек) — это одна из основных структур данных, которая реализует принцип LIFO (Last In, First Out) — последний пришел, первый ушел. Это значит, что элементы добавляются и извлекаются из стека только с одного его конца — вершины.

Основные операции, реализуемые в стеке:

• Push — добавление элемента на вершину стека.
• Pop — извлечение элемента с вершины стека.
• Peek — просмотр элемента на вершине стека без его извлечения.
• IsEmpty — проверка, пуст ли стек.
• Size — получение количества элементов в стеке.

Stack может быть реализован как на базе массива, так и на базе связного списка. При использовании массива, стек имеет фиксированную максимальную емкость, а при добавлении элемента в полный стек возникает ошибка, называемая переполнением (overflow). При использовании связного списка, стек может динамически увеличиваться и уменьшаться в размере.

Пример использования стека:

1. Для реализации обратной польской записи при вычислении математических выражений.
2. Для хранения вызовов функций при работе с рекурсией.
3. Для отмены (undo) операций в текстовых редакторах.
4. Для реализации алгоритма обхода графа в глубину (Depth-First Search).

Выбор использования стека зависит от требований конкретной задачи. Если необходимо сохранить порядок элементов и работать с ними в обратном порядке, стек будет подходящей структурой данных. Для решения других задач, например, для поиска элементов по определенному приоритету или для быстрого доступа к заданному элементу, следует использовать другие структуры данных, такие как очередь (queue) или двусторонняя очередь (deque).

Различия между queue, deque и stack

Структуры данных queue, deque и stack являются одними из самых распространенных в программировании. Они используются для хранения и управления наборами элементов, но имеют некоторые отличия в своем поведении и особенностях использования.

Queue

Queue представляет собой структуру данных, в которой элементы добавляются в конец и удаляются из начала. Она соответствует принципу «первый вошел, первый вышел» (FIFO — First In, First Out). Это значит, что элементы в очереди обрабатываются в порядке их добавления, то есть сначала обрабатывается первый добавленный элемент, затем второй и так далее.

Deque

Deque (сокращение от «double-ended queue») является обобщением queue и представляет собой двустороннюю очередь. Он также позволяет добавлять и удалять элементы как с начала, так и с конца. За счет этого deque может быть использован для реализации не только FIFO, но и LIFO (Last In, First Out) обработки элементов.

Stack

Stack (стек) также представляет собой структуру данных, в которой элементы добавляются и удаляются только с одного конца. Однако в отличие от queue и deque, stack использует принцип LIFO, то есть последний добавленный элемент обрабатывается первым. Стек можно представить как стопку тарелок: последняя тарелка, которая была положена на стек, будет первой, которую можно взять с вершины.

Как выбрать подходящую структуру данных?

Выбор подходящей структуры данных зависит от требований и особенностей задачи, которую нужно решить. Если необходимо обрабатывать элементы в порядке их добавления, их удаление происходит в порядке, который соответствует их добавлению, тогда подойдет queue. Если же нужно иметь возможность добавлять и удалять элементы как с начала, так и с конца, то лучше использовать deque. А если требуется обрабатывать элементы в обратном порядке, то лучше использовать stack.

Как выбрать подходящую структуру данных?

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

Для выбора подходящей структуры данных следует учитывать следующие факторы:

1. Тип данных: В первую очередь необходимо определить тип данных, с которыми вы будете работать. Некоторые структуры данных оптимальны для хранения чисел, другие — для строк или объектов.
2. Операции над данными: Важно определить, какие операции вы будете выполнять над данными. Некоторые структуры данных лучше подходят для поиска и вставки элементов, другие — для удаления и обновления.
3. Время выполнения операций: Каждая структура данных имеет свою производительность, которую следует учитывать при выборе. Некоторые структуры данных обеспечивают более быстрые операции, но требуют больше памяти, в то время как другие могут быть менее эффективными, но более экономичными в использовании ресурсов.
4. Объем данных: Если вам требуется работать с большим количеством данных, необходимо выбрать структуру данных, которая эффективно обрабатывает большие объемы информации и не приводит к перегрузке памяти.
5. Взаимодействие со структурами данных: Иногда требуется использовать несколько структур данных вместе. В таких случаях необходимо выбрать структуры данных, которые легко сочетаются и позволяют эффективно обмениваться данными.

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

Также стоит помнить, что не существует универсальной структуры данных, которая подходит для всех случаев. Иногда придется проводить анализ нескольких структур данных и выбирать оптимальную исходя из конкретной задачи и требований к производительности.

Вопрос-ответ

Каковы основные отличия между queue, deque и stack?

Queue, deque и stack — это все структуры данных, но они отличаются своими особенностями и функционалом. Основное отличие между ними заключается в способе добавления и извлечения элементов. Queue (очередь) работает по принципу «First-In-First-Out» (FIFO) — первым в очередь попадает элемент, добавленный первым, и первым извлекается. Deque (двусторонняя очередь) позволяет добавлять и извлекать элементы с обоих концов очереди. Stack (стек) работает по принципу «Last-In-First-Out» (LIFO) — последним в стек попадает элемент, добавленный последним, и первым извлекается.

В каких случаях следует использовать queue?

Queue — это структура данных, которая наиболее подходит для решения задач, где необходимо обрабатывать элементы в порядке их добавления. Например, queue можно использовать для решения задач обработки запросов веб-сервера — запросы обрабатываются в том порядке, в котором они поступают. Также queue удобна для реализации алгоритмов BFS (обхода графа в ширину) и симуляции очереди.

Когда лучше использовать deque?

Deque, или двусторонняя очередь, подходит для решения задач, где необходимо добавлять и извлекать элементы как с начала, так и с конца очереди. Например, использование deque может быть удобным при реализации алгоритмов обхода графа в ширину, где одновременно могут производиться операции добавления и удаления элементов как в начало, так и в конец очереди. Deque также может быть полезной, когда требуется некоторая форма хранения данных, которая позволяет эффективно добавлять и извлекать элементы с обоих концов.