Stack and Queue, Why?

Question

Why and when should I use stack or queue data structures instead of arrays/lists? Can you please show an example for a state thats it'll be better if you'll use stack or queue?

Thanks.

Answer 1

When you want to enforce a certain usage pattern on your data structure. It means that when you're debugging a problem, you won't have to wonder if someone randomly inserted an element into the middle of your list, messing up some invariants.

Answer 2

Because they help manage your data in more a particular ways than arrays and lists.

Queue is first in, first out (FIFO)

Stack is last in, first out (LIFO)

Arrays and lists are random access. They are very flexible and more easily corruptible. IF you want to manage your data as FIFO or LIFO it's best to use those, already implemented, collections.

Answer 3

1. Use a queue when you want to get things out in the order that you put them in.
2. Use a stack when you want to get things out in the reverse order than you put them in.
3. Use a list when you want to get anything out, regardless of when you put them in (and when you don't want them to automatically be removed).

Answer 4

It's a matter of intent. Stacks and queues are often implemented using arrays and lists, but the addition and deletion of elements is more strictly defined.

Answer 5

A stack or queue is a logical data structure; it would be implemented under the covers with a physical structure (e.g. list, array, tree, etc.)

You are welcome to "roll your own" if you want, or take advantage of an already-implemented abstraction.

Answer 6

Apart from the usage enforcement that others have already mentioned, there is also a performance issue. When you want to remove something from the beginning of an array or a List (ArrayList) it usually takes O(n) time, but for a queue it takes O(1) time. That can make a huge difference if there are a lot of elements.

Answer 7

The question is ambiguous, for you can represent the abstract data type of a stack or queue using an array or linked data structure.

The difference between a linked list implementation of a stack or queue and an array implementation has the same basic tradeoff as any array vs. dynamic data structure.

A linked queue/linked stack has flexible, high speed insertions/deletions with a reasonable implementation, but requires more storage than an array. Insertions/deletions are inexpensive at the ends of an array until you run out of space; an array implementation of a queue or stack will require more work to resize, since you'd need to copy the original into a larger structure (or fail with an overflow error).

Answer 8

Arrays/lists and stacks/queues aren't mutually exclusive concepts. Infact any stacks or queue implementations you find are almost certainly using either arrays or lists under the hood.

Array and list structures provide a description of how the data is stored, a long with guarantees of the complexity of fundamental operations on the structures.

Stacks and queues give a high level description of how elements are inserted or removed. FIFO for queues, FILO for stacks.

For example. if you are implementing a message queue, you will use a queue. But the queue itself may store each message in a list. "Pushing" a message adding to the front of the list, "popping" a message taking from the end of the list.

Answer 9

The stack and the Queue are more advanced ways to handle a collection that the array itself, which doesn't establish any order in the way the elements behave inside the collection.

The Stack ( LIFO - Last in first out) and a Queue (FIFO - First in First out ) establish and order in which your elements are inserted and removed from a collection.

You can use an Array or a Linked List as the Storage structure to implement the Stack or the Queue pattern. Or even create with those basic structures more complex patterns like Binary Trees or priority queues, which might also bring not only an order in the insertion and removal of elements but also sorting them inside the collection.

Answer 10

You've been to a cafeteria, right? and seen a stack of plates? When a clean plate is added to the stack, it is put on top. When a plate is removed, it is removed from the top. So it is called Last-In-First-Out (LIFO). A computer stack is like that, except it holds numbers, and you can make one out of an array or a list, if you like. (If the stack of plates has a spring underneath, they say you "push" one onto the top, and when you remove one you "pop" it off. That's where those words come from.)

In the cafeteria, go in back, where they wash dishes. They have a conveyor-belt where they put plates to be washed in one end, and they come out the other end, in the same order. That's a queue or First-In-First-Out (FIFO). You can also make one of those out of an array or a list if you like.

What are they good for? Well, suppose you have a tree data structure (which is like a real tree made of wood except it is upside down), and you want to write a program to walk completely through it, so as to print out all the leaves.

One way is to do a depth-first walk. You start at the trunk and go to the first branch, and then go to the first branch of that branch, and so on, until you get to a leaf, and print it. But how do you back up to get to the next branch? Well, every time you go down a branch, you "push" some information in your stack, and when you back up you "pop" it back out, and that tells you which branch to take next. That's how you keep track of which branch to do next at each point.

Another way is a breadth-first walk. Starting from the trunk, you number all the branches off the trunk, and put those numbers in the queue. Then you take a number out the other end, go to that branch, and for every branch coming off of it, you again number them (consecutively with the first) and put those in the queue. As you keep doing this you are going to visit first the branches that are 1 branch away from the trunk. Then you are going to visit all the branches that are 2 branches away from the trunk, and so on. Eventually you will get to the leaves and you can print them.

These are two very basic concepts in programming.