Stacks
Stack is Linear Data Structure (comes under Abstract Data type-ABT) which works on LIFO (Last in First Out). LIFO means Element which Insert at Last Remove very First form the Stack. Both Insertion and Deletion done single end is called TOP of the Stack. Insertion an Element is called Push and Deletion an Element is Called POP of the Stack. Only one operation done at one time.
Stack Representation
A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going to implement stack using arrays, which makes it a fixed size stack implementation.
Operation of Stack: There are two Basic operation in Stack
PUSH: Insert an Element into the Stack.
- Step 1 − Checks if the stack is full.
- Step 2 − If the stack is full, produces an error and exit.
- Step 3 − If the stack is not full, increments top to point next empty space.
- Step 4 − Adds data element to the stack location, where top is pointing.
- Step 5 − Returns success.
Algorithm for PUSH Operation:
Step 1: If TOP >= SIZE – 1 then
Write “Stack is Overflow”
Step 2: TOP = TOP + 1
Step 3: STACK [TOP] = X
POP: Delete an Element from the Stack.
- Step 1 − Checks if the stack is empty.
- Step 2 − If the stack is empty, produces an error and exit.
- Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
- Step 4 − Decreases the value of top by 1.
- Step 5 − Returns success.
Algorithm for POP Operation:
Step 1: If TOP = -1 then
Write “Stack is Underflow”
Step 2: Return STACK [TOP]
Step 3: TOP = TOP - 1
Conditions under Stack Operation:
OverFlow:
When Stack is Full and we want to Insert (PUSH) an Element into the Stack, This Condition is Called Overflow
UnderFlow:
When Stack is Empty and we want to Delete (POP) an Element From the Stack, This Condition is Called Overflow
IsEmpty:
To Check the Stack is Empty or Not.
isempty(): IsEmpty Function Denoted by isempty()
Algorithm of isempty() function −
begin procedure isempty
if top less than 1
return true
else
return false
endif
end procedure
IsFull:
To Check the Stack is Full or Not.
isfull(): IsFull Function Denoted by isfull()
Algorithm of isfull() function −
begin procedure isfull
if top equals to MAXSIZE
return true
else
return false
endif
end procedure
PEEK:
To Get the top data element of the stack, without removing it.
peek() Function: Peek Function Denoted by peek()
Algorithm of peek() function −
begin procedure peek
return stack[top]
end procedure
Application of Stack:
There are some Stack Application
1. Expression evaluation
2. Backtracking (game playing, finding paths, exhaustive searching)
3. Memory management, run-time environment for nested language features.
Expression Evaluation
Evaluate an expression represented by a String. Expression can contain parentheses, you can assume parentheses are well-matched. For simplicity, you can assume only binary operations allowed are +, -, *, and /. Arithmetic Expressions can be written in one of three forms:
Infix Notation: Operators are written between the operands they operate on, e.g. 3 + 4 .
Prefix Notation: Operators are written before the operands, e.g + 3 4
Postfix Notation: Operators are written after operands.
Backtracking
Backtracking is used in algorithms in which there are steps along some path (state) from some starting point to some goal.
Find your way through a maze.
Find a path from one point in a graph (roadmap) to another point.
Play a game in which there are moves to be made (checkers, chess).
In all of these cases, there are choices to be made among a number of options. We need some way to remember these decision points in case we want/need to come back and try the alternative
Consider the maze. At a point where a choice is made, we may discover that the choice leads to a dead-end. We want to retrace back to that decision point and then try the other (next) alternative.
Again, stacks can be used as part of the solution. Recursion is another, typically more favored, solution, which is actually implemented by a stack.
Memory Management
Any modern computer environment uses a stack as the primary memory management model for a running program. Whether it's native code (x86, Sun, VAX) or JVM, a stack is at the center of the run-time environment for Java, C++, Ada, FORTRAN, etc.
The discussion of JVM in the text is consistent with NT, Solaris, VMS, Unix runtime environments.
Each program that is running in a computer system has its own memory allocation containing the typical layout as shown below.
