Stack and Queue, Why?

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?

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 fundamental concepts in programming.

Because they help manage your data in more a particular way 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 also easily corruptible. IF you want to manage your data as FIFO or LIFO it's best to use those, already implemented, collections.

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

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.

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.

Arrays/lists and stacks/queues aren't mutually exclusive concepts. In fact, any stack or queue implementations you find are almost certainly using linked lists under the hood.

Array and list structures provide a description of how the data is stored, along 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. A queue is First-In-First-Out, while a stack is First-In-Last-Out.

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

Stack

Fundamentally whenever you need to put a reverse gear & get the elements in constant time,use a Stack. Stack follows LIFO it’s just a way of arranging data.

Appln:

1. Achieving the undo operation in notepads.
2. Browser back button uses a Stack.

Queue:

Queues are implemented using a First-In-Fist-Out (FIFO) principle

Appln:

1. In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until a service representative is free. CPU scheduling, Disk Scheduling. When multiple processes require CPU at the same time, various CPU scheduling algorithms are used which are implemented using Queue data structure.
2. In print spooling
3. Breadth First search in a Graph
4. Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive, First come first served.

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.

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.

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.

There are algorithms that are easier to conceptualize, write and read with stacks rather than arrays. It makes cleaner code with less control logic and iterators since those are presupposed by the data structure itself.

For example, you can avoid a redundant "reverse" call on an array where you've pushed elements that you want to pop in reverse order, if you used a stack.

I think stack and queue both are memory accessing concepts which are used according to application demand. On the other hand, array and lists are two memory accessing techniques and they are used to implement stack(LIFO) and queue(FIFO) concepts.

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

Stacks are used in cache based applications, like recently opened/used application will comes up. Queues are used in deleting/remove the data, like first inserted data needs to be deleted at first.

The use of queue has always been somewhat obscure to me (other than the most obvious one).

Stacks on the other hand are intrinsically linked to nesting which is also an essential part of backtracking.

For example, while checking if in a sentence brackets have been properly closed or not, it is easy to see that >sentence := chars | chars(chars)chars | chars{chars}chars | chars[chars]chars --- suppose cases like (chars) is not valid
>chars := char | char char
>char := a | b | ... | z | ␢ --- ignored uppercase

So now, when checking a given input is a sentence, if you encounter a (, you must check whether the part from here to ) is a sentence or not. This is nesting. If you ever study about context free languages and the push down automata, you will see in detail how stacks involved in these nested problems.

If you want to see difference between the use of stacks and queues, I recommend that you look up Breadth-First Search and Depth-First Search algorithms and their implementations.