-
A priority queue arranges queued elements in ascending order based on
an integer priority assigned to each element as it’s enqueued. Explain
how to assign priorities to enqueued elements so that the priority queue acts
like a stack.
If the priority queue removes the enqueued element with the largest
priority, then assigning each element a priority larger than that of any
elements already enqueued would provide first-in, first-out behavior. The
easiest priority to assign is the queue size. If the priority queue dequeues
the element with the smallest priority, then assign negative of the queue size
as the new element’s priority.
The answers, approximately verbatim and in no particular order:
- A queue is a fifo based data structure, meaning the first element in is
the first element out. Priority queue would assign the nth element in with the
nth integer priority as it is enqueued, and the arrange then as stated above.
To make a priority queue act like a stack, the priority would have to be set to
lifo, which is last in first out. So the integer priority would have to be in
descending order, meaning before enqueueing, one should know how many elements
the will be and set one of the elements to that priority value all the way
down to priority 1, then arrange them in descending order from the top so they
would dequeue as last in first out.
- If you always assign the item going into the queue with the lowest priority
it will be enqueued if first in last out order. This will give us the first in
last out behavior of the stack.
- Well, a stack can only have the top taken off, so automatically assign
the last item entered highest priority, and then make it so that once that’s
removed, the one under it is immediately #1.
- If the integer priority assigned to each element causes the queue to
arranged in ascending order according to the # of elements in the queue, then
it can assign the integer priority (the integer starting at n = # of elements
and going to 0) backwards in order to make the priority queue act like a stack.
- Since a stack has the last in first out behavior the assignment of the
priority queue needs to be arranged in descending order so the last element in
the queue is the 1st one to come out. Just in the same manner as a stack
removes the last element of the stack first. So in a manner of speaking the
last element of a priority queue is the 1st element in an stack.
- Queues and stacks differ in the way they behave. A queue uses first in
first out behavior allowing the elements to be dequeued or displayed in the
same order there were enqueued. A stack uses last in first out behavior so the
elements are simply reversed. For a priority queue to act as a stack, the
elements enqueued in the queue will need to be reversed.
-
Assign the priorities from least significant to most significant. The
most important element priority-wise would then be on the top.
Put the
elements on a stack in descending order such as 321 priority and they will be
removed in a 123 order. This is known as LIFO.
- Stacks have the ‘lifo’ property. Enqueuing is done at the tail of
the queue. And dequeing is done at the head of the queue. Therefore the last
element in the ascending order should be enqueued into the priority queue so
that when we dequeue the priority queue, from the head, we will get the list in
the ascending order.
-
Using a circular buffer in an array-based implementation of a queue avoids the
need to shift elements within the array. Why doesn’t a stack use the
same technique?
A stack implemented as an array only varies at one end of the data block;
the other end remains stationary. Because the data block doesn’t move
through the array, there’s no need to shift data and no advantage to
using a circular buffer.
- Because with stacks, you can only remove the top data piece of said
stack. You can’t shift elements in a stack anyway.
- The elements are not supposed to be shifted in a stack. The bottom
element (the first element pushed in the stack) remains stationary while the
other elements being pushed into the stack are added.
- Queues use the first in first out method and by using the circular buffer
implementation when a element is removed from the array the item that was
removed loops around like a circle and becomes the empty spot at the beginning
of the array for the next element to be added without having to shift any
elements. But a stack uses the last in first out implementation which
basically allows us to “stack” elements on top of each other like a stack
of books, and by removing an element we remove from the top and not from the
bottom as in the queue. So the circular buffer is not needed.
- A stack does not use the same technique as a queue because it’s
behavior is LIFO as opposed to FIFO, which reverses the elements of a stack.
As a queue’s enqueue function is utilized at the tail of the array and
it’s dequeue function is used at the head, the circular buffer is
possible with a stack, elements are pushed at the head of the array and popped
at the head of the array.
- A queue has a tail that data gets inserted into and a head where data is
extracted. A stack only has top where you put elements and remove them. A
circular buffer would not work and would not provide any benefit. Also it
would be impossible to tell if it was full or not as top would be the same
element, as opposed to having a head and a tail.
-
A stack always gives the last element that went in to stack; in other
words, we can only access a stack from only one side (head side).
Whereas
queue can be accessed from either top or the bottom, which enables the circular
arrangement.
Since stacks does not allow access from either sides, ie top
and bottom, similar circular technique cannot be applied for stacks.
- A stack doesn’t use the same techniques because in a stack, the
elements are last in first out meaning elements will be being pushed onto the
stack, which will cause the elements already in the stack to be pushed down on
more in the array.
- Because a stack only has access to the first element. A queue can only
have the circular property because it has access to both the head and tail
elements.
-
What role does operator precedence play when using a stack to convert an infix
expression to post-fix?
See pages 374 to 379 in Nyhoff.
The answers, approximately verbatim and in no particular order:
- The operator precedence changes the stack from infix to post-fix by
having the operator that has more precedence change the behavior of the stack.
- Stacks use the property of last in first out. In converting an infix
expression to post fix, operator precedence can be used to set priorities by
which how one wants to arrange the post fix expression.
- Operator precedence is what decides how to convert from infix to
post-fix, so the role of operator precedence is extremely important. A
possible approach to ensuring the order will be correct is to use parenthesis
first. Operator precedence ensures you arrive at the correct answer
mathematically.
- As stacks are sequential, they follow the before and after relationship.
- With post-fix notation we want to move the operators to the right-most
part of the string. When we reach an operator we push it onto the operator
stack, when we reach a number we push it onto the number stack. When we reach
the end of the input, we pop off 2 numbers and an operator. This will reverse
the input and turn 2*2 into 22*.
- Operator precedence would play a major role when converting from infix to
post-fix using a stack because of the way that it is implemented. Considering
stacks are lifo, the operator precedence would have to be inverted to
accommodate the stack’s behavior. If not, the infix expression that is
pushed will not come out post-fix if the precedence order is not accounted for.
Although () would done first still, addition might come before multiplication
after being popped off the stack, throwing off operator precedence.
- Primarily it has to do with what expressions are first converted to
post-fix expressions.
- The operator precedence plays the role of comparing the infix expression
to the post-fix expression.
-
A colleague of yours has to implement a linked-list data structure for which it
is important to be able to reverse the order of the elements in the list
quickly. Your colleague thinks that by using a doubly-linked list the reverse
operation can take constant time by just swapping the head and tail pointers.
What do you think of your colleague’s scheme? Explain.
It won’t work, because the next and previous pointers on each
element link are backwards. When a linked list is first reversed, for example,
the next pointer for the new queue head (formally the queue tail) points to
nil.
Your colleague can flip the pointers with O(n) work, but
there’s another way that preserves constant time behavior: store the
pointers in a two-element array neighbors indexed by the variables
next = 0 and last = 1. When it comes time to reverse the queue, the
pointers can be flipped in constant time by doing next = (next + 1) % 2
and last = (last + 1) % 2.
The answers, approximately verbatim and in no particular order:
- My colleague would be correct, but using a stack would be more beneficial
in his situation. Since stacks work in last in and first out, that means the
last element in would be the first one printed out when prompted to. Example:
“Hello world” when pushed into a stack would pop out like “dlrow
olleh” when popped.
- It would take constant time (just the swap of two pointers) however it
would only work to reverse the elements one time. If you want to insert to a
list that has been reversed using this technique it will not work the way you
want it to. Essentially after the swap you will have two separate fifo lists,
where the second list starts at the tail of the first list.
- As linked-lists do not have access to the head or tail, this procedure
will not work. If the colleague used a stack implemented with a doubly linked
list, constant time may be achieved.
-
A doubly linked list is twice the overhead of a singly-linked list.
It would be quicker to sort the linked list or to insert them in
order.
There is also overhead with creating new nodes for the linked list
in order to perform the swap.
Putting the linked list into a stack would
be another option, for reverse order, that is.
- Surely the reversing can be done I guess. But again it still takes O(n)
amount of work to get this done. Not only that, by having the double-linked
list, the overhead is now twice than a singly-linked list. A stack using list
would be my suggestion.
- I think that the method that he is proposing will not work because, every
element has a node that points to another node and at the end of the linked
list the tail is always a null. If he switches the head and tail pointers (the
pointer point to those pointers will also be switched) the beginning of the list
will be the node with the null in it. So it will not reverse the order of the
linked list.
- If you swap head and tail pointers, only the head and tail pointer
references would be changed. The pointers between the head and tail would
remain the same and the linked-list would not be reversed. If the colleague
wants to reverse the order of the elements, I think he/she should create a stack
using linked list implementation, which already stores the elements in reverse
order. This will also be constant time since there is only access at one end.
-
I think it’s a good idea. The problem is that linked lists
are really dependent on all it’s data pieces and how they are connected
by pointers. If it is so necessary, use a sort, done in descending/ascending
order, y’know?
I feel iffy about messing with pointer, but it
seems like it’d work.