Programming and Data

Structures
Module:2
Content
• Computer programming language & types,
• machine and assembly languages, high-level language.
Data Structures:
• Introduction to Data Structures,
• Arrays,
• Stacks,
• Queues.
Computer programming language & types
• The languages that are used to write a program or set of instructions are called "Programming
languages".
• Programming languages are broadly categorized into three types − Machine level language(Low
level). Assembly level language(Middle level). High-level language.
• Computer programming language, any of various languages for expressing a set of detailed
instructions for a digital computer.
• Such instructions can be executed directly when they are in the computer manufacturer-specific
numerical form known as machine language, after a simple substitution process when expressed
in a corresponding assembly language, or after translation from some “higher-level” language.
• Although there are many computer languages, relatively few are widely used.
• Machine and assembly languages are “low-level,” requiring a programmer to manage explicitly all
of a computer’s features of data storage and operation.
• In contrast, high-level languages shield a programmer from worrying about such considerations
and provide a notation that is more easily written and read by programmers.
Types of computer programming languages
There are basically three types of computer programming languages, they are

• Low level programming languages

• Middle level programming languages

• High level programming languages

LOW LEVEL LANGUAGES
• These are machine dependent programming languages such as Binary
(Machine code) and Assembly language.
• Since computer only understand the Binary language that means
instructions in the form of 0’s and 1’s (Signals - that can be either High or
Low), so these programming languages are the best way to give signals
(Binary Instructions) to the computer directly.
• Machine Code (Binary Language) does not need any interpreter or
compiler to convert language in any form because computer understands
these signals directly.
• But, Assembly language needs to be converted in equivalent Binary code,
so that computer can understand the instructions written in Assembly.
Assembler is used to convert an assembly code to its equivalent Binary
code.
• The codes written in such kind of languages are difficult to write, read, edit
and understand; the programs are not portable to any other computer
MIDDLE LEVEL PROGRAMMING LANGUAGE
▪ Assembly language is one level above machine language.
▪ It uses short mnemonic codes for instructions and allows the programmer to introduce names for blocks of memory that hold
data.
▪ One might thus write “add pay, total” instead of “0110101100101000” for an instruction that adds two numbers.
▪ Assembly language is designed to be easily translated into machine language.
▪ Although blocks of data may be referred to by name instead of by their machine addresses, assembly language does not
provide more sophisticated means of organizing complex information.
▪ Like machine language, assembly language requires detailed knowledge of internal computer architecture.
▪ It is useful when such details are important, as in programming a computer to interact with peripheral devices (printers,
scanners, storage devices, and so forth).
▪ Since, there is no such category of computer programming languages, but the programming languages that have features of
low level and high level programming languages come under this category.
▪ Hence, we can say that the programming languages which have features of Low Level as well as High Level
programming languages known as "Middle Level" programming language.
▪ C programming languages is the best example of Low Level Programming languages as it has features of low level and
high level programming languages both.
High level programming languages

• These are the machine independent programming languages, which are easy to
write, read, edit and understand.
• The languages like Java, .Net, Pascal, COBOL, C++, C, C# and other (which are
very popular now to develop user end applications). These languages come under
the high level programming language category.
• High level programming languages have some special keywords, functions and
class libraries by using them we can easily build a program for the computer.
• Computer does not understand program written in such languages directly, as I
have written above that computer understands only Machine code. So, here
programming translators are required to convert a high level program to its
equivalent Machine code.
• Programming translators such as Compilers and Interpreters are the system
software’s which converts a program written in particular programming
languages to its equivalent Machine code.
FEATURES OF HIGH LEVEL PROGRAMMING
LANGUAGES

• The programs are written in High Level programming languages and are
independent that means a program written on a system can be run on
another system.
• Easy to understand - Since these programming languages have keywords,
functions, class libraries (which are similar to English words) we can
easily understand the meaning of particular term related to that
programming language.
• Easy to code, read and edit - The programs written in High Level
programming languages are easy to code, read and edit. Even we can
edit programs written by other programmers easily by having little
knowledge of that programming language.
• Since, High Level language programs are slower than Low level language
programs; still these programming languages are popular to develop
Various - High Level languages

Algorithmic languages
• Algorithmic languages are designed to express mathematical or
symbolic computations.
• They can express algebraic operations in notation similar to
mathematics and allow the use of subprograms that package
commonly used operations for reuse. They were the first high-level
languages.
FORTRAN

• The first important algorithmic language was FORTRAN (formula translation),

designed in 1957 by an IBM team led by John Backus.
• It was intended for scientific computations with real numbers and collections of
them organized as one- or multidimensional arrays.
• Its control structures included conditional IF statements, repetitive loops (so-
called DO loops), and a GOTO statement that allowed nonsequential execution
of program code.
• FORTRAN made it convenient to have subprograms for common mathematical
operations, and built libraries of them.
• FORTRAN was also designed to translate into efficient machine language.
• It was immediately successful and continues to evolve
ALGOL (algorithmic language)
• ALGOL (algorithmic language) was designed by a committee of American and European
computer scientists during 1958–60 for publishing algorithms, as well as for doing
computations.
• ALGOL had recursive subprograms—procedures that could invoke themselves to solve a
problem by reducing it to a smaller problem of the same kind.
• ALGOL introduced block structure, in which a program is composed of blocks that might
contain both data and instructions and have the same structure as an entire program.
• Block structure became a powerful tool for building large programs out of small
components.
• ALGOL contributed a notation for describing the structure of a programming language,
Backus–Naur Form, which in some variation became the standard tool for stating
the syntax (grammar) of programming languages.
C
• The C programming language was developed in 1972 by Dennis Ritchie and
Brian Kernighan at the AT&T Corporation for programming computer operating
systems.
• Its capacity to structure data and programs through the composition of smaller
units is comparable to that of ALGOL.
• It uses a compact notation and provides the programmer with the ability to
operate with the addresses of data as well as with their values.
• This ability is important in systems programming, and C shares with assembly
language the power to exploit all the features of a computer’s internal
architecture.
• C, along with its descendant C++, remains one of the most common languages.
Business-oriented languages

• COBOL
• COBOL (common business oriented language) has been heavily used by businesses since its
inception in 1959.
• A committee of computer manufacturers and users and U.S. government organizations established
CODASYL (Committee on Data Systems and Languages) to develop and oversee the language
standard in order to ensure its portability across diverse systems.
• COBOL uses an English-like notation—novel when introduced.
• Business computations organize and manipulate large quantities of data, and COBOL introduced
the record data structure for such tasks.
• A record clusters heterogeneous data—such as a name, an ID number, an age, and an address—
into a single unit.
• This contrasts with scientific languages, in which homogeneous arrays of numbers are common.
Records are an important example of “chunking” data into a single object, and they appear in
nearly all modern languages.
SQL

• SQL (structured query language) is a language for specifying the

organization of databases (collections of records).
• Databases organized with SQL are called relational, because SQL
provides the ability to query a database for information that falls in a
given relation.
• For example, a query might be “find all records with both last
name Smith and city New York.” Commercial database programs
commonly use an SQL-like language for their queries.
Java

• In the early 1990s Java was designed by Sun Microsystems, Inc., as a

programming language for the World Wide Web (WWW).
• Although it resembled C++ in appearance, it was object-oriented.
• In particular, Java dispensed with lower-level features, including the ability to
manipulate data addresses, a capability that is neither desirable nor useful in
programs for distributed systems.
• In order to be portable, Java programs are translated by a Java Virtual Machine
specific to each computer platform, which then executes the Java program.
• In addition to adding interactive capabilities to the Internet through Web
“applets,” Java has been widely used for programming small and portable
devices, such as mobile telephones.
Python

• The open-source language Python was developed by Dutch

programmer Guido van Rossum in 1991.
• It was designed as an easy-to-use language, with features such as
using indentation instead of brackets to group statements.
• Python is also a very compact language, designed so that complex
jobs can be executed with only a few statements.
• In the 2010s, Python became one of the most popular programming
languages, along with Javagi988 and JavaScript.
Introduction to Data Structures
• Data Structure is a way of collecting and organising data in such a way that we can
perform operations on these data in an effective way. Data Structures is about
rendering data elements in terms of some relationship, for better organization and
storage. For example, we have some data which has, player's name "Virat" and age 26.
Here "Virat" is of String data type and 26 is of integer data type.
• We can organize this data as a record like Player record, which will have both player's
name and age in it. Now we can collect and store player's records in a file or database
as a data structure. For example: "Dhoni" 30, "Gambhir" 31, "Sehwag" 33.
• In simple language, Data Structures are structures programmed to store ordered data,
so that various operations can be performed on it easily. It represents the knowledge of
data to be organized in memory. It should be designed and implemented in such a way
that it reduces the complexity and increases the efficiency.
Basic types of Data Structures

• As we have discussed above, anything that can store data can be called as a data
structure, hence Integer, Float, Boolean, Char etc, all are data structures. They
are known as Primitive Data Structures.
• Then we also have some complex Data Structures, which are used to store large
and connected data. Some example of Abstract Data Structure are :
• Linked List
• Tree
• Graph
• Stack, Queue etc.
• All these data structures allow us to perform different operations on data. We
select these data structures based on which type of operation is required.
The data structures can also be classified on
the basis of the following characteristics:
Characterstic Description
Linear In Linear data structures,the data items are arranged
in a linear sequence. Example: Array
Non-Linear In Non-Linear data structures,the data items are not
in sequence. Example: Tree, Graph
Homogeneous In homogeneous data structures,all the elements are
of same type. Example: Array
Non-Homogeneous In Non-Homogeneous data structure, the elements
may or may not be of the same type.
Example: Structures
Static Static data structures are those whose sizes and
structures associated memory locations are fixed, at
compile time. Example: Array
Dynamic Dynamic structures are those which expands or
shrinks depending upon the program need and its
execution. Also, their associated memory locations
changes. Example: Linked List created using
pointers
Data Structure vs Storage Structure

• Data Structure : The logical or mathematical model

of a particular organization of data
• Storage Structure : Representation of a particular
data structure in the memory of a computer
• There are many possible storage structure to a
particular data structure
• Ex: there are a number of storage structure for a data structure such
as array
• It is possible for two DS to represented by the same storage
structure

21
Classification
• Data Structure
• Linear
• Non-Linear

• A Data structure is said to be linear if its elements from a sequence or

in other words form a linear list

22
Representation in Memory
• Two basic representation in memory
• Have a linear relationship between the elements represented by means of
sequential memory locations [ Arrays]

• Have the linear relationship between the elements represented by means of

pointer or links [ Linked List]

23
Operation on Linear Structure
• Traversal : Processing each element in the list
• Search : Finding the location of the element with a given value or the
record with a given key
• Insertion: Adding a new element to the list
• Deletion: Removing an elements from the list
• Sorting : Arranging the elements in some type of order
• Merging : Combining two list into a single list

24
Array

25
Linear Arrays
• A linear array is a list of a finite number of n homogeneous data
elements ( that is data elements of the same type) such that
• The elements are of the arrays are referenced respectively by an index set
consisting of n consecutive numbers
• The elements of the arrays are stored respectively in successive memory
locations

26
Linear Arrays
• The number n of elements is called the length or size of the array.
• The index set consists of the integer 1, 2, … n
• Length or the number of data elements of the array can be obtained
from the index set by
Length = UB – LB + 1 where UB is the largest index called the upper
bound and LB is the smallest index called the lower bound of the
arrays

27
Linear Arrays
• Element of an array A may be denoted by
• Subscript notation A1, A2, , …. , An
• Parenthesis notation A(1), A(2), …. , A(n)
• Bracket notation A[1], A[2], ….. , A[n]

• The number K in A[K] is called subscript or an index and A[K] is called

a subscripted variable

28
Representation of Linear Array in Memory

1000
1001
1002
1003
1004
1005

:
Computer Memory

29
Representation of Linear Array in Memory
• Let LA be a linear array in the memory of the computer
• LOC(LA[K]) = address of the element LA[K] of the array LA
• The element of LA are stored in the successive memory cells
• Computer does not need to keep track of the address of every
element of LA, but need to track only the address of the first element
of the array denoted by Base(LA) called the base address of LA

30
Representation of Linear Array in Memory
• LOC(LA[K]) = Base(LA) + w(K – lower bound) where w is the number
of words per memory cell of the array LA [w is aka size of the data
type]

31
Example 1
200 LA[1]
Find the address for LA[6] 201 LA[2]
Each element of the array occupy
202 LA[3]
1 byte
203 LA[4]
204 LA[5]
205 LA[6]
206 LA[7]
207 LA[8]

LOC(LA[K]) = Base(LA) + w(K – lower bound) :

