How do queues work

Interview Preparation. Practice Geeksforgeeks. Data Structures. Programming Languages. Web Technologies. But backtrack to where? Therefore, at each choice point you store on a stack all possible choices. Then backtracking simply means popping a next choice from the stack. The variable top changes from -1 to capacity - 1.

In a fixed-size stack abstraction, the capacity stays unchanged, therefore when top reaches capacity , the stack object throws an exception. See ArrayStack. Stack is a container of objects that are inserted and removed according to the last-in first-out LIFO principle. Queue is a container of objects a linear collection that are inserted and removed according to the first-in first-out FIFO principle.

Stack: In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. A stack is a limited access data structure - elements can be added and removed from the stack only at the top.

Take the example of a printer. Suppose we have a shared printer, and several jobs are to be printed at once. The printer maintains a printing "queue" internally, and prints the jobs in sequence based on which came first. Another instance where queues are extensively used is in the operating system of our machines. An OS maintains several queues such as a job queue, a ready queue, and a device queue for each of the processes.

If you're interested, refer to this link to know more about them. I hope we've got a solid high-level understanding about what queues are. Let's go ahead and understand how they work! Consider a pipe, perhaps a metal one in your bathroom or elsewhere in the house.

Naturally, it has two open ends. Imagine that we have some elements in the pipe, and we're trying to get them out. There will be one end through which we have inserted the elements, and there's another end from which we're getting them out. As seen in the figure below, this is precisely how the queue data structure is shaped.

Unlike the stack data structure that we primarily think of with one "open end", the queue has two open ends: the front and rear. They have different purposes-- with the rear being the point of insertion and the front being that of removal.

However, internally, the front and rear are treated as pointers. We'll learn more about them in the subsequent sections programmatically. Note that the element that got inside first is the initial one to be serviced, and removed from the queue. Similar to how a stack has push and pop operations, a queue also has two pairwise operations:. Click here to check out our lesson on the stack data structure!