Page 15 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures
Notes
8 LOVELY PROFESSIONAL UNIVERSITY
consecutive numbers, usually 1, 2, 3, …n. If we choose the name A for the array, then the
elements of A are denoted by subscript notation:
a1, a2, a3, ……., an
or, by the parenthesis notation:
A(1), A(2), A(3),……., A(N)
or, by the bracket notation:
A[1], a[2], A[3],…….., A[N]
Regardless of the notation, the number K in A[K] is called a subscript and A[K] is called a
subscripted variable.
Linear arrays are called one-dimensional arrays because each element in such an array is
referenced by one subscript. A two-dimensional array is a collection of similar data elements
where each element is referenced by two subscripts.
Did u know? Such arrays are called matrices in mathematics, and tables in business
applications.
1.3.2 Stack
A stack is a linear structure in which items may be added or removed only at one end. The stack
is a common data structure for representing things that need to maintained in a particular order.
For instance, when a function calls another function, which in turn calls a third function, it’s
important that the third function return back to the second function rather than the first. One
way to think about this implementation is to think of functions as being stacked on top of each
other; the last one added to the stack is the first one taken off. In this way, the data structure itself
enforces the proper order of calls.
Conceptually, a stack is simple: a data structure that allows adding and removing elements in a
particular order. Every time an element is added, it goes on the top of the stack; the only element
that can be removed is the element that was at the top of the stack. Consequently, a stack is said
to have “first in last out” behavior (or “last in, first out”). The first item added to a stack will be
the last item removed from a stack.
Example: Figure 1.1 pictures three everyday examples of such a structure: a stack of
dishes, a stack of pennies and a stack of folded towels.
Figure 1.1: A Stack of Dishes, a Stack of Pennies and a Stack of Folded Towels
Source: http://www.csbdu.in/econtent/DataStructures/Unit1-DS.pdf