It's helpful to review these data structures that we use while solving algorithm problems. So, I have implemented these 3 structures in Java.
Stack
The stack is pretty straightforward. We use an underlying array to store data and a number to keep the index we are at. When we are pushing an element, we increment the index and put the given value to the data array at that index. When we are popping, we get the element at the index and decrement the index to the previous element. It is also helpful the set the element at the index to null before decrementing. peek() method gets the element at the index without decrementing it.
Double-ended Queue with Array (Dequeue, Deque)
This data structure is more elaborate than the usual stack. It's helpful the think how a queue can be implemented using an array. As we are pushing to the beginning of the array in the stack, we would be enqueueing to the end of the array for a queue:
enqueue(9)
enqueue(18)
enqueue(27)
data is [0, 0, 0, 0, 0, 27, 18, 9] // 0's stand for unassigned values
Combining this with array-stack would yield as a double-ended queue:
push(36)
push(45)
push(54)
data is [36, 45, 54, 0, 0, 27, 18, 9]
If we start popping out elements, we would trivially pop out the first 3 elements. After that, the stack index would have to shift to the end of the array if the queue part is not empty.
pop_n_elements(3)
data is [0, 0, 0, 0, 0, 27, 18, 9]
pop()
data is [0, 0, 0, 0, 0, 27, 18, 0]
Same would happen with polling:
poll_n_elements(3)
data is [36, 45, 54, 0, 0, 0, 0, 0]
poll()
data is [0, 45, 54, 0, 0, 0, 0, 0]
Unlike the directly linear structure of the stack, we won't expand the array when the stack index reaches the end or the queue index reaches the beginning, unless the queue part or the stack part is respectively empty. The emptiness of the stack or the queue parts can be checked by the stack index being at -1 or the queue index being at data length.
Here is how actual expansion happens:
data is [18, 27, 0, 36, 108, 144, 180, 72]
queue_index is 3
stack_index is 1
enqueue(45)
data is [18, 27, 45, 36, 108, 144, 180, 72] (queue_index is 2)
push(99) -> stack_index is 1 smaller than queue_index, which means that pushing would override the beginning element
-> expand:
data is [18, 27, 99, 0, 0, 0, 0, 0, 0, 0, 45, 36, 108, 144, 180, 72]
queue_index is 11
stack_index is 2
We should also be able to poll elements that we push, and fill the empty indices at the beginning too:
data is [36, 45, 54, 0, 0, 0, 0, 0]
poll() // polls 36
data is [0, 45, 54, 0, 0, 0, 0, 0]
enqueue(18)
enqueue(27)
data is [18, 45, 54, 0, 0, 0, 0, 27]
Same happens with pushing:
data is [0, 0, 0, 0, 0, 27, 18, 0]
push(99)
enqueue(216)
data is [216, 0, 0, 0, 0, 27, 18, 99]
For this cyclical structure, we can take the modulo of the queue or stack index after incrementing or decrementing them.
Array List
I've added this as it was really easy to add as the subclass of the deque. We only need to calculate the index corresponding to the list elements. Which is either some indices after the queue index or some indices (given index - queue elements at the end) before the stack index
I haven't added Iterator and equals() properties, because I think that the logic of these structures are enough for now.
It's helpful to review these data structures that we use while solving algorithm problems. So, I have implemented these 3 structures in Java.
Stack
The stack is pretty straightforward. We use an underlying array to store data and a number to keep the index we are at. When we are pushing an element, we increment the index and put the given value to the data array at that index. When we are popping, we get the element at the index and decrement the index to the previous element. It is also helpful the set the element at the index to
nullbefore decrementing.peek()method gets the element at the index without decrementing it.Double-ended Queue with Array (Dequeue, Deque)
This data structure is more elaborate than the usual stack. It's helpful the think how a queue can be implemented using an array. As we are pushing to the beginning of the array in the stack, we would be enqueueing to the end of the array for a queue:
Combining this with array-stack would yield as a double-ended queue:
If we start popping out elements, we would trivially pop out the first 3 elements. After that, the stack index would have to shift to the end of the array if the queue part is not empty.
Same would happen with polling:
Unlike the directly linear structure of the stack, we won't expand the array when the stack index reaches the end or the queue index reaches the beginning, unless the queue part or the stack part is respectively empty. The emptiness of the stack or the queue parts can be checked by the stack index being at -1 or the queue index being at data length. Here is how actual expansion happens:
We should also be able to poll elements that we push, and fill the empty indices at the beginning too:
Same happens with pushing:
For this cyclical structure, we can take the modulo of the queue or stack index after incrementing or decrementing them.
Array List
I've added this as it was really easy to add as the subclass of the deque. We only need to calculate the index corresponding to the list elements. Which is either some indices after the queue index or some indices (given index - queue elements at the end) before the stack index
I haven't added Iterator and equals() properties, because I think that the logic of these structures are enough for now.