Data Structures Using C UNIT-III I Year II Semester BCA

STACKS AND QUEUES

Stack:
A stack is an ordered collection of items into which new items may be inserted
and from which items may be deleted at one end, called the top of the Stack. Stack is a
memory which works with the concept (LIFO) “last in first out”.

Special terminology is used for two basic operations associated with stacks.

1) PUSH is the term used to insert a element into a stack

2) POP is the term used to delete a element from a stack

The removal or addition of elements can take place only at the top of the stack.

Top → 10
8
6
4
2
Consider the above stack containing integers.

10 is the current top element of stack.

If an element is added to the stack, it will be placed on the top of 10. If a element
is to be deleted. It will be 10.

Ex:
push(12) on the stack push(14) on the stack

Top → 12 Top → 14
10 12
8 10
6 8
4 6
2 4
2

Department of Computer Science 1 A.S.N. Degree College, Tenali

Data Structures Using C UNIT-III I Year II Semester BCA
PUSH(16) on
POP an element POP an element
the stack
from the stack from stack
Top →
top→ 12 Top → 10 16
10 8 10
8 6 8
6 4 6
4 2 4
2 2

The last element pushed on to a stack is always the first that will be popped from the
stack that is why stack is called Last-In-First-Out (or) LIFO list.

Applications of Stack:
1. implementation of recursion
2. implement quick sort
3. converting infix expression to postfix expression
4. evaluation of postfix expressions
Implementation of Stacks:

There are two ways for implementing stacks. One is using arrays and other is
used by linked lists.

Operations on Stacks:
Associated with the stack, there are several primitive operations like creating
stack, pushing an element in to the stack, popping an element from the stack and
checking the stack, whether the stack is empty or not etc.,

If a stack is empty and it contains no elements, it is not possible to pop the stack.
Therefore before popping an element, one must ensure that stack is not empty. If stack
is implemented using linked lists there is no upper limit on the number of items that
may be kept in a stack except the limitations of the memory.

If stack is implemented using arrays, array size is the upper limit for the number
of items that may be kept in a stack.

Implementation of stacks using arrays:

Although an array can’t be a stack, it can be the home of the stack. We can
declare an array large enough so that the stack can grow and shrink with in the space
allotted for it during program execution. We can fix one end of the array as a bottom of
the stack, the other end of the array may be used as a top of the stack, which keeps
shifting constantly as items are popped and pushed.

Department of Computer Science 2 A.S.N. Degree College, Tenali

Data Structures Using C UNIT-III I Year II Semester BCA

Inserting or pushing an element into the stack:

To insert or push an element,

i) Check whether the stack is already full or not, i.e., check for stack
overflow. If it is already full. We can’t insert a element into a stack.
ii) If stack is not full, increment the stack top so that it point to the next
location in the stack .
iii) Push the element into stack.

Ex: Consider the following stack.

5 top element =40

top=3
4 max=6
Top → 40 3 where ‘max’ is size of array
30 2
20 1
10 0

Push(50) on to the stack

i) pushing is possible
(since top!=max-1)

ii) Increment top by one

top=top+1 = 3+1=4

iii) Push the element

Stack after pushing

top element =50

Top → 50 top=4
40
30
20
10

Department of Computer Science 3 A.S.N. Degree College, Tenali

Data Structures Using C UNIT-III I Year II Semester BCA

Deleting or popping a element from the stack:

To POP an element from the stack,

1) Check whether the stack is empty or not. If stack is empty, we can’t pop an
element.
2) If stack is not empty pop the element form the stack pointed by the top.
3) Decrement stack top by one.

Ex: Consider the following integer stack.

6
top element=40
5 top=3
max=7
4 max is the size of the array

Top → 40 3

30 2
20 1
10 0

POP an element from the stack

i) Popping is possible
(since top!=-1) i.e stack is not empty.
ii) POP the element from stack
iii) decrement top by one
top=top-1=3-1=2

Stack after popping

Top element =30

Top =2

Department of Computer Science 4 A.S.N. Degree College, Tenali

 Data Structures Using C UNIT-III I Year II Semester BCA

6
5
4
Top → 30 3
2
20
1
10 0

Displaying the contents of stack:

To display the contents of a stack

1) check whether stack is empty or not

2) if stack is empty no elements are available for display
3) if stack is not empty display the contents of stack from bottom to top or top to
bottom as required.
Polish notation: Infix, Prefix, Postfix

The method of writing all operators either before their operands or after them is
called Polish notation. In general simple arithmetic expression can be represented in
three ways, Infix, Prefix, Postfix. In Infix notation the operator is placed between the
two operands. In Prefix notation, the operator precedes the two operands and in
postfix notation the operator follows the two operands.

Ex: Consider the expression A+B

A+B infix
AB+ postfix
+AB prefix

Conversion of infix to postfix and prefix:

The infix operator precedence is as follows,

1. parenthesis( )
2. Exponential
3. Multiplication *, division /
4. Addition +, subtraction – (left to right)

Department of Computer Science 5 A.S.N. Degree College, Tenali

 Data Structures Using C UNIT-III I Year II Semester BCA

The basic rules for conversion process are

Operations with highest precedence are converted first and then after a portion of
expression that has been converted to postfix or prefix is to be treated as a single
operand.

(1) convert the infix expression A+B*C to prefix and postfix

postfix prefix
A+B*C =A+BC* A+B*C=A+*BC
=ABC*+ =+A*BC

Implementation of stack using linked lists:

Stack list can be maintained dynamically by using the concept of linked list.
Figure below shows the concept of stack implementation using linked list.

top
50 top element in stack

40

30

20

10 Null Bottom element in stack

Where top is a pointer variable, which points to top element in the stack.

i) Pushing an element into the stack

A new element can be pushed on to the stack by adjusting the pointers such that
top points to newly pushed element into the stack as shown in figure below.

Department of Computer Science 6 A.S.N. Degree College, Tenali

Data Structures Using C UNIT-III I Year II Semester BCA

top
60 top element in the stack

50

40

30

20

Bottom element in the stack

10 Null

ii) popping an element from the stack:

To pop an element from the stack make sure, there are elements in the stack. If
there are elements in the stack POP the stack top element, adjust the top pointer such
that it points to next available top element in the stack, as shown in figure below

60

Popped element
50 top element after popping

40

30

20

10 Null Bottom element in stack

Department of Computer Science 7 A.S.N. Degree College, Tenali

Data Structures Using C UNIT-III I Year II Semester BCA

iii) To display elements of a stack:

To display the elements of a stack, make sure that there are elements in the stack
if elements are available display them either top to bottom or bottom to top.
Creation of stack using linked list:

1. Create the first element. Hold the address of the first element in a separate
variable.
Ex: top
top
10 Null

2. push a new element when ever required by making ‘top’ points to new
element as shown below.
Ex: top

20 .

10 Null

3. repeat step ‘2’ for pushing.

Ex: top

30

20 .

10 NULL

Department of Computer Science 8 A.S.N. Degree College, Tenali

Data Structures Using C UNIT-III I Year II Semester BCA

4. to pop element, remove the element from top and make top points to next
element.
Ex: top

20

NULL

5. repeat step ‘4’ for popping.

QUEUES

A queue is an ordered collection of elements from which elements may be

deleted at one end called the front of the queue and into which elements may be
inserted at the other end called the rear of the queue.

Queues are called fist-in-first-out (FIFO) lists, since the first element in a queue
will be the first element out of the queue.

Fig. below shows integer queue with 4 elements.

10 20 30
 
Front Rear

‘30’ is the recently entered element into the queue. ‘10’ is the first element in the
queue. If an element is to be inserted into queue, it should be inserted after ‘30’. If an
element is to be deleted it should be 10.

Ex: insert(40)

10 20 30 40
 
Front Rear

Ex: delete an element from queue.

20 30 40
 
Front Rear

Department of Computer Science 9 A.S.N. Degree College, Tenali

Data Structures Using C UNIT-III I Year II Semester BCA

Implementation of Queues:

Queues can be implemented in two ways.

1. Queues can be implemented using arrays.

2. Queues can be implemented using linked lists.
Applications of Queues:
1. Round robin algorithm
2. CPUschedulingin multiprogramming environment
Operations on Queues:

Associated with the queue, there are several primitive operations like creating
queue, inserting an element into the queue, deleting an element from the queue,
displaying the contents of the queue etc.
If a queue is empty and it contains no element, it is not possible to delete an
element from the queue. Therefore, before deleting an element, we must ensure that
queue is not empty.
If queue is implemented using the linked list, there is no upper limit on the
number of elements that may be kept in a queue except the limitations of the memory.
If the queue is implemented using arrays, the no. of elements that can be kept in queue
is equal to the array size.

Implementation of queue using Arrays:

Array can be used to implement queue. Fig. below shows the concept of queue
implementation using array.

10 20 30 40
 
Front Rear

Where Rear is position from which insertion into queue is made. Front is
position from which deletion of elements is made. Front holds the index of the element,
which can be deleted next. Rear holds the index of the recently entered element into the
queue.
(i) Inserting an element into Queue: To insert an element

1. Check whether queue is full (or) not. If queue is full, we can’t insert an element.
2. If queue is not full increment the ‘rear’ by one, so that it points to the next
location in the queue.
3. Insert the element into queue.

Department of Computer Science 10 A.S.N. Degree College, Tenali

Data Structures Using C UNIT-III I Year II Semester BCA

Ex: Insert(40)
0 1 2 3 4
10 20 30 front=0

rear=2
front rear rear =2
i) Insertion possible since rear != max-1, where max is size of array.
ii) Increment is rear by one. rear = rear + 1
= 2+1
= 3
iii) Insert the element.
Queue after insertion:
0 1 2 3 4 front=0
10 20 30 40
  rear=3
front rear

(ii) Deleting an element from Queue: To delete an element from queue :

1. Check whether the queue is empty (or) not. If queue is empty, we can’t delete an
element.
2. If it is not empty, delete the element from queue, which pointed by the ‘front’ of
the queue.
3. Increment the ‘front’ by one.

Ex: Consider the following queue.

Array Index → 0 1 2 3 4 front=0

10 20 30
  rear=2
front rear

i) Deletion possible, since front != -1 OR front is not greater than rear.

ii) Delete the element.
iii) Increment ‘front’ by one, i.e., front = 0+1 = 1
Queue after deletion:

Array Index → 0 1 2 3 4 front=1

20 30
  rear=2
front rear

Department of Computer Science 11 A.S.N. Degree College, Tenali

Data Structures Using C UNIT-III I Year II Semester BCA

(iii) To display the contents of the Queue :

1. Check whether queue is empty (or) not. If queue is empty, no elements

available for display.
2. If queue is not empty, display the contents of queue from front position to rear
position.
CIRCULAR QUEUES
In Linear Queue, the space allotted to the queue will not be utilized fully.
Consider the following linear queue.

0 1 2 3 4 Front=3
a 40 50
  Rear=4
Front Rear
Insertion of another element into above queue is not possible, because the array
can accommodate only 5 elements and last element will be placed at a[4]. Even though,
there is space at a[0], a[1], a[2] the element can’t be inserted.

The inefficient use of space can be overcome by simply viewing the array as a
circular rather than a straight line as shown in fig. below.
0 1 2 3 4
40 50

A circular queue may be viewed as shown in fig. below.

4 0

3 1

Department of Computer Science 12 A.S.N. Degree College, Tenali

Data Structures Using C UNIT-III I Year II Semester BCA

In a circular queue after inserting an element at last position, the next element
will be inserted at first position, if ‘front’ of the queue is not at first position.
Ex: Consider the following circular queue.

0 1 2 3 4 5  Array Index
30 40 50
 
front rear

Insert element ‘60’. After insertion the queue will be

0 1 2 3 4 5
60 30 40 50
 
rear front

Deleted element : 30, after deletion queue will be.

0 1 2 3 4 5
60 40 50
 
rear front
Operations on Circular Queues : The following operations can be performed on circular
queues. Implementation, insertion, deletion and display the elements.
Inserting an element into circular queue : To insert an element into circular queue

1. Check whether there is space to insert an element into Circular Queue.

2. If there is a space update the rear.

If rear is at the maximum position and front is not at first position, update the rear
so that, it points to first position, otherwise increment the rear.

3. Insert the element at rear position.

Ex: Consider the following Circular Queue

0 1 2 3 4
20 30 40
 
front rear
Insert 50 : Queue will be

Department of Computer Science 13 A.S.N. Degree College, Tenali

Data Structures Using C UNIT-III I Year II Semester BCA

0 1 2 3 4
20 30 40 50
 
front rear
Insert 60 : Queue will be
0 1 2 3 4
60 20 30 40 50
 
rear front

Deleting an element from Circular Queue : To delete an element from the Circular
Queue.
1. Check whether there are elements in queue to delete.
2. If there are elements, delete the element from the front position.
3. Update the front. If front is at maximum position and rear is not at minimum
position.
4. Update the front so that, it points to minimum position otherwise increment the
front.
Ex: Consider the following Circular Queue.

0 1 2 3 4
60 70 30 40 50
 
rear front
Delete an element : deleted element is 40. After deletion queue will be

0 1 2 3 4
60 70 30 50
 
rear front

Delete an element : Deleted element is 50. After deletion queue will be

0 1 2 3 4
60 70 30
 
front rear

Displaying the elements of the Queue : To display the elements of the Circular
Queue :
1. Check, whether there are elements in Circular Queue.
If there are elements, display them from front position to rear position.

Department of Computer Science 14 A.S.N. Degree College, Tenali

Data Structures Using Java II Year IV Semester B.Sc., B.C.A

Department of Computer Science 15 A.S.N. Degree College, Tenali