Understanding ADTs: Lists, Stacks, and Queues - Implementation and Operations

Explore the world of Abstract Data Types (ADTs) - Lists, Stacks, and Queues, focusing on their operations like adding, removing, and accessing elements. Learn the differences between array and linked list implementations, along with insights on how to manipulate data structure implementations. Dive into the intricacies of inserting, pushing, and dequeuing elements, as well as the complexities of removing elements and accessing specific locations within these data structures.

• ADTs
• Abstract Data Types
• Data Structures
• Operations
• Implementations

con_c Follow

Uploaded on Oct 03, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Help Session: ADTs: List, Stack, Queue Proof by Induction Ezgi Shenqi Bran 4/4/2016 CSE 373 Spring 2016 1

2. ADTs so far List Stack Queue Adding Elements insert (at any location) push (only to the last location, top of the stack) enqueue (only to the last location, back of the queue) Removing Elements remove (from any location) pop (only from the last location, top of the stack) dequeue (only from the first location, front of the queue) Accessing Elements retrieve (from any location) top (only the last element, top of the stack) front (only the first element, front of the queue) 4/4/2016 CSE 373 Spring 2016 2

3. java.util.queue class ArrayQueue.java ... ADT vs Implementation how to change the data structure implementation eg: queue Data Structure program (user) ADT enqueue dequeue isFull isEmpty front CSE 373 Spring 2016 printer your first hw! (Executor.java) array linked list 4/4/2016 3

4. Implementations List Stack Queue Adding Elements insert (at any location) push (only to the last location, top of the stack) enqueue (only to the last location, back of the queue) - Move n elements if not inserting to the end - O(n) - Update the pointer - O(1) - Update the pointer - O(1) Array Implementation - Traverse until the location - O(n) - Add a new node - O(1) - Add a new node - O(1) Linked List Implementation 4/4/2016 CSE 373 Spring 2016 4

5. Implementations List Stack Queue Removing Elements remove (from any location) pop (only from the last location, top of the stack) dequeue (only from the first location, front of the queue) - Move n elements if not removing from the end - O(n) - Update the pointer - O(1) - Update the pointer - O(1) Array Implementation - Traverse until the location - O(n) - Remove a node - O(1) - Remove a node - O(1) Linked List Implementation 4/4/2016 CSE 373 Spring 2016 5

6. Implementations List Stack Queue Accessing Elements retrieve (from any location) top (only the last element, top of the stack) front (only the first element, front of the queue) - O(1) - O(1) - O(1) Array Implementation - Traverse until the location - O(n) - O(1) - O(1) Linked List Implementation 4/4/2016 CSE 373 Spring 2016 6

7. Example: Palindromes A palindrome A string of characters that reads the same from left to right as its does from right to left noon, radar, level, racecar Eve, Hannah A man, a plan, a canal - Panama! How would you recognize a palindrome using ADTs? Hint: order matters in both directions 4/4/2016 CSE 373 Spring 2016 7

8. Example: Palindromes To recognize a palindrome, a queue can be used in conjunction with a stack A stack reverses the order of occurrences A queue preserves the order of occurrences As you traverse the character string from left to right, insert each character into both a queue and a stack Compare the characters at the front of the queue and the top of the stack 4/4/2016 CSE 373 Spring 2016 8

9. Example: Palindromes abcd Enqueue into a queue and push into a stack Dequeue from the queue and pop from the stack d c a b c d b a b c d a d c b a queue stack 4/4/2016 CSE 373 Spring 2016 9

10. Example: Palindromes hannah Enqueue into a queue and push into a stack Dequeue from the queue and pop from the stack h a n n h a n n a h a h a n n a h h queue h a n n a h stack 4/4/2016 CSE 373 Spring 2016 10

11. Real Life Applications Stacks: (when you need to reverse something) Recursion Function call Have you ever heard of stack overflow ? Redo / Undo Queues: (when you want to preserve the order) Routers Printers OS scheduling 4/4/2016 CSE 373 Spring 2016 11

12. Proof by Induction A proof consists of three parts: 1. Prove it for the base case. 2. Assume it for some integer k. 3. With that assumption, show it holds for k+1. 4/4/2016 CSE 373 Spring 2016 12

13. Proof by Induction: Example 1 ? ??= ?0+ ?1+ ?2+ ?3+ + ??=??+1 1 ? 1 ?=0 ??? ? 1 Remember special case from lecture ? = 2: 20+ 21+ 22+ + 2?= 2?+1 1 4/4/2016 CSE 373 Spring 2016 13

14. ?0+ ?1+ ?2+ ?3+ + ??=??+1 1 ? 1 1. Base case: ? = 0 ?0=?0+1 1 ? 1 1 = 1 2. Assume that the statement is true for ? = ?. ?0+ ?1+ ?2+ ?3+ + ??=??+1 1 ? 1 3. Induction: Show that following statement is also true. ?0+ ?1+ ?2+ ?3+ + ??+1=??+2 1 ? 1 4/4/2016 CSE 373 Spring 2016 14

15. 2. Assumption: ?0+ ?1+ ?2+ ?3+ + ??=??+11 3. Induction: ?0+ ?1+ ?2+ ?3+ + ??+1 ? 1 = ?0+ ?1+ ?2+ ?3+ + ??+ ??+1 ??+1 1 ? 1 + ??+1 = ??+1 1 ? 1 ? 1 ??+1 (? 1) = + =??+1 1 + ? ??+1 ??+1 ? 1 =? ??+1 1 ? 1 ??+2 1 ? 1 = 4/4/2016 CSE 373 Spring 2016 15

16. Proof by Induction: Example 2 ? 1 ? ? + 1 ? ??? ? + ? (? + 1)= ?=1 1 1 1 1 ? 1 2+ 2 3+ 3 4+ + = ? ? + 1 ? + 1 4/4/2016 CSE 373 Spring 2016 16

17. 1 1 1 1 ? 1 2+ 2 3+ 3 4+ + = ? ? + 1 ? + 1 1. Base case ? = 1 (remember ? +) 1 1 1 2=1 1 2= 1 + 1 2 2. Assume that the statement is true for ? = ?. 1 1 1 1 ? 1 2+ 2 3+ 3 4+ + = ? ? + 1 ? + 1 3. Induction: Show that the statement is also true for ? = ? + 1. 1 1 1 1 =? + 1 ? + 2 1 2+ 2 3+ 3 4+ + (? + 1) ? + 2 CSE 373 Spring 2016 4/4/2016 17

18. 1 1 1 1 ? 1 2+ 2 3+ 3 4+ + ? ?+1= 2. Assumption: ?+1 3. Induction: 1 1 1 1 1 2+ 2 3+ 3 4+ + ? + 1 ? + 2 1 1 1 1 1 = 1 2+ 2 3+ 3 4+ + + ? + 1 ? + 2 ? ? + 1 ? 1 = ? + 1+ ? + 1 ? + 2 ? (? + 2) ? + 1 (? + 2)+ 1 = ? + 1 ? + 2 ?2+ 2 ? + 1 ? + 1 (? + 2)= ? + 12 ? + 1 (? + 2)=? + 1 = ? + 2 4/4/2016 CSE 373 Spring 2016 18