ADT Queue and Types of Queues

DATA STRUCTURES AND ALGORITHMS USING C (CST-003)

B.Tech. 2nd Year Lecture Notes

1. Introduction to Queue

A Queue is a linear data structure in which insertion of an element takes place at one end and deletion takes place at the other end.

A queue follows the principle of:

FIFO — First In, First Out

The element that enters the queue first is the first element to leave the queue.

A real-life example is a queue of people waiting at a ticket counter. The person who arrives first is generally served first.

2. Queue as an Abstract Data Type (ADT)

A Queue ADT defines the behavior and operations of a queue without specifying how the queue must be implemented.

The implementation may use:

• Array

• Linked list

The important operations of Queue ADT are:

The detailed algorithms and C implementations of these operations will be discussed in Topic 4.

3. Basic Terminology of Queue

A queue mainly has two ends:

Front

The front indicates the position from where an element is removed.

Rear

The rear indicates the position where a new element is inserted.

For example, consider:

10, 20, 30, 40

Here:

• 10 → Front element

• 40 → Rear element

4. FIFO Principle

The fundamental property of a normal queue is FIFO.

Suppose the following elements are inserted:

10 → 20 → 30 → 40

The removal order will be:

10 → 20 → 30 → 40

Thus:

Example

If four students enter a laboratory queue in the following order:

1. Student A

2. Student B

3. Student C

4. Student D

Then the service order will normally be:

1. Student A

2. Student B

3. Student C

4. Student D

5. Queue Representation

A queue can primarily be represented using:

1. Array

A fixed-size array is used to store queue elements.

2. Linked List

Dynamic memory allocation is used to create queue nodes.

The choice depends on the application.

6. Types of Queues

The important types of queues are:

1. Simple Queue / Linear Queue

2. Circular Queue

3. Priority Queue

Another commonly discussed variant is the Deque (Double-Ended Queue), in which insertion and deletion can be performed from both ends.

For the present syllabus, the major focus is on:

Simple Queue, Circular Queue and Priority Queue

7. Simple Queue / Linear Queue

A Simple Queue, also called a Linear Queue, is the basic implementation of a queue in which:

• insertion takes place at the rear

• deletion takes place at the front

• FIFO principle is followed

Example

Suppose a queue initially contains:

10 20 30 40

If 50 is inserted:

10 20 30 40 50

If one element is deleted:

20 30 40 50

The element 10 is removed because it was inserted first.

8. Structure of a Linear Queue

In an array implementation, two variables are generally maintained:

• front

• rear

For example:

Queue = [10, 20, 30, 40, 50]
         ↑             ↑
       front          rear

Conceptually:

• front points to the first available element.

• rear points to the last inserted element.

9. Problem with Linear Queue

One important limitation of a simple linear queue implemented using an array is unused space.

Consider an array of size 5:

[10][20][30][40][50]
 ↑                  ↑
front              rear

Now remove three elements:

[ ][ ][ ][40][50]
         ↑       ↑
       front    rear

Although the first three positions are empty, the queue may report that it is full if rear has already reached the last array position.

This is called false overflow or space wastage in a linear array queue.

This limitation motivates the use of a Circular Queue.

10. Circular Queue

A Circular Queue is a queue in which the last position of the array is logically connected to the first position.

When the rear reaches the last position, it can move back to the beginning if free space is available.

The circular arrangement allows previously unused positions to be reused.

11. Need for Circular Queue

Consider an array of size 5.

Initially:

10 20 30 40 50

After deleting three elements:

_ _ _ 40 50

A linear queue may not use the empty locations at the beginning.

A circular queue can reuse these locations.

For example, when new elements 60, 70, and 80 are inserted:

60 70 80 40 50

Thus, circular queues provide better utilization of the available array space.

12. Circular Movement Using Modulo

Circular queues commonly use the modulo operator %.

For an array of size N:

Similarly:

For example, if:

and:

then:

Therefore, rear moves from position 4 back to position 0.

13. Advantages of Circular Queue

1. Efficient utilization of array memory.

2. Avoids unnecessary space wastage.

3. Supports continuous insertion and deletion.

4. Useful in systems requiring repeated processing.

5. Suitable for buffers and scheduling applications.

