What is the order of items being popped and pushed from a stack?

Question

    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]

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

stack = [10, 20]

3. 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.

Answer 1

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.

Answer 2

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.