Is it possible for a sequence of linked-sequence actions (not linked-sequence operations) to specify the behavior of a stack or a linked list but not a queue? If so, give an example of a short sequence; if not, explain why.
It is, as described by the linked-sequence actions
(put, 0, 0, true, undefined) // stack, queue, or linked list behavior. (put, 0, 1, true, undefined // stack or linked list, but not a queue behavior.
The answers, in no particular order and approximately verbatim:
1: How?
stack queue s.push(1) s.push(1)3 s.push(2) s.push(2)
2: Linked lists can show LIFO behavior, but they can also show lots of other behavior too.
3: These aren’t linked sequence actions.
4: How?
5: Which it? The action sequence?
6: Is this the same it as the previous one
7: Which properties?
8: Which it is this?
9: What about stacks and queues, which are linked sequences?
10: Yes? How does that prevent an action sequence from behaving like a stack or a linked list but not a queue?
11: Which actions?
12: Or a linked list perhaps?
13: Pop isn’t a linked-sequence action
14: What’s not possible
15: Last one what?
16: What about linked lists?
17: Different how? And can an action sequence demonstrate that difference?
18: Pop isn’t an action.
19: Presumably the action sequence would exploit these properties somehow.
Yes. There is a linked-sequence actions when performed gives the behavior of linked list and stack but not queue.
Example of actions add and remove. We add elements in ADT at index values keeping the ADT constraints in mind.
Test case if we add 3 elements and remove them all the three ADT works.20 But if want to delete element from index reference Queue doesn’t satisfy i = 0 case, which the other two satisfy.
Sequence actionadd (index 0, val 4)21 remove (index 0)
These actions work for stack and linked list but not for queue.
20: Using the same action sequence?
21: Are these linked sequence actions?
put(0, T) success23 put(0, T) success24 get(0, T) success get(0, T) success see(0, T) fail
22: But the question wants to distinguish between stacks and queues.
23: Is this a linked-sequence action?
24: Why do you need any more than this?
Regarding a stack and a queue, a sequence of actions could very well determine which data type is being used.25 For example, if the values 1, 2, 3 are added in that order, and then removed, their order in the output would differentiate between the two.
This is because a stack operates on LIFO (last in first out) and a queue operates on FIFO (first in first out). So basically if a sequence comes out the same as it was entered, you’re dealing with a queue, but if it’s backwards it’s a stack.26
25: That may be, but that’s not what the question is about.
26: Right, but where’s the linked list part?
27: Is that relevant?
1) put(0, 1) 2) put(0, 2) 3) get(0) // 2 4) get(0) // 1
This can be linked list as that can insert or remove from index 0.
A stack can only put or get at index 0. Which is fine in this example.
However a queue can only get from index 0 when it is the index of the only value in the queue. In the case of action 3, get(0), this is not true.
(put, 0, 10, true, undefined) (put, 0, 10, true, undefined)
These operations can only be preformed on stack or linked list, but not on a queue.
28: That’s backward; because stacks are more restrictive than queues, they can’t do things that queues can.
It has to be a doubly-linked list. Inserting a value just before the tail in a singly-linked list requires traversing from the head to the tail, taking time proportional to the number of elements in the list, while a doubly-linked list can insert the value just before the tail in time independent of the number of values in the list, assuming there’s a pointer to the tail.
The answers, in no particular order and approximately verbatim:
1: Not the question asked.
Free links reference stored in array2 are used to insert element at constant time in a linked list.3
The freeLink array stores the reference for the next-available free link.
If we are at index 0 and want to insert we look-up to find out next empty link so we get 1 and add element there. Later we know at index 3 there is empty node and so on.
2: Array? Where?
3: A free list is used to find a free node in constant time, but that doesn’t apply here.
4: But the question states the linked list is implemented with dynamic storage.
5: The head and the tail are adjacent.
6: True, but the question isn’t about arbitrary traversals.
7: What does this have to do with anything?
8: Yes, but that’s more than the question requires.
9: A constant amount of time.
10: Why?
If values are off limits, the only part of the circular buffer available are the head and tail pointers. Assume that the head points to the next value, if any, to be removed and the tail points the location at which the next value added will be stored; then the buffer is not full when the head and tail pointers are different. However, when the head and tail are equal, it’s not clear if the buffer’s full or empty. The way to distinguish between empty and full is to remember which pointer was changed to make them equal. If the head pointer was moved (that is, a value was removed), the buffer’s empty. If the tail was moved (that is, a value was added), the buffer’s full.
The need to remember the last pointer moved can be avoided by further assuming that an n-element buffer can only hold at most n - 1 elements. Now the buffer is unambiguously empty when the head and tail are equal, and full when (head + 1) mod n == tail.
There are other techniques using different assumptions, but they become increasingly more obscure.The answers, in no particular order and approximately verbatim:
The circular buffer is empty when the head is empty/null and the tail is null.1
The circular buffer is full when the head is empty/null and the tail is equal to (n - 1), n number of values in the circular buffer.2
1: What does it mean for the head or tail to be null? Are they null themselves, or pointing to nulls?
2: How do you know that arrangement will always be present when the buffer is full?
3: Ok, but how does isEmpty() work?
4: What happens if no exception is thrown?
5: The question disallows counting elements.
6: Is the head always connected to the tail in a circular buffer?
7: The user of the circular buffer?
8: Why would moving a value from one place to another in a circular buffer be helpful?
9: But the question disallows counting.
I’m assuming ‘head’ is the index of the first value in the buffer and ‘tail’ is the index of the first empty spot. In other words, tail is the index of the element after the last value. Also ‘size’ is the size of the allocated buffer, i.e. NOT the count.
If head is equal to tail then the list is empty, i.e., count = 0. If ((tail + 1) % size) == head, then the buffer is full, i.e., count = size + 1.
In this implementation there is a phantom tail, if you were to completely fill the buffer then head would equal tail and would make it ambiguous as to whether the buffer is empty or full. This requires a buffer of at least two elements allocated.10
10: Does this fix the ambiguity?
11: What happens if the queue can hold nulls as values?
12: Possibly, but the question disallows value counting.
13: Which point?
14: And then what?
15: What if the buffer can store nulls as values?
16: Isn’t that counting?
Class CQueue {
Node head
T data
}
temp = head;
if (temp.next == temp) // circular queue is empty
else // circular queue is full.17
17: How is a queue implemented using dynamic storage ever full?
18: Or if the value removed was the last value.
19: Or if there was only one open slot left.
20: What if the value you add makes the buffer full?
21: Isn’t that an expensive way to determine if any values are in the buffer? And what do you do with the returned values?
22: ? The word looked like “syntax” anyway.
23: And what of the removed value?
24: And what of the added value?
25: Do you mean the head or tail is referring to null, or are themselves null?
26: What happens if the head isn’t 0 or the tail isn’t n - 1.
Assumption: We implement two stacks in a circular buffer.27
Solution: The two stacks' top-of-stack s1 and s2 respectively placed at i = 0 and i = size (say n). Whenever the push operation takes place, the s1, s2 increments in opposite directions.28
push(s1, x) s1[TOS1] ← x TOS1 ← TOS1 + 1
|
push(s2, x) s2[TOS2] ← x TOS2 ← TOS2 - 1
|
pop(s1) if s1[TOS1] == null then buffer is empty29
|
pop(s2) if s2[TOS2] == null then buffer is empty
|
27: You mean implement two stacks in the circular buffer, or implement the circular buffer using two stacks?
28: Why would you push on both ends of the queue?
29: Is s2 empty too? Why?
if (head == tail) then array is empty.
After a few enqueue.30
if (((tail + 1) % array.length) ==) then array is full.31
30: What about dequeues?
31: But what happens when the head is a few values behind the tail?
32: You mean the buffer wasn’t empty; it may be empty after you’ve removed a value.
33: Correct; the queue wasn’t full, but it may be after you add a value.
34: What about the changes made to the queue? What happens to those?
35: Do you mean the buffer has capacity n and current size 0?
36: What about the tail?
37: Isn’t that expensive in time and space?
38: Determined how?
39: The original what?
40: But what of the other queue positions?
Yes. Values placed in the array don’t move once placed. A reference to a value (that is, the value’s index) in the array remains valid until the value is removed from the array.
The answers, in no particular order and approximately verbatim:
1: How?
2: How does this solve the phantom-reference problem? And how do values move from the enqueue array to the dequeue array?
3: Why not use the reference to locate the value directly?
4: What consequences does this have for the phantom-reference problem?
5: True, but that doesn’t have much to do with the phantom reference problem that I can see.
6: Which it?
7: What does this mean? How does time enter into it?
8: How is this relevant?
9: Why not?
10: What about the nodes with values?
11: Perhaps, but what effect does that have on the phantom-reference problem?
12: That’s one part of the phantom-reference problem, but there are others.
13: Why would the values have to be moved around when in the array?
14: True, but more important for the phantom reference problem is that adding and removing values don’t change the positions of other values in the linked list.
15: Is that the phantom-reference problem?
16: The phantom-reference problem is related to, but independent of, the modifying-while-traversing problem.
17: Refactoring what how?
18: Why exactly? What good does keeping track to?
Use a circular buffer. Deques provide access at both ends, same as queues, except both adding and removing at each end. A circular buffer provides unrestricted movement at both ends, at least until the buffer’s full or empty.
The answers, in no particular order and approximately verbatim:
The simplest way would be to implement another set of arrays1 where we can add the values to the empty spaces, so we don’t have to worry about moving all the values.2
If it was a case of [???] we could have made the node point towards the result nodes, so the empty nodes goes to the free list and we are not moving any values.
1: That’s a lot of extra space.
2: What purpose do the multiple arrays serve?
3: Pop what out of the sequence?
4: When is popping done?
5: Do you mean the deque here?
6: What kind of errors?
7: Why would there be extra value shifting without a free list?
8: Wouldn’t that be at the ends of the deque?
9: Right, but how do you do that? That’s what the question’s asking.
a[i] = a[i + 1] until i < size -
1 where size is length of the queue.10
10: Does this minimize value movement?
The simplest, most space efficient way to implement a deque using an array would be to use a circular buffer.
At this point you can queue values on either end without having to move elements.
Value movement may otherwise occur if values are queued to one end more than the other, and dequeued more from the opposite end in a non-circular buffer.
To address this problem you can make the array circular. This way the values may still logically “move” depending on the access, but you would never have to explicitly move each element to make room. This assumes the array is large enough and doesn’t get filled.
A simple fix for that problem would be to allow the deque to eat the tails on a queue, thus the array would never fill.11: How is data’s importance determined?
12: Is that a deque?
13: Copy old values from where?
14: Passing the value index where?
15: What happens when the values reach the end of an array?
head = (head + 1) % array.length.
16: What is resetting? What does it do?
Deque is a kind of queue, where you can add/remove element from both ends. Objective is to minimize value movement within array. Therefore the simplest and most space efficient way to implement deque is using array as stack.17
Stack stores and removes element as when they are being called by subroutines. They grow and shrink in size efficiently solves space efficient problem.18
RemLast(s) x ← s[tos] tos = tos - 1 return x |
RemLast(s) x ← s[tos] tos = tos - 1 return x |
17: Just one stack, or two?
18: True, but deques grow and shrink at both ends. How does a stack handle that?
19: Which is what part of the array? The low indices?
20: Do you mean value movement in and out of the array, or within the array?
21: Which doubles the space used with no increase in values stored.
22: But the array’s implementing a deque. What values move in a deque?
23: What’s a stack array?
24: Does this provide minimal data movement with efficient space use?
25: Wouldn’t that have to be done even if value movement wasn’t being minimized?
26: That’s moving values.
27: Why is this an advantage, given deque access.
28: Aren’t all the values linked in the array?
29: How is that done?