Help us understand the difference between queues and stacks
I don't understand the topic of stack queues and variants from implementations. The extract from what I managed to dig up in Google looks like something like this:
1.
Queue is a one-way queue - you can get the items in the same order as you added them.
Question:
It seems to be PriorityQueue and LinkedList its implementation in java collections. Are there any others? Or in another way:
Is it possible to say that any collection that makes it possible to get are the elements in the order they are added Queue, or just these two?
2.
Deque is a two-way queue-a queue that doesn't have an explicit expressed end and beginning. It can grow and shrink in both directions.
Question: Here it is not clear at all it is by type as a closed bidirectional linked list? What's it? I don't understand the idea and what problem it solves.
3.
And there is a stack - here you can get only the last item.
Question:
It seems that List has an implementation of Stack that kind of reflects this idea. Are there any other implementations? And what problem does this mechanism solve?
Here I got a little confused, help me figure out what is needed for what, and what implementations it has. Thanks.
3 answers
A queue is like a pipeline. You put it on one side and take it away on the other.
Stack-like the clip of a gun, what you put last, you take first.
Bidirectional queue-combines a queue and a stack. You can add values both to the beginning and to the end, as well as take them either on the principle of the stack, or on the principle of the queue, it is difficult to come up with a "live" example, but you can understand the idea by studying the methods of this tool. This is such a box with two holes, in which you can put something on one side and on the other side, as well as take it away. For example, we put it on the left and pick it up on the left (as a stack), or we put it on the left and pick it up on the right (as a queue), or we approach it from the other side and do the same.
Clearly, the live queue is somewhere in the checkout window and another window opens, the part from the end goes to this window, and the last one in the first queue is the most cunning and got first in the new queue. Options when interacting with a bidirectional network there are a lot of queues, and this is one example. In programming practice, it is used in asynchronous processing, as an option. In general, it can be used both as a stack and as a queue, as well as combine both approaches.
It has nothing to do with lists (you can get any element in them), in queues and stacks you can only get either the first one or the last one. Also, you can only enter either at the beginning or at the end. Items inside the stack / queue are not available until they will be at the top (the elements that got there before them will not be extracted). It also differs from lists in that if you put the first element in the list, then how much you do not get it later, it will be the first. In the queue / stack, when extracting, we move through the previously received ones and extracting the first one, we get everything (in the order of receipt)
We need these tools as a kind of buffer for temporary storage, basically. That is, you receive some information, you put it in this stack / queue, and then process, either in the order of arrival, the first first - the queue, or the last first-the stack.
You can read articles with pictures, like this, here about self-implementation, but the principle is well described "from the inside".
1) There are other
All Known Implementing Classes: AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue
Javadoc usually mentions all known implementations of the interface.
And as in the saying about the duck, which behaves like a queue in a queue and is.
2) No, this is not a closed bidirectional linked list. There are two ends, one is conventionally called the beginning, the other the end. Such a queue can be filled and emptied at both ends.
Fuck knows what it's for. But once they came up with it, it means that it is necessary for a fairly wide range of tasks.
For example, it is strongly recommended to use deque instead of stack (which is considered deprecated). From javadoc
Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class.
3) Well, actually, as already written in paragraph 2, not that there are alternative implementations of the stack, but even recommend using them instead of the original one.
Fist In - First Out (FIFO) Queue)
поставить в очередь -> ||||||||||||| -> извлечь из очереди
| |
| `первым пришёл, первым и выходит FIFO
`последний в очереди последним и выйдет
Last In - First Out (LIFO) Stack)
поместить в стек -> ||||||||||||
извлечь из стека <- ||||||||||||
| |
| ` помещён первым, но выйдет последним
` помещён в стек последним, но извлекается первым LIFO
Hereafter, the element occupies two rows in height. (So that someone would not think that these are some kind of "parallel threads". You just need to place the labels to the element in two lines)
Deque combines the advantages of a queue and a stack, and even on both sides
поставить в начало очереди -> ||||||||||| -> извлечь с конца очереди
извлечь с начала очереди <- ||||||||||| <- поместить в конец очереди
If we ignore one of the lines, we get the queue
If we ignore the right or left part, we get the stack