LOC(LA[6]) = 200 + 1(6 – 1) = 205
32
Example 2
200
Find the address for LA[16] LA[1]
201
Each element of the array occupy
202
2 byte LA[2]
203
204
LA[3]
205
206
LA[4]
207

LOC(LA[K]) = Base(LA) + w(K – lower bound) :

LOC(LA[16]) = 200 + 2(16 – 1) = 230
33
Representation of Linear Array in Memory
• Given any value of K, time to calculate LOC(LA[K]) is same
• Given any subscript K one can access and locate the content of LA[K]
without scanning any other element of LA
• A collection A of data element is said to be index if any element of A
called Ak can be located and processed in time that is independent of
K

34
Traversing Linear Arrays
• Traversing is accessing and processing (aka visiting ) each element of
the data structure exactly ones

Linear Array
•••

35
Traversing Linear Arrays
• Traversing is accessing and processing (aka visiting ) each element of
the data structure exactly ones

Linear Array
•••

36
Traversing Linear Arrays
• Traversing is accessing and processing (aka visiting ) each element of
the data structure exactly ones

Linear Array
•••

37
Traversing Linear Arrays
• Traversing is accessing and processing (aka visiting ) each element of
the data structure exactly ones

Linear Array
•••

38
Traversing Linear Arrays
• Traversing is accessing and processing (aka visiting ) each element of
the data structure exactly ones

Linear Array
•••

39
Traversing Linear Arrays
• Traversing is accessing and processing (aka visiting ) each element of
the data structure exactly ones

Linear Array
•••

40
Traversing Linear Arrays
• Traversing is accessing and processing (aka visiting ) each element of
the data structure exactly ones

Linear Array
•••

1. Repeat for K = LB to UB
Apply PROCESS to LA[K]
[End of Loop]
2. Exit 41
Inserting and Deleting
• Insertion: Adding an element
• Beginning
• Middle
• End

• Deletion: Removing an element

• Beginning
• Middle
• End

42
Insertion
1 Brown 1 Brown
2 Davis 2 Davis
3 Johnson 3 Johnson
4 Smith 4 Smith
5 Wagner 5 Wagner
6 6 Ford
7 7
8 8

Insert Ford at the End of Array

43
Insertion
1 Brown 1 Brown 1 Brown 1 Brown
2 Davis 2 Davis 2 Davis 2 Davis
3 Johnson 3 Johnson 3 Johnson 3 Ford
4 Smith 4 Smith 4 4 Johnson
5 Wagner 5 5 Smith 5 Smith
6 6 Wagner 6 Wagner 6 Wagner
7 7 7 7
8 8 8 8

Insert Ford as the 3rd Element of Array

Insertion is not Possible without loss of data

if the array is FULL
44
Deletion
1 Brown 1 Brown
2 Davis 2 Davis
3 Ford 3 Ford
4 Johnson 4 Johnson
5 Smith 5 Smith
6 Taylor 6 Taylor
7 Wagner 7
8 8

Deletion of Wagner at the End of Array

45
Deletion
1 Brown 1 Brown 1 Brown
1 Brown
2 Davis 2 2 Ford
2 Ford
3 Ford 3 Ford 3
3 Johnson
4 Johnson 4 Johnson 4 Johnson
4
5 Smith 5 Smith 5 Smith
5 Smith
6 Taylor 6 Taylor 6 Taylor
6 Taylor
7 Wagner 7 Wagner 7 Wagner
7 Wagner
8 8 8
8

Deletion of Davis from the Array

46
Deletion
1 Brown
2 Ford
3 Johnson
4 Smith
5 Taylor
6 Wagner
7
8

No data item can be deleted from an empty array

47
Insertion Algorithm
• INSERT (LA, N , K , ITEM) [LA is a linear array with N
elements and K is a positive integers such that K ≤ N. This
algorithm insert an element ITEM into the Kth position in LA ]
1. [Initialize Counter] Set J := N
2. Repeat Steps 3 and 4 while J ≥ K
3. [Move the Jth element downward ] Set LA[J + 1] :=
LA[J]
4. [Decrease Counter] Set J := J -1
5 [Insert Element] Set LA[K] := ITEM
6. [Reset N] Set N := N +1;
7. Exit

