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

    public static void reverseFirstK(Queue<Integer> q, int k) {
for (int i = 0; i < k; i++) {
stack.push(q.remove());
}
System.out.println(q);
System.out.println(stack);
while (!stack.isEmpty()) {
}
System.out.println(q);
for (int i = 0; i < q.size() - k; i++) {
}
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.

• As a stack and a queue are different data structures, they perforce have different behaviors. One is LIFO and the other FIFO.
– user16034
May 1 at 19:24
• 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]? May 1 at 19:47

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



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.

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.