What is the reason for the application of the concept LIFO (Last In, First Out)?

Question

Is there an advantage in implementing the concept LIFO (Last In, First Out) or is it just a semantic question to represent an order in algorithm logic?

Answer 1

The pure application of this concept of UEPS (Last In, First Out) does not bring an inherent obvious advantage. Its application in a specific way can be very advantageous. The concept itself is too broad to indicate an advantage.

LIFO is almost synonymous with pile (stack) when it comes to computing. Part of the advantage of having a stack has already been answered in What are and where are the "stack" and "heap"?. And there’s another stack answer that helps understand: How it works and uses the C Stack#?.

Without a pure pile shape it may not have that much advantage. It is possible to implement LIFO as a linked list, for example, and so it is very bad and does not bring clear advantages from the point of view of computing in general.

It is possible to apply LIFO to something because the semantics of the problem requires it, but then we can’t talk about computational advantage, it is a requirement of the problem.

For general stack computing or local memory call/allocation stack are the greatest examples of concept usage, but the gain is even because it is a stack.

So the stack is advantageous because it doesn’t have to keep anything sophisticated where the data collection starts and ends, it’s not hard to go through it, and mostly it’s cheap to include and exclude new elements in the collection. As you can only add at the top of the stack (last in) no further processing required, as long as you have space available, and as you can only remove what’s on top of the stack (first out) just change what is the top of the stack without any extra processing, taking the data that is there easily and always directly (O(1)).

Already the application of stacks, in addition to the specific domains that need the specific semantics that what enters last is the first to leave (lower values nearby or the nearest neighbor, history of actions to do rollback), in computing has a lot of application, for example backtrackings several (in general analyzing nested data), Parsing in various levels and modalities, management Chunks of heap free (in some implementations) and some processor scheduling managements, Depth-first search, and those already cited at the beginning of the question, in addition to the most obvious one is recursion.

Answer 2

I do not believe that the application of the concept of structure LIFO (or the semantic variant FILO - First In, Last Out) be a matter of head start, but rather of appropriateness the requirement of a particular process.

As an example, consider the nested transactions of a database. Certain behaviors are expected:

• Data changes will only be made available when a transaction is confirmed (via commit);
• Subsequent transactions define their own scope, where the parent transaction will only have access to the changed data in the daughter transaction when it is confirmed.

Now imagine a situation where a transaction T1 is started, followed by a new transaction T2. The nesting structure can be described as a LIFO queue, where T2 was the last member to be lined up.

If the transaction confirmation T1 is requested by the user the database can decide between two options:

• Inform that the action is not possible due to other pending transactions (simply checking whether T1 is at the top of the stack), or
• Perform confirmation of all transactions listed in the LIFO structure, starting with the last added member (T2).

Answer 3

I won’t go into the traditional merit, which I believe the answers of Maniero and Onosendai already answer the core of the question, but I will get into the real advantage of using batteries in some classes of problems. So expect to see complexity classes in this answer and if, by chance, the term "complexity class" doesn’t make sense to you, then this answer won’t add much.

In decision problems, there are some problems that it is possible to answer in time finite, if the answer to it is yes. On the other hand, I may not be able to answer nay. The most typical example of these problems in which there is answer to yes but perhaps there is no answer to nay is the parade problem. These problems belong to the class RE. All problems within this class can be solved by a turing machine.

The name RE means recursively enumerable

On the other hand, we have another class of problems: those that answer nay in finite time, but not necessarily answered yes in finite time. These problems belong to co-RE.

The prefix co means "complement", the complement being understood as the complement operation of Set Theory

And there are those problems that you can answer in finite time yes or nay. These problems are at the intersection of RE and co-RE, the so-called class R.

The name R means recursive

While for trouble RE you need a Turing machine with full capacity, for problems R you get resolution with a Turing machine with a finite size input-dependent tape.

Yeah, but what does that mean at the end of the day?

When you are checking to see if it is possible to answer, you have a tape of the Turing machine filled with the head positioned in an arbitrary location, and the machine is in another arbitrary state. From there, you have a finite amount of changes:

• the states that the Turing machine can assume are defined by a finite set S
• the symbols that the Turing machine can fill into a tape cell are bounded by the finite set Σ
• Turing machine can go left on tape or right on tape
  • there are some authors who speak of a third possibility: of the Turing machine continuing in the same position

Therefore, the next state is in a finite amount of options to search for. If the problem is R, this means that there is a maximum depth of states (in the state change graph of the machine/tape) that runs until finding an alley with the answer yes or nay, which means that if you get a positive response, it’s on another course. Also remember that because the Turing machine that solves these problems has a limited tape size, it means that it cannot go continuously to the right, because one day it will hit the edge of the ribbon and be in an invalid state and a Kuegelblitz will appear and the universe will be swallowed by a black hole formed by the gravity of photons in compact space.

However, in a problem RE, It may not be possible to indicate that a path has reached the end of processing. The Turing machine will continue to move to the right without ever arriving at a conclusion whether the answer to that path is nay.

In the structure of solving these problems, if you use a pile (LIFO) for a problem RE, You can walk into an infinite well and never leave there to investigate another way. The correct way to search for an answer to problems in this class is by using a queue (FIFO).

In class trouble R, however, use a pile can present an answer more quickly as you will be going in depth on the problem. A search in width requires checking many intermediate paths that, perhaps, do not lead to the answer, not to mention that they need a memory without limits.

So at the end of the day:

• the stack offers less search capability in terms of problem classes that solve with searches
• the stack offers a lower limit of maximum memory used for problems that it can actually solve
• potentially the stack will respond more quickly to a yes for your problem

See more about search in width x deep search

---

Another point I would like to highlight here, about automata:

• stack automata can answer problems that can be represented by a context-free language
• queue automata are equivalent in problem solving power to Turing machines

Answer 4

Regarding the subject Data Structures, we have 2 Stacks and Queues, each with its behavior and purpose.

In the Queue, we have the FIFO (First Input, First Output) behavior, where the First Element to Enter must be the First Element to Exit.

Then, in the Fila (FIFO), we have two points, one Input and one Output.

On the Stack, we have the LIFO (Last Input, First Output) behavior, where the Last Entry Element must be the First Out.

Then, on the Stack (LIFO), we have a single Input and Output point.

Answer 5

The use of the data structure pile is one of the ways to calculate the result of an algebraic expression using Polish inverse notation to represent the expression. In practice we use infix notation, when the operator appears among the operands to which it applies, plus the use of parentheses to define the order of calculation, which is not practical for use in computers. In Polish notation the order operands - operator is changed to post-fixed notation and parentheses are deleted, see shunting-Yard algorithm

Answer 6

There are no advantages, it depends on the need of each application.

An example of using LIFO are recursive functions, where you need to return calls in reverse order, from last to first.

Already in a data integration queue with a Web API you need the upload order to be from the oldest to the latest, ie a FILO.