Data Structures and Applications Unit II

Introduction to Data Structures

• Textbook: "Data Structures using C / C++" by Yedidyah, Augenstein, and Tenenbaum, 2nd edition, 2015.
• Reference Book: "Data Structures and Program Design in C" by Kruse, Leung, Tondo, Mogalla, 2nd Edition, 2019.

Queue Structure

• A queue is a linear structure that operates on a First In First Out (FIFO) basis.
• In queues, the first consumer served is the one who arrived first, distinguishing them from stacks, where the most recently added item is removed first.

Basic Operations on Queues

• Enqueue(): Adds an element to the rear end of the queue.
• Dequeue(): Removes an element from the front of the queue.
• Peek(): Retrieves the front element without removing it.
• isFull(): Checks if the queue has reached its maximum capacity.
• isEmpty(): Verifies if the queue is empty.

Enqueue Operation

• Check if the queue is full; if so, an overflow error occurs.
• Increment the rear pointer to the next available space.
• Insert the new element at the rear position.

Dequeue Operation

• Verify if the queue is empty; if so, an underflow error occurs.
• Access the element at the front position.
• Move the front pointer to the next data element.

Peek Operation

• Confirm if the queue is empty; print "Queue is Empty" if true.
• Access the front element and return its value.

isFull Operation

• Determines if the maximum element count is reached by checking if rear equals MAXSIZE - 1.
• Returns "Queue is Full" if true, otherwise "Queue is not Full."

isEmpty Operation

• Compares if both the front and rear pointers are pointing to NULL.
• Indicates "Queue is empty" if they are; otherwise, "Queue is not empty."

Queue Implementations

• Implementations can be done using arrays and linked lists with specific files for the main logic and structure.

Circular Queue

• A circular queue connects the end position back to the start, creating a circular buffer.
• Utilizes pointers to maintain circular behavior, allowing movement from 0 to N-1 (maximum size).
• The rear pointer indicates the next free position while the front pointer shows the first full position.

Circular Queue Conditions

• A circular queue is empty when rear == front.
• It is considered full when ((rear + 1) % BUFFER_SIZE) == front.

Deque (Double-Ended Queue)

• A deque allows insertion and deletion at both front and rear ends, in contrast to a standard queue.
• Combines properties of both queues and stacks, enhancing flexibility in data management.