Applications
Stack of books
Stacks have numerous applications. We
see stacks in everyday life, from the books in our library, to the sheaf of
papers that we keep in our printer tray. All of them follow the Last In
First Out(LIFO) logic, that is when we add a book to a pile of books, we add
it to the top of the pile, whereas when we remove a book from the pile, we
generally remove it from the top of the pile.
Given below are a few applications of stacks in the world of computers:
Converting a decimal number into a binary number
Decimal to
binary conversion of 23
The logic for transforming a decimal
number into a binary number is as follows:
1. Read a number
2. Iteration (while number is greater than
zero)
1. Find out the remainder after dividing
the number by 2
2. Print the remainder
3. Divide the number by 2
3. End the iteration
However, there is a problem with this
logic. Suppose the number, whose binary form we want to find is 23. Using this
logic, we get the result as 11101, instead of getting 10111.
To solve this problem, we use a stack. We
make use of the LIFO property of the stack. Initially we push the
binary digit formed into the stack, instead of printing it directly. After the
entire digit has been converted into the binary form, we pop one
digit at a time from the stack and print it. Therefore we get the decimal
number is converted into its proper binary form.
Algorithm:
function outputInBinary(Integer n)
Stack s = new
Stack
while n
> 0 do
Integer bit
= n modulo 2
s.push(bit)
if s
is full then
return
error
end if
n = floor(n / 2)
end while
while s is
not empty do
output(s.pop())
end while
end function
Notes
continue into the next blog:
Applications part 5 Continue (Abstract Data Type (ADT))
J.W. PRODUCTION