Data & Procedure Stacks
~[case study]
We’ll now turn our attention to two simple ADTs, the Stack ADT and the Queue ADT. Unlike the other ADTs we have studied (List, Set, Map), these are not represented in java. util package. Moreover, they do not have any new capabilities beyond those of the other ADTs. In fact, both are special cases of the List ADT. Still, they are important restrictions of the List ADT, and they occur often enough that computer scientists give them special names.
~Stacks —
The Stack ADT is for representing a stack of information, where you can add or remove elements at the top of the stack, but you cannot access data below the top. It includes four operations.
~Case study 1: Program stack
[case study problem statement how program stack work??*]
Each method has a collection of variables that it uses while it is working, including both the parameter values and other local variables declared within the method. This collection of variables is called that method’s activation record. (This phenomenon is especially notable with recursive methods: Changing a local variable at lower levels of the recursion has no effect on the variable of the same name in upper levels. This occurs because each recursive call gets its own activation record.) Computers store activation records for methods currently in execution on a stack called the program stack.
~[Case handled, tools and technology used]
It stores its location within A inside A’s activation record.
It pushes an activation record for B onto the top of the stack, initializing the variables corresponding to B’s parameters based on the values designated by
It begins executing the code for B
~[Analysis of case study]
part of the implementation underlying the execution of Java programs, so it’s not something that we can demonstrate in Java code. But understanding how the computer actually processes the execution of methods is a key component to understanding how Java programs work.
[References, literature survey]
http://www.ijirt.org/master/publishedpaper/IJIRT101357_PAPER.pdf
~case study 2: Postfix expression evaluation
[case study problem statement ??*]
How to Postfix expression evaluation works
[Case handled, tools and technology used]
Expression evaluation is a case where one might want to use a stack in Java programs. We’ll look at the simplest case of evaluating expressions given in postfix order. Recall that with postfix order, the operator is given after the arguments. For example, the expression normally written 2 + 3 would be written 2 3 + instead. The following is a more sophisticated example, with the corresponding expression tree.
[Analysis of case study]
Stacks are also useful for evaluating prefix-order expressions and infix-order expressions, but the algorithms are more complex
[References, literature survey]
http://ijirt.org/master/publishedpaper/IJIRT101022_PAPER.pdf
~case study 3 :
[case study problem statement ]
how the In-order tree traversal works ???
[Case handled, tools and technology used methodology]
[Analysis of case study]
Each call to next, we’ll pop the top node, push all the nodes along the path to the leftmost node of the popped node’s right subtree, and then return the popped node’s value. The following sequence illustrates how this works.
[References, literature survey]