There is another data strucutre that used to store tons of data. Therefore, it has two special operations known as the insert and the pop. However, there are two types of ways to make policies for inserting and poping a data from a structure.
Depending on this two method, it is so-called as a stack or a queue. Stack has a property known as LIFO(Last-In-First-Out). Queue has a property known as FIFO(First-In-First-Out).
Stack
If we insert a data into a stack first, it should be popped from the stack first. Therefore, it reserves the order we inserted even when it is popped.
Queue
If we insert a data into a queue first, it should be popped from the stack later. Therefore, it reverses the order we inserted even when it is popped.
Complexity
If we use a list for implementing a stack and a queue, it is easy to get a good performance because we already has $O(1)$ complexity for inserting and deleting at the front and the end of the list.
| Time complexity | Stack | Queue |
|---|---|---|
| Insert | $O(1)$ | $O(1)$ |
| Pop | $O(1)$ | $O(1)$ |
| Space complexity | $O(n)$ | $O(n)$ |