480 Programming and Data Structures
The va*?ue of m is initially zero. The sum obtained is again subtracted from m. This is because if
negative numbers are entered, they are to be considered in the sorting. For example, the value of
sum=20. In real execution, the sum may be different depending on integers entered.
Value of m would be m= - 20 (as pre m = m - 20 when m = 0).
Thus, in the while loop value of m varies from -20 to 20. In this range, all the entered elements are
covered. The value of m changes from -20 to 20, that is, -20, -19 upto +20 in ascending order. Thus,
the same order is applied while saving elements in array C[].
14.11 REPRESENTATION OF A STACK
Stack is an important tool and extensively used in programming languages. Stack is one of the most
essential linear data structures. Implementation of most of the system programs is based on stack
data structure. We can insert or delete an element from a list, which takes place from one end. A
subclass of lists permits the same operations. A linear list belonging to this subclass is called a stack.
The insertion operation of an element onto the stack is called as "push" and deletion operation is
called "pop." Due to the push operation from one end, elements are added in the stack, the stack is
also known as pushdown list. The most and least reachable elements in the stack are known as the
"top" and "bottom" of the stack, respectively. A stack is an arranged collection of elements into
which new elements can be inserted or from which new elements can be deleted at one end. Stack is
a set of elements in a last-in-first-out technique. The end where the insertion or deletion operation is
carried out is called top. In Fig. 14.6 a stack is shown.
Top of the stack
Fig. 14.6 Stack
As shown in Fig. 14.6, the stack is based on the rule last-in-first out. The element appended lastly is
deleted first. If we want to delete element 3, it is necessary to delete first top elements 5 and 4.
You can see in Fig. 14.7, a pot containing plates one above the other. Plates can be inserted or removed
from the top. If some plate is to be removed, the removal operation has to be carried out from the
top. Thus, placing or removing takes place from top, that is, from the same end.
Fig. 14.7 Stack
Linear Data Structure 481
As shown in Fig. 14.8 first integer 1 is inserted and then 2,3,4 and 5 (push). In the second portion
(pop), elements are deleted in opposite order of insertion. The elements are deleted in the order
from 5 to 1. The insertion and deletion operations are carried out at one end. Hence, the recently
inserted element is deleted first. If we want to delete a particular element of the stack, it is necessary
to delete all the elements present above that element. It is not possible to delete element 2 without
deleting elements 5, 4 and 3. The stack expands or shrinks with the passage of time. In the above
example the stack initially expands until element 5 is inserted and then shrinks till the element 2 is
removed. There is no higher limit on the number of elements to be inserted in the stack. The total
capacity of the stack depends on memory of the computer.
5
41
33
23 23
13 13
Push
Pop
Fig. 14.8 Working of a stack
In practical life, we come across many examples based on the principle of stack. A railway system
for shunting the railways is an example of a stack. The incoming trains arrive in sequence in the
stack. The last entered train in the stack leaves first and it will be placed at first on the outgoing
track. Fig. 14.9 shows a picture of a railway system.
Incoming trains Outgoing trains
482 Programming and Data Structures
(a) Empty stack (b) Filled stack
y /
Bottom of stack
V
X
I
I
I
X
Top of stack
1
T unoccupied element
i
(c) Stacks
Fig. 14.10 Representation of a stack
A TOP pointer maintains track of the top elements as shown in Fig. 14.10 (c). When a stack has no
element, it is called an empty stack [Fig. 14.10(a)], that is, the value of TOP is zero. When a stack has
one element the value of TOP is one and so on. Whenever an element is inserted (push operation) in
the stack the value of pointer TOP is increased by one. In the same manner, the value of pointer is
decremented when an element is deleted from the stack (pop operation). The push operation can be
applied to any stack, but before applying pop operation on the stack, it is necessary to make sure
that the stack is not empty. Sometimes to know the top element we have to perform a certain operation;
such an operation is called as stack top(s). If a pop operation is performed on empty stack, it results
underflow. An operation to insert an element more than the capacity of the stack is known as overflow
stack. In the filled stack [Fig. 14.10 (b)] no more elements can be inserted.
Stack is very helpful in every ordered and chronological processing of functions. The most useful
application of stack is in recursion. It saves memory space. The mechanism of stack Last-in- first-out
is commonly useful in applications such as manufacturing and accounting calculations. It is a well-
known accounting concept.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.