Applications of Stack
A stack is a restricted data structure .A stack may be implemented to have a bounded capacity. Stacks have numerous applications, in everyday of human life, from the books in our library, to the blank sheets of paper in our printer tray. All of them follow the Last in First out (LIFO) logic.
Towers of Hanoi :
One of the most applications of stack is solving a puzzle called Tower of Hanoi. According to an old Brahmin story, the existence of the universe is calculated in terms of the time taken by a number of monks, who are working all the time, to move 64 disks from one pole to another. But there are some rules about how this should be done, which are:
One of the most applications of stack is solving a puzzle called Tower of Hanoi. According to an old Brahmin story, the existence of the universe is calculated in terms of the time taken by a number of monks, who are working all the time, to move 64 disks from one pole to another. But there are some rules about how this should be done, which are:
1. Move only one disk at a time.
2. For temporary storage, a third pole may be used.
3. A disk of larger diameter may not be placed on a disk of smaller diameter.
Expression evaluation and syntax parsing :
Reverse Polish notation use a stack structure to hold values. Expressions can be represented in pre-fix; post-fix or infix notations and conversion from one form to another may be accomplished using a stack.
Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code. Most programming languages are context-free languages, allowing them to be parsed with stack based machines.
Backtracking :
Consider a simple example of finding the correct path in a maze. There are a series of points, from the starting point to the destination. We start from one point. To reach the final destination, there are several paths. Suppose we choose a random path. After following a certain path, we realize that the path we have chosen is wrong. So we need to find a way by which we can return to the beginning of that path. This can be done with the use of stacks. With the help of stacks, we remember the point where we have reached. This is done by pushing that point into the stack. In case we end up on the wrong path, we can pop the last point from the stack and thus return to the last point and continue our quest to find the right path. This is called backtracking.
Consider a simple example of finding the correct path in a maze. There are a series of points, from the starting point to the destination. We start from one point. To reach the final destination, there are several paths. Suppose we choose a random path. After following a certain path, we realize that the path we have chosen is wrong. So we need to find a way by which we can return to the beginning of that path. This can be done with the use of stacks. With the help of stacks, we remember the point where we have reached. This is done by pushing that point into the stack. In case we end up on the wrong path, we can pop the last point from the stack and thus return to the last point and continue our quest to find the right path. This is called backtracking.
No comments:
Post a Comment