48
Deletion Algorithm
• DELETE (LA, N , K , ITEM) [LA is a linear array with N
elements and K is a positive integers such that K ≤ N. This
algorithm deletes Kth element from LA ]
1. Set ITEM := LA[K]
2. Repeat for J = K to N -1:
[Move the J + 1st element upward] Set LA[J] := LA[J + 1]
3. [Reset the number N of elements] Set N := N - 1;
4. Exit

49
Multidimensional Array
• One-Dimensional Array
• Two-Dimensional Array
• Three-Dimensional Array
• Some programming Language allows as many as 7 dimension

50
Two-Dimensional Array
• A Two-Dimensional m x n array A is a collection of m .
n data elements such that each element is specified
by a pair of integer (such as J, K) called subscript with
property that
1 ≤ J ≤ m and 1 ≤ K ≤ n

The element of A with first subscript J and second

subscript K will be denoted by AJ,K or A[J][K]

51
2D Arrays
The elements of a 2-dimensional array a is shown as below

a[0][0] a[0][1] a[0][2] a[0][3]

a[1][0] a[1][1] a[1][2] a[1][3]
a[2][0] a[2][1] a[2][2] a[2][3]
Rows Of A 2D Array
a[0][0] a[0][1] a[0][2] a[0][3] row 0
a[1][0] a[1][1] a[1][2] a[1][3] row 1
a[2][0] a[2][1] a[2][2] a[2][3] row 2
Columns Of A 2D Array
a[0][0] a[0][1] a[0][2] a[0][3]
a[1][0] a[1][1] a[1][2] a[1][3]
a[2][0] a[2][1] a[2][2] a[2][3]

column 0 column 1 column 2 column 3

2D Array
• Let A be a two-dimensional array m x n
• The array A will be represented in the memory by a block of m x n
sequential memory location
• Programming language will store array A either
• Column by Column (Called Column-Major Order) Ex: Fortran, MATLAB
• Row by Row (Called Row-Major Order) Ex: C, C++ , Java

55
2D Array in Memory
A Subscript A Subscript
(1,1) (1,1)
(2,1) (1,2)
Column 1 Row 1
(3,1) (1,3)
(1,2) (1,4)
(2,2) Column 2 (2,1)
(3,2) (2,2)
(1,3) Row 2
(2,3)
(2,3) Column 3 (2,4)
(3,3) (3,1)
(1,4) (3,2) Row 3
(2,4) Column 4 (3,3)
(3,4) (3,4)

Column-Major Order Row-Major Order 56

2D Array
• LOC(LA[K]) = Base(LA) + w(K -1)

• LOC(A[J,K]) of A[m,n]
Column-Major Order
LOC(A[J,K]) = Base(A) + w[m(K-1) + (J-1)]
Row-Major Order
LOC(A[J,K]) = Base(A) + w[n(J-1) + (K-1)]

57
Stack

58
Basic Idea
• A stack is an Abstract Data Type (ADT), commonly
used in most programming languages. It is named stack
as it behaves like a real-world stack, for example – a
deck of cards or a pile of plates, etc.

59
Stack Representation

• Can be implemented by means of Array, Structure, Pointers and

Linked List.
• Stack can either be a fixed size or dynamic. 60
push

pop

create
STACK
isempty

isfull

61
STACK: Last-In-First-Out (LIFO)
• void push (stack *s, int element);
/* Insert an element in the stack */
• int pop (stack *s);
/* Remove and return the top
element */
• void create (stack *s);
/* Create a new stack */
• int isempty (stack *s);
/* Check if stack is empty */
• int isfull (stack *s);
Assumption: stack contains integer elements!
/* Check if stack is full */
62
Stack using Array

63
Push using Stack

PUSH

top
top

64
Pop using Stack

POP

top
top

65
Stack using Linked List

66
Push using Linked List

PUSH OPERATION

top

67
Pop using Linked List

POP OPERATION

top

68
Basic Idea
• In the array implementation, we would:
• Declare an array of fixed size (which determines the maximum
size of the stack).

• Keep a variable which always points to the “top” of the stack.

• Contains the array index of the “top” element.

• In the linked list implementation, we would:

• Maintain the stack as a linked list.
• A pointer variable top points to the start of the list.
• The first element of the linked list is considered as the stack top.

69
Declaration

#define MAXSIZE 100 struct lifo

{
struct lifo int value;
{ struct lifo *next;
int st[MAXSIZE]; };
int top; typedef struct lifo
}; stack;
typedef struct lifo
stack; stack *top;
stack s;

ARRAY LINKED LIST

70
Stack Creation

void create (stack *s) void create (stack **top)

{ {
s->top = -1; *top = NULL;
/* s->top points to /* top points to NULL,
last element indicating empty
pushed in; stack */
initially -1 */ }
}

ARRAY LINKED LIST

71
Pushing an element into stack

void push (stack *s, int element) void push (stack **top, int element)
{ {
stack *new;
if (s->top == (MAXSIZE-1))
{ new = (stack *)malloc (sizeof(stack));
printf (“\n Stack overflow”); if (new == NULL)
exit(-1); {
} printf (“\n Stack is full”);
exit(-1);
else
}
{
s->top++; new->value = element;
s->st[s->top] = element; new->next = *top;
} *top = new;
}
}

ARRAY LINKED LIST

72
Popping an element from stack
int pop (stack **top)
{
int pop (stack *s) int t;
{ stack *p;
if (s->top == -1) if (*top == NULL)
{ {
printf (“\n Stack underflow”); printf (“\n Stack is empty”);
exit(-1);
exit(-1); }
} else
else {
{ t = (*top)->value;
p = *top;
return (s->st[s->top--]); *top = (*top)->next;
} free (p);
} return t;
}
}

ARRAY LINKED LIST

73
Checking for stack empty

int isempty (stack *s) int isempty (stack *top)

{ {
if (s->top == -1) if (top == NULL)
return 1; return (1);
else else
return (0); return (0);
} }

ARRAY LINKED LIST

74
Checking for Stack Full

int isempty (stack *s) int isempty (stack *top)

{ {
if (s->top == -1) if (top == NULL)
return 1; return (1);
else else
return (0); return (0);
} }

ARRAY LINKED LIST

75
Example: A Stack using an Array
#include <stdio.h>
#define MAXSIZE 100
struct lifo
{
int st[MAXSIZE];
int top;
};
typedef struct lifo stack;
main() {
stack A, B;
create(&A);
create(&B);
push(&A,10);
push(&A,20);
push(&A,30);
push(&B,100);
push(&B,5);
printf (“%d %d”, pop(&A), pop(&B));
push (&A, pop(&B));
if (isempty(&B))
printf (“\n B is empty”);
return;
}

76
Example: A Stack using Linked List
#include <stdio.h>
struct lifo
{
int value;
struct lifo *next;
};
typedef struct lifo stack;
main() {
stack *A, *B;
create(&A);
create(&B);
push(&A,10);
push(&A,20);
push(&A,30);
push(&B,100);
push(&B,5);
printf (“%d %d”, pop(&A), pop(&B));
push (&A, pop(&B));
if (isempty(B))
printf (“\n B is empty”);
return;
}

77
Applications of Stacks
• Direct applications:
• Page-visited history in a Web browser
• Undo sequence in a text editor
• Chain of method calls in the Java Virtual Machine
• Validate XML

• Indirect applications:
• Auxiliary data structure for algorithms
• Component of other data structures

78
Infix and Postfix Notations
• Infix: operators placed between operands:
A+B*C
• Postfix: operands appear before their operators:-
ABC*+
• There are no precedence rules to learn in postfix
notation, and parentheses are never needed

79
Infix to Postfix
Infix Postfix
A+B AB+
A+B*C ABC*+
(A + B) * C AB+C*
A+B*C+D ABC*+D+
(A + B) * (C + D) AB+CD+*
A*B+C*D AB*CD*+

A+B* C 🡪 (A + (B * C)) 🡪 (A + (B C *) ) 🡪 A B C * +

A + B * C + D 🡪 ((A + (B * C)) + D ) 🡪 ((A + (B C*) )+ D) 🡪

((A B C *+) + D) 🡪 A B C * + D +

80
Infix to postfix conversion
• Use a stack for processing operators (push and pop
operations).
• Scan the sequence of operators and operands from left
to right and perform one of the following:
• output the operand,
• push an operator of higher precedence,
• pop an operator and output, till the stack top contains
operator of a lower precedence and push the present
operator.

81
The algorithm steps
1. Print operands as they arrive.
2. If the stack is empty or contains a left parenthesis on top, push the incoming operator onto the
stack.
3. If the incoming symbol is a left parenthesis, push it on the stack.
4. If the incoming symbol is a right parenthesis, pop the stack and print the operators until you
see a left parenthesis. Discard the pair of parentheses.
5. If the incoming symbol has higher precedence than the top of the stack, push it on the stack.
6. If the incoming symbol has equal precedence with the top of the stack, use association. If the
association is left to right, pop and print the top of the stack and then push the incoming
operator. If the association is right to left, push the incoming operator.
7. If the incoming symbol has lower precedence than the symbol on the top of the stack, pop the
stack and print the top operator. Then test the incoming operator against the new top of stack.
8. At the end of the expression, pop and print all operators on the stack. (No parentheses should
remain.)

82
Infix to Postfix Conversion
Requires operator precedence information

Operands:
Add to postfix expression.

Close parenthesis:
pop stack symbols until an open parenthesis appears.

Operators:
Pop all stack symbols until a symbol of lower precedence appears. Then push
the operator.

End of input:
Pop all remaining stack symbols and add to the expression.
83
Infix to Postfix Rules
Current Operator Postfix string
Expression: symbol Stack
1 A A
A * (B + C * D) + E 2 * * A
3 ( *( A
becomes
4 B *( AB

ABC D * +* E+ 5 + *(+ AB
6 C *(+ ABC
7 * *(+* ABC
8 D *(+* ABCD
Postfix notation 9 ) * ABCD*+
is also called as
10 + + ABCD*+*
Reverse Polish
Notation (RPN) 11 E + ABCD*+*E
12 ABCD*+*E+

84
Queue

85
Basic Idea
• Queue is an abstract data structure, somewhat similar to
Stacks. Unlike stacks, a queue is open at both its ends.
One end is always used to insert data (enqueue) and the
other is used to remove data (dequeue).

86
Queue Representation

• As in stacks, a queue can also be implemented using

Arrays, Linked-lists, Pointers and Structures.
87
enqueue

dequeue

create
QUEUE
isempty

size

88
QUEUE: First-In-First-Out (FIFO)
void enqueue (queue *q, int element);
/* Insert an element in the queue */
int dequeue (queue *q);
/* Remove an element from the queue */
queue *create();
/* Create a new queue */
int isempty (queue *q);
/* Check if queue is empty */
int size (queue *q);
/* Return the no. of elements in queue */

Assumption: queue contains integer elements!

89
Queue using Linked List

90
Basic Idea
• Basic idea:
• Create a linked list to which items would be added to one end
and deleted from the other end.
• Two pointers will be maintained:
• One pointing to the beginning of the list (point from where
elements will be deleted).
• Another pointing to the end of the list (point where new
elements will be inserted).
Rear

Front DELETION INSERTION

91
Queue: Linked List Structure

ENQUEUE

front rear

92
Queue: Linked List Structure

DEQUEUE

front rear

93
Example :Queue using Linked List
struct qnode
{
int val;
struct qnode *next;
};

struct queue
{
struct qnode *qfront, *qrear;
};
typedef struct queue QUEUE;

void enqueue (QUEUE *q,int element)

{
struct qnode *q1;
q1=(struct qnode *)malloc(sizeof(struct qnode));
q1->val= element;
q1->next=q->qfront;
q->qfront=q1;
}

94
Example :Queue using Linked List
int size (queue *q)
{
queue *q1;
int count=0;
q1=q;
while(q1!=NULL) int dequeue (queue *q)
{ {
q1=q1->next; int val;
count++; queue *q1,*prev;
} q1=q;
return count; while(q1->next!=NULL)
} {
prev=q1;
q1=q1->next;
}
val=q1->val;
int peek (queue *q) prev->next=NULL;
{ free(q1);
queue *q1; return (val);
q1=q; }
while(q1->next!=NULL)
q1=q1->next;
return (q1->val);
}

95
Problem With Array Implementation
• The size of the queue depends on the number and
order of enqueue and dequeue.
• It may be situation where memory is available but
enqueue is not possible.
ENQUEUE DEQUEUE
Effective queuing storage area of array gets reduced.
0 N

front
front rearrear

Use of circular array indexing

96
Applications of Queues
• Direct applications:-
• Waiting lists
• Access to shared resources (e.g., printer)
• Multiprogramming

• Indirect applications:-
• Auxiliary data structure for algorithms
• Component of other data structures

97