Data Structures: Stacks and Queues

Stacks

• Stacks are linear data structures that operate on the Last-In, First-Out (LIFO) principle.
• Elements are added and removed from the top of the stack.
• Common operations include push (add to top), pop (remove from top), peek (view top element), and isEmpty (check if stack is empty).
• Stacks are useful for tasks like function calls, expression evaluation, and undo/redo functionalities.
• Stacks can be implemented using arrays or linked lists.
• Array-based stacks have a fixed size; overflow errors can occur if the stack exceeds its capacity.
• Linked list-based stacks don't have a fixed size but might be slower due to pointer manipulations during push and pop operations.

Queues

• Queues are linear data structures that follow the First-In, First-Out (FIFO) principle.
• Elements are added to the rear (enqueue) and removed from the front (dequeue).
• Common operations include enqueue, dequeue, peek (view front element), and isEmpty (check if queue is empty).
• Queues are used for managing tasks (like in a printer queue), handling requests (like in a call center), and implementing breadth-first search algorithms.
• Queues can be implemented using arrays or linked lists.
• Array-based queues can have overflow problems, while linked list-based queues are size-unrestricted.
• Circular queues, a variation of array-based queues, enhance memory use and avoid array copying during enqueue and dequeue operations.

Tries

• Tries (Prefix Trees) are tree-based data structures optimized for string searching and prefix matching.
• Nodes in the trie represent prefixes of strings. Each node stores pointers to child nodes, representing subsequent characters.
• Trie nodes are typically implemented as arrays or linked lists.
• Trie nodes can store a single character, or multiple references (if each character needs a separate reference for partial substring matching). This depends on the implementation's needs.
• Searching for a string or a prefix in a trie involves traversing the tree using characters and checking for a node marking the end of a word.
• Prefix searches only need traversal until the end of the prefix to identify if any words begin with that prefix.
• Tries handle large string datasets efficiently due to their efficiency in prefix and complete word matching.

Hashing

• Hashing uses hash tables for efficient data storage and retrieval.
• A hash function maps data to an index within the hash table.
• Hash functions are crucial for generating unique indices based on input data.
• Collision resolution handles situations where different data maps to the same index (hash collision).
• Common collision resolutions are separate chaining and open addressing.
• Separate chaining uses a linked list for elements mapping to the same index; each list node holds data and key. Open addressing re-hashes data until an empty table space is found.
• Hashing dramatically improves search, insert, and delete performance compared to other standard data structures.
• Hash function effectiveness, distributing data uniformly across the hash table, is critical for minimizing collisions and maximizing performance.
• Hashing is vital in dictionaries, databases, caches, and applications demanding speedy data retrieval.

This quiz covers key concepts of stacks and queues, two fundamental linear data structures. Explore the Last-In, First-Out (LIFO) principle for stacks and the First-In, First-Out (FIFO) principle for queues, including their operations and use cases. Designed for students learning data structures, this quiz will help reinforce your understanding of these essential topics.