Applications

• CPU scheduling

• Printer buffering

• Keyboard buffering

• Network packet buffering

• Streaming systems

• Traffic management

• Round-robin scheduling

14. Priority Queue

A Priority Queue is a queue in which every element is associated with a priority.

Unlike a simple FIFO queue, deletion is generally based on priority rather than merely on arrival order.

For example:

If a smaller numerical value represents higher priority, the removal order can be:

B → C → A

15. Priority Queue Principle

The fundamental idea is:

The element having the highest priority is served before an element having lower priority.

If two elements have the same priority, their relative order may be maintained according to the implementation, often following FIFO order.

Example

Suppose:

If priority 1 is highest, the queue may process:

P2 → P4 → P3 → P1

Here, P2 and P4 have the same priority, so their arrival order can be preserved.

16. Types of Priority Queue

Priority queues are commonly categorized as:

1. Ascending Priority Queue

The element with the smallest priority value is served first.

Example:

1 → 2 → 3 → 4

2. Descending Priority Queue

The element with the largest priority value is served first.

Example:

4 → 3 → 2 → 1

The exact meaning of "high priority" depends on the convention adopted by the application.

17. Simple Queue vs Circular Queue vs Priority Queue

18. Queue Operations — Overview

Although the detailed algorithms are covered in the next topic, it is important to understand the basic operations.

18.1 Enqueue

Enqueue means inserting an element into a queue.

For a normal queue:

Insertion occurs at the rear.

Example:

Before:

10 20 30

Enqueue 40:

10 20 30 40

18.2 Dequeue

Dequeue means removing an element from a queue.

For a normal queue:

Deletion occurs from the front.

Before:

10 20 30 40

After dequeue:

20 30 40

Element removed = 10.

18.3 Front / Peek

The front() or peek() operation returns the element at the front without removing it.

Example:

Queue:

10 20 30

front() returns:

10

Queue remains unchanged.

18.4 Rear

The rear() operation identifies the last element in the queue.

For:

10 20 30

the rear element is:

30

18.5 isEmpty()

Checks whether the queue contains no elements.

Conceptually:

if (front == -1)
    printf("Queue is Empty");

The exact condition depends on the chosen queue implementation.

18.6 isFull()

For an array-based linear queue, it generally checks whether:

rear == MAX - 1

For a circular queue, the full condition is different and depends on the implementation.

A common condition is:

(rear + 1) % MAX == front

when one array position is intentionally kept empty.

19. Queue Overflow and Underflow

Queue Overflow

Overflow occurs when an insertion is attempted into a queue that has no available space.

Example:

Queue capacity = 5
Current elements = 5

Attempting another insertion can cause overflow.

Queue Underflow

Underflow occurs when deletion is attempted from an empty queue.

Example:

Queue = Empty

Attempting dequeue() causes underflow.

20. Queue Using Linked List

A queue can also be implemented using a linked list.

Typically, two pointers are maintained:

• front

• rear

The structure consists of dynamically allocated nodes.

The advantage is that the queue does not require a fixed array size.

For a linked-list queue:

• insertion is normally performed at rear

• deletion is normally performed at front

21. Applications of Queue

Queues are extensively used in computer science.

1. CPU Scheduling

Processes waiting for CPU execution can be maintained in queues.

2. Printer Spooling

Print jobs wait in a queue before being processed.

3. Network Communication

Packets may be temporarily stored in queues before transmission.

4. Operating Systems

Various processes and resources can be managed using queues.

5. Breadth-First Search

BFS of a graph uses a queue.

6. Buffering

Queues are used for temporary storage of data between components operating at different speeds.

7. Simulation

Queues are used to model:

• Bank queues

• Traffic systems

• Customer service systems

• Call centers

8. Round-Robin Scheduling

Circular queues are particularly suitable for round-robin CPU scheduling.

22. Queue and Stack — Important Difference

Students frequently confuse stacks and queues.

23. Important Conceptual Example

Suppose the following elements are inserted into a queue:

A, B, C, D

The queue becomes:

A → B → C → D

Now perform two dequeue operations.

First deletion:

A is removed.

Queue:

B → C → D

Second deletion:

B is removed.

Queue:

C → D

Now insert E:

C → D → E

