0
$\begingroup$
    public static void reverseFirstK(Queue<Integer> q, int k) {
       LinkedList<Integer> stack = new LinkedList<>();
       for (int i = 0; i < k; i++) {
            stack.push(q.remove());
        }
        System.out.println(q);
        System.out.println(stack);
        while (!stack.isEmpty()) {
            q.add(stack.pop());
        }
        System.out.println(q);
        for (int i = 0; i < q.size() - k; i++) {
            q.add(q.remove());
        }
        System.out.println(q);
    }
}

I was asked to write a program that given a value k and a queue of elements reverses the order of the first k elements of the queue, leaving the other elements in the same relative order. Through trial and error I arrived at the right code, although I don't get why it works.

For the sake of lucidity let the original queue be [10, 20, 30, 40, 50, 60, 70, 80, 90]. After the first for loop queue = [50, 60, 70, 80, 90] and stack = [40, 30, 20, 10]. Why is stack =/= [10,20,30,40]? My thought process was remove() removes the first element of the queue, and that push added elements to the end of a stack. So the steps would look something like

  1. queue = [20, 30, 40, 50, 60, 70, 80, 90],

stack = [10]

  1. queue = [30, 40, 50, 60, 70, 80, 90]

stack = [10, 20]

  1. queue = [40, 50, 60, 70, 80, 90] stack = [10, 20, 30]

etc.

Then after the while loop, the queue is [50, 60, 70, 80, 90, 40, 30, 20, 10]. What I don't understand here is why is the queue not [50, 60, 70, 80, 90, 10, 20, 30, 40] here? My thought process was that pop() removes elements from the end of the stack, and add adds elements to the end of a queue. So the steps would look something like

  1. Stack: [50, 60, 70, 80, 90] Queue: [40, 30, 20, 10]

  2. Stack: [50, 60, 70, 80, 90, 10] Queue: [40, 30, 20]

  3. Stack: [50, 60, 70, 80, 90, 10, 20] Queue: [40, 30] etc.

I would really appreciate some clarification on this.

$\endgroup$
2
  • $\begingroup$ As a stack and a queue are different data structures, they perforce have different behaviors. One is LIFO and the other FIFO. $\endgroup$ May 1 at 19:24
  • $\begingroup$ I read this everywhere but I don't get how to correctly apply this to the above statements. Using the above example, if a stack is first in first out and a queue is last in first out, if you run stack.push(q.remove()), the item being removed from the queue is 10, then 20, then 30, then 40, but shouldn't they be added to the stack as [10,20,30,40] (Since the top of the stack is the position where the most recent element was added) instead of as [40,30,20,10]? $\endgroup$
    – BeanieBaby
    May 1 at 19:47

2 Answers 2

0
$\begingroup$

If you put {int i = 1; i < 4; i++} into this linked list, you should have:

head->1<->2<->3<->4<-tail

Now we can dequeue each element, in the case we use java and we use the .remove() function from the Linked List class, we'll take the head element every time - this essentially acts as a queue. The queue will not act to rearrange any of the integers that we put in. We can look at the following to see what putting a queue into a stack would look like. For our purposes, we'll use the same linked list I created:

Linked List: head->1<->2<->3<->4<-tail
Stack: head->null

Linked List: head->2<->3<->4<-tail
Stack.push(LinkedList.remove())
Stack: head->1

Linked List: head->3<->4<-tail
Stack.push(LinkedList.remove())
Stack: head->2->1

Linked List: head->4<-tail
Stack.push(LinkedList.remove())
Stack: head->3->2->1

Linked List: head->dummy node<-tail
Stack.push(LinkedList.remove())
Stack: head->4->3->2->1

Now let's pop this stack we have: head->4->3->2->1. stack.pop() = 4 -> stack.pop() = 3 -> stack.pop() = 2 -> stack.pop() = 1. 4,3,2,1 is the order. Putting a for loop in a queue doesn't do anything if you're just going to dump the queue into the stack.

It's important to note that queues do not rearrange data. If you wanted your data to be in original order using a stack, you can use two stacks - put whatever data into one stack and pop it to another stack.

data -> push to stack1 -> pop this data and it will be reversed compared to the original; push the data to stack2 -> pop this data and it will be in its original order.

[edit] Just read your comment about how you're confused on what LIFO and FIFO mean:

For first in first out [FIFO], we use the queue data structure. We can think of restaurants, the first person to order - unless they order something extravagant - will generally be the first person to get their food and the last person to order food will be the last person to get their food; however, that person will eventually be the first person to order relatively to all orders in the queue.

For last in first out [LIFO], the stack data structure, think of a pile of plates at the buffet. The plate on top is always the last plate that was put on. Although it is the last plate, it is the first out.

$\endgroup$
0
$\begingroup$

The result of the stack you observed is based on how the push()operation of the LinkedList is implemented in Java, which appears to be the language of your code. If you follow the link, you will see that the top is the front/head of the LinkedList, hence you get as result [40, 30, 20, 10] and not [10, 20, 30, 40].

Of course, you can have your own implementation to enforce that the back/tail of the LinkedList to be the top and you will obtain [10, 20, 30, 40]. However, this should not change how elements are popped because like insert (push), removal (pop) should also be done at the top. So in your implementation where the tail is the top, elements will be removed from the tail, i.e. 40 will be removed first, then 30, and so on.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.