Queues Data Structures PDF
Document Details
Uploaded by HardyChiasmus8244
Cihan University – Sulaimaniya
Tags
Summary
This document describes queues, a fundamental data structure in computer science. It explains the concept of queues, including operations like enqueue and dequeue, and how queues can be implemented practically. It also introduces palindromes, which are sequences that read the same forward and backward, showing how queues and stacks can be used to identify them.
Full Transcript
Queues Data Structures What is a queue? It is an ordered group of homogeneous items of elements. Queues have two ends: – Elements are added at one end. – Elements are removed from the other end. The element added first is also removed first (FIFO: First In, First Out). ...
Queues Data Structures What is a queue? It is an ordered group of homogeneous items of elements. Queues have two ends: – Elements are added at one end. – Elements are removed from the other end. The element added first is also removed first (FIFO: First In, First Out). Queue Specification Definitions: (provided by the user) – MAX_ITEMS: Max number of items that might be on the queue – ItemType: Data type of the items on the queue Operations – MakeEmpty – Boolean IsEmpty – Boolean IsFull – Enqueue (ItemType newItem) – Dequeue (ItemType& item) Enqueue (ItemType newItem) Function: Adds newItem to the rear of the queue. Preconditions: Queue has been initialized and is not full. Postconditions: newItem is at rear of queue. Dequeue (ItemType& item) Function: Removes front item from queue and returns it in item. Preconditions: Queue has been initialized and is not empty. Postconditions: Front element has been removed from queue and item is a copy of removed element. Implementation issues Implement the queue as a circular structure. How do we know if a queue is full or empty? Initialization of front and rear. Testing for a full or empty queue. Make front point to the element preceding the front element in the queue (one memory location will be wasted). Initialize front and rear Queue is empty now!! rear == front Queue Implementation The class can include: private: int front; void MakeEmpty(); int rear; bool IsEmpty() const; ItemType bool IsFull() const; int maxQue; void Enqueue(ItemType); void Dequeue(ItemType&); Queue Implementation (cont.) maxQue = max + 1; front = maxQue - 1; rear = maxQue - 1; palindromes A palindrome is a sequence of characters, words, numbers, or phrases that reads the same forward and backward, ignoring spaces, punctuation, and capitalization. For example: Words: "madam," "racecar" Numbers: 121, 12321 Phrases: "A man, a plan, a canal, Panama!" Palindromes are often studied in linguistics, Cont. Palindromes are related to queues because of their structural properties. A queue operates on a First In, First Out (FIFO) principle, while a stack operates on Last In, First Out (LIFO). By using both data structures together, you can verify if a sequence is a palindrome: Enqueue each character into a queue (FIFO order). Push each character onto a stack (LIFO order). By comparing the characters dequeued from the queue and popped Example: recognizing palindromes Example Input: "radar" Procedure: Enqueue each character into a queue: Queue = r → a → d → a → r Push each character onto a stack: Stack = r → a → d → a → r Comparison: Dequeue and pop one character at a time and compare: Queue: r, Stack: r (Match) Queue: a, Stack: a (Match) Queue: d, Stack: d (Match) Queue: a, Stack: a (Match) Queue: r, Stack: r (Match)