Therefore, the order of removal is:

A → B → C → D → E

This demonstrates the FIFO principle.

24. Comparison of Queue Types

Simple Queue

Best understood as a straightforward FIFO structure.

Circular Queue

Best suited where the storage area is reused continuously.

Priority Queue

Best suited when elements must be processed according to importance or priority.

The appropriate type depends on the application requirements.

25. Complexity Overview

For appropriate implementations, the fundamental queue operations can generally be performed efficiently.

*Assuming both front and rear pointers are maintained.

For priority queues, complexity depends on the underlying implementation, such as:

• Array

• Linked list

• Binary heap

26. Key Points for Examination

Students should remember the following:

1. Queue follows FIFO.

2. Insertion occurs at rear.

3. Deletion occurs at front.

4. enqueue() inserts an element.

5. dequeue() removes an element.

6. peek() returns the front element without deleting it.

7. Linear queues can suffer from unused spaces after deletions.

8. Circular queues solve the space-reuse problem through wrap-around.

9. Circular queues commonly use the modulo operator %.

10. Priority queues process elements according to priority.

11. Queues can be implemented using arrays or linked lists.

12. Queue is used in BFS, scheduling, buffering and resource management.

27. Short-Answer Questions

1. Define a queue.

2. What is FIFO?

3. What are front and rear?

4. Define enqueue and dequeue.

5. What is queue overflow?

6. What is queue underflow?

7. What is a linear queue?

8. What is a circular queue?

9. Why is a circular queue required?

10. What is a priority queue?

11. Differentiate between FIFO and priority-based processing.

12. Give two applications of queues.

13. Differentiate between stack and queue.

14. What is the purpose of the modulo operator in a circular queue?

15. How can a queue be implemented using a linked list?

28. Long-Answer / Descriptive Questions

1. Explain Queue ADT and its basic operations with suitable examples.

2. Explain the FIFO principle of a queue.

3. Explain the representation of a linear queue using an array.

4. Discuss the limitations of a linear queue.

5. Explain circular queue with a suitable example.

6. How does a circular queue overcome the limitations of a linear queue?

7. Explain priority queue and its types.

8. Compare simple queue, circular queue and priority queue.

9. Explain array and linked-list implementations of queues.

10. Discuss various applications of queues in computer science.

29. Programming-Oriented Questions

1. Write a C program to implement a queue using an array.

2. Write a C program to perform enqueue and dequeue operations.

3. Write a C program to implement a circular queue.

4. Write a C program to implement a queue using a linked list.

5. Write a C program to check whether a queue is empty or full.

6. Implement a priority queue using an array.

7. Display all elements of a queue.

8. Implement front() and rear() operations.

Topic Summary

A Queue is a fundamental linear data structure based on the FIFO principle. The two important ends are front and rear. A Simple Queue provides basic FIFO processing but may suffer from space wastage in array implementation. A Circular Queue allows the unused positions of an array to be reused. A Priority Queue processes elements according to their priority rather than simply according to their arrival order.

Topic 3 in one line:

Simple Queue → FIFO, Circular Queue → FIFO + efficient space reuse, Priority Queue → priority-based processing.

Next topic: Topic 4 – Operations on Different Types of Queues, covering detailed Enqueue, Dequeue, Front, Rear, algorithms, C programs, circular queue implementation, priority queue implementation, and complexity analysis.

Applications of Stack – Expression Conversion and Evaluation

1. Introduction

One of the most important applications of a Stack is the processing of arithmetic and logical expressions.

Stacks are particularly useful for:

• Converting expressions from one notation to another

• Evaluating postfix expressions

• Evaluating prefix expressions

• Managing operators and parentheses

• Checking balanced parentheses

• Supporting compiler and interpreter operations

The three commonly used expression notations are:

1. Infix

2. Prefix

3. Postfix

2. Expression

An expression is a combination of operands and operators that represents a computation.

For example:

Here:

• A and B are operands.

• + is an operator.

Another example:

contains:

• Operands: A, B, C

• Operators: +, *

3. Operand

An operand is a value, variable, or data item on which an operation is performed.

Examples:

A
B
X
25
100

In:

A and B are operands.

4. Operator

An operator specifies the operation to be performed on operands.

Common arithmetic operators are:

In C, additional operators such as relational, logical, bitwise, and conditional operators are also available.

For the basic expression-conversion algorithms, arithmetic operators are generally considered.

5. Types of Expression Notations

An arithmetic expression can be represented in three major forms:

1. Infix notation

The operator is written between the operands.

Example:

2. Prefix notation

The operator is written before the operands.

Example:

3. Postfix notation

The operator is written after the operands.

Example:

6. Infix Expression

In infix notation, the operator is placed between its operands.

Examples:

A + B
A - B
A * B
(A + B) * C
A + B * C

This is the notation normally used by humans in mathematics and programming languages.

Example

Here, multiplication has higher precedence than addition, so the expression is interpreted as:

7. Prefix Expression

In prefix notation, the operator appears before its operands.

It is also called Polish notation.

Examples:

+AB
-AB
*AB

For:

the prefix form is:

+A*BC

Prefix notation does not require parentheses to indicate the order of operations when the expression is properly formed.

8. Postfix Expression

In postfix notation, the operator appears after its operands.

It is also called Reverse Polish notation (RPN).

Examples:

AB+
AB-
AB*

For:

the postfix form is:

ABC*+

Postfix expressions are particularly convenient for stack-based evaluation.

9. Comparison of Infix, Prefix and Postfix

Consider:

Another Example

Consider:

10. Why Expression Conversion Is Required

Humans generally prefer infix notation, but computers can process expressions efficiently using other representations.

Infix expressions require consideration of:

• Operator precedence

• Associativity

• Parentheses

Stack-based processing can simplify expression conversion and evaluation.

For example:

can be converted to:

Postfix:

AB+CD-*

The postfix representation makes the evaluation order explicit.

11. Operator Precedence

Precedence determines which operator should be evaluated first when an expression contains multiple operators.

For the basic arithmetic operators:

For example:

Since * has higher precedence than +:

Therefore postfix is:

ABC*+

12. Associativity

When two operators have the same precedence, associativity determines the order in which they are processed.

For example:

The - and + operators have the same precedence and are normally evaluated from left to right:

Common Associativity

The right-to-left associativity of exponentiation is particularly important in expression conversion.

13. Role of Parentheses

Parentheses can override normal precedence.

Consider:

Multiplication is performed first:

But:

requires addition to be performed first.

Thus parentheses have very high priority in expression processing.

14. Infix to Postfix Conversion

The stack is used to temporarily store operators and parentheses during conversion.

Basic Rules

While scanning the infix expression from left to right:

1. If the symbol is an operand, add it directly to the postfix expression.

2. If the symbol is an opening parenthesis (, push it onto the stack.

3. If the symbol is a closing parenthesis ), pop operators until ( is encountered.

4. If the symbol is an operator, compare its precedence with the operator on top of the stack.

5. Pop higher- or appropriately equal-precedence operators before pushing the current operator.

6. After scanning the entire expression, pop all remaining operators.

15. Algorithm: Infix to Postfix

Algorithm

Input: Infix expression E

Output: Equivalent postfix expression

1. Create an empty stack.
2. Scan the infix expression from left to right.

3. If the scanned symbol is an operand:
       Add it to the postfix expression.

4. If the symbol is '(':
       Push it onto the stack.

5. If the symbol is ')':
       Pop from the stack and add to postfix
       until '(' is found.
       Remove '(' from the stack.

6. If the symbol is an operator:
       While the stack is not empty and
       the operator at the top has higher
       precedence than the current operator
       (or equal precedence when left-associative):
           Pop and add it to postfix.

       Push the current operator.

7. After the expression is completely scanned:
       Pop all remaining operators
       and add them to postfix.

8. Return the postfix expression.

16. Example: Infix to Postfix

Convert:

Step-by-step

Therefore:

17. Example: Infix to Postfix with Parentheses

Convert:

Step-by-step

Therefore:

18. Example: More Complex Infix to Postfix

Convert:

Step-by-step

Therefore:

19. Complexity of Infix to Postfix Conversion

Suppose the expression contains n symbols.

Each symbol is scanned once.

An operator may be pushed and popped from the stack at most a constant number of times.

Therefore:

Time Complexity

Space Complexity

In the worst case, the stack may contain O(n) operators/parentheses.

20. Infix to Prefix Conversion

Infix expressions can also be converted to prefix form.

A common stack-based approach is:

1. Reverse the infix expression.

2. Interchange ( and ).

3. Convert the resulting expression to postfix.

4. Reverse the postfix result to obtain prefix.

Example

Convert:

to prefix.

The result is:

*+ABC

Therefore:

21. Algorithm: Infix to Prefix

1. Reverse the infix expression.
2. Replace every '(' with ')' and every ')' with '('.
3. Convert the modified expression into postfix
   using a stack.
4. Reverse the resulting postfix expression.
5. The result is the prefix expression.

Complexity

For n symbols:

22. Postfix Expression Evaluation

One of the most important applications of a stack is postfix expression evaluation.

Consider:

23+

This represents:

For postfix evaluation:

• Operands are pushed onto the stack.

• When an operator is encountered, the required operands are popped.

• The operation is performed.

• The result is pushed back onto the stack.

23. Algorithm: Postfix Evaluation

Input: Postfix expression

Output: Evaluated result

1. Create an empty stack.

2. Scan the postfix expression from left to right.

3. If the symbol is an operand:
       Push it onto the stack.

4. If the symbol is an operator:
       Pop the top operand.
       Pop the next operand.
       Perform the operation.
       Push the result onto the stack.

5. Repeat until the expression is completely scanned.

6. The final element in the stack is the result.

Important

For a binary operator:

operand2 = pop()
operand1 = pop()

result = operand1 operator operand2

The order is important.

For example:

52-

means:

not:

24. Example: Postfix Evaluation

Evaluate:

23*5+

This represents:

Step-by-step

Therefore:

25. Example: Postfix Evaluation with Multiple Operators

Evaluate:

52+83-*

Equivalent expression:

Step-by-step

Therefore:

26. C Program for Postfix Evaluation

The following program evaluates a postfix expression containing single-digit operands.

#include <stdio.h>
#include <ctype.h>

#define MAX 100

int stack[MAX];
int top = -1;

void push(int value)
{
    stack[++top] = value;
}

int pop()
{
    return stack[top--];
}

int evaluatePostfix(char exp[])
{
    int i;
    int operand1, operand2, result;

    for (i = 0; exp[i] != '\0'; i++)
    {
        if (isdigit(exp[i]))
        {
            push(exp[i] - '0');
        }
        else
        {
            operand2 = pop();
            operand1 = pop();

            switch (exp[i])
            {
                case '+':
                    result = operand1 + operand2;
                    break;

                case '-':
                    result = operand1 - operand2;
                    break;

                case '*':
                    result = operand1 * operand2;
                    break;

                case '/':
                    result = operand1 / operand2;
                    break;

                case '%':
                    result = operand1 % operand2;
                    break;
            }

            push(result);
        }
    }

    return pop();
}

int main()
{
    char exp[] = "52+83-*";

    printf("Result = %d\n", evaluatePostfix(exp));

    return 0;
}

Output

Result = 35

Complexity

If the postfix expression contains n symbols:

27. Prefix Expression Evaluation

Prefix expressions can also be evaluated using a stack.

Unlike postfix evaluation, prefix expressions are scanned from right to left.

Example

Consider:

+23

This represents:

28. Algorithm: Prefix Evaluation

1. Create an empty stack.

2. Scan the prefix expression from right to left.

3. If the symbol is an operand:
       Push it onto the stack.

4. If the symbol is an operator:
       Pop the first operand.
       Pop the second operand.
       Perform the operation.
       Push the result onto the stack.

5. Continue until the expression is completely scanned.

6. The final element in the stack is the result.

For an operator:

operand1 = pop()
operand2 = pop()

result = operand1 operator operand2

The exact operand order should be handled carefully for non-commutative operations such as subtraction and division.

29. Example: Prefix Evaluation

Evaluate:

*+23-84

This represents:

Step-by-step

Scan from right to left:

Therefore:

30. Postfix vs Prefix Evaluation

31. Expression Conversion and Evaluation: Overall Process

A typical process can be represented conceptually as:

Infix Expression

↓

Expression Conversion

↓

Prefix / Postfix Expression

↓

Stack-Based Evaluation

↓

Final Result

For example:

↓

Postfix:

AB+C*

↓

Evaluation using Stack

↓

Result

32. Balanced Parentheses Using Stack

Another important application of stack is checking whether parentheses are properly balanced.

Consider:

(A+B)

This is balanced.

But:

(A+B

is not balanced.

Similarly:

((A+B)*C)

is balanced.

Basic Algorithm

1. Create an empty stack.
2. Scan the expression from left to right.
3. If an opening symbol is found:
       Push it onto the stack.
4. If a closing symbol is found:
       If the stack is empty → Not balanced.
       Otherwise pop the corresponding opening symbol.
5. After scanning:
       If stack is empty → Balanced.
       Otherwise → Not balanced.

The same principle can be extended to:

()
{}
[]

Complexity

For an expression containing n symbols:

in the worst case.

33. Important Rules for Expression Conversion

Students should remember these rules:

Rule 1

Operands are normally directly added to the output.

Rule 2

Opening parenthesis ( is pushed onto the stack.

Rule 3

Closing parenthesis ) causes operators to be popped until ( is found.

Rule 4

Higher-precedence operators are processed before lower-precedence operators.

Rule 5

For left-associative operators, an operator of equal precedence on the stack is generally popped before pushing the current operator.

Rule 6

After scanning the complete expression, all remaining operators are popped.

Rule 7

For postfix evaluation, scan left to right.

Rule 8

For prefix evaluation, scan right to left.

34. Common Errors in Expression Conversion

Error 1: Ignoring precedence

Incorrect:

A+B*C → AB+C*

Correct:

A+B*C → ABC*+

because * has higher precedence than +.

Error 2: Incorrect operand order

For:

52-

correct evaluation is:

not:

Error 3: Incorrect handling of parentheses

For:

(A+B)*C

the result is:

AB+C*

not:

ABC+*

Error 4: Forgetting remaining operators

After the complete infix expression has been scanned, all operators remaining in the stack must be popped and added to the output.

35. Complexity Summary

Let n represent the number of symbols in the expression.

The linear time complexity occurs because each expression symbol is processed a limited number of times.

36. Applications of Expression Processing

Stack-based expression processing is useful in many areas of computer science:

1. Compilers

Compilers process and transform expressions during syntax and semantic analysis.

2. Calculators

Expression evaluation systems can use stack-based techniques.

3. Programming Languages

Expressions written by programmers must be interpreted according to precedence and associativity rules.

4. Mathematical Software

Symbolic and numerical systems process mathematical expressions.

5. Interpreters

Interpreters evaluate expressions while executing programs.

6. Expression Parsers

Stacks are fundamental to many parsing techniques.

7. Reverse Polish Notation

Postfix expressions are used in systems based on Reverse Polish Notation.

37. Important Comparison

38. Worked Example for Examination

Convert:

to postfix.

Step 1: Scan A

Output:

A

Step 2: Scan *

Push *.

Step 3: Scan (

Push (.

Step 4: Scan B

Output:

AB

Step 5: Scan +

Push +.

Step 6: Scan C

Output:

ABC

Step 7: Scan )

Pop +.

Output:

ABC+

Remove (.

Step 8: Scan -

* has higher precedence than -, so pop *.

Output:

ABC+*

Push -.

Step 9: Scan D

Output:

ABC+*D

Step 10: End of expression

Pop -.

Final postfix:

39. Key Points to Remember

• Stack is an important data structure for expression conversion and evaluation.

• The three major notations are infix, prefix, and postfix.

• Infix places the operator between operands.

• Prefix places the operator before operands.

• Postfix places the operator after operands.

• Precedence determines operator priority.

• Associativity determines the processing direction when precedence is equal.

• Infix-to-postfix conversion uses a stack.

• Infix-to-prefix conversion can be performed using reversal and stack-based processing.

• Postfix expressions are evaluated from left to right.

• Prefix expressions are evaluated from right to left.

• During evaluation, operands are pushed onto the stack.

• When an operator is encountered, operands are popped, the operation is performed, and the result is pushed back.

• Expression conversion and evaluation generally require O(n) time.

• Balanced-parentheses checking is another important application of stacks.