![]() Before that, let’s look at how we might use an ordinary Python list to do something similar, using the indexing of a Python list in a clever way. We’ll consider an example problem where dictionaries are useful: document similarity using word frequency histograms. A dictionary allows each value to be accessed by an index, or key that might not be an integer – for example, a string. DictionariesĪ Python list allows each value to be accessed by an integer index. Here is a solution solve the problem yourself before checking the solution. (Hint: none of the bodies of these methods needs to be more than one line long.) Your Queue class should have methods to enqueue an item, dequeue and return the item, empty which returns True if there are no more items on the Queue, and _str_ which returns a string representation of the queue. Write a Queue class that internally uses a list to keep the data in order. It’s convenient to have a class that handles the details of the implementation. ![]() We define the Queue based on the operations available on the Queue, not based on how it is implemented: a Queue is a data type that supports enqueue and dequeue operations. There may be many different ways to implement a data type such as Queue. Objective: write a class that implements a data structure by wrapping a simple data type. I’d recommend using a deque if you need a queue or a stack. (Doubly-linked lists are described in a later chapter.) Perhaps that is how the Python deque class is implemented. When Python deletes an item from the front of a list, the interpreter loops over all remaining items, shifting them one index earlier in the list.Īn alternate implementation would use a data structure called a doubly-linked list for either one, allowing Θ(1) operations to add or remove items from the beginning or end of the list. If you dequeue an item a queue by deleting an item from the front of a list, the run-time is Θ( n) in all cases. You might notice that for the stack implementation above, the worst-case run-time of appending an item is Θ( n) (although it’s only Θ(1) amortized over many appends). At that point there are only two tickets left, so only Alice and Carol are served.Įfficient implementations of stacks and queues Before Eliza is served, Carol and Betty get in line. ![]() Try to mimic the following sequence (each character’s name is denoted by the letter next to them, and you can enqueue them by clicking on them): Dave and Eliza get in line to buy movie tickets, followed shortly by Alice. Here is a visualization of a queue (written by Dartmouth student Daniel Shanker), with enqueue and dequeue operations. We will need operations to enqueue data items at the end of the queue, and dequeue items from the front. Whereas stacks are “last in, first out,” queues are the opposite - “first in, first out.” Like stacks, queues allow for the ordering of objects while following a certain set of rules. Nobody can cut in front of you, and you are guaranteed to get out from the front of the line (dequeue) before anybody behind you. When you get in line (or enqueue) for an amusement park ride, you have your spot in line. Click on a brick to push it onto the stack in the correct order. Here is a visualization of a stack of numbered bricks, written by Dartmouth student Daniel Shanker. We say that the stack is “last in, first out” for this reason. In order to access the bottom plate of a stack of heavy plates, you might first have to take off all of the plates above it one by one, starting from the top. ![]() When you take an object off of the stack, it’s taken off the top of the stack. When you add an object to the stack, it’s added to the top of the stack. StacksĪ stack data structure models a familiar way of organizing objects in the physical world: stacked objects. We’ll look at stacks, queues, and dictionaries. Sometimes data structures are used to organize important data (for example, a collection of names and associated phone numbers), and sometimes data structures are used for book-keeping as an algorithm runs. If you were solving a Sudoku puzzle, you would mark down some possible numbers in each cell.Ī data structure allows information to be organized and stored. For example, if you had to find a path through a picture of a maze, you might use your pencil to draw some paths as you worked out the problem. Sometimes when you solve a problem, it’s helpful to take some notes as you go: book-keeeping.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |