Stack, an abstract data type(ADT) was formally introduced to me during week 2 lectures by Professor Danny Heap. Later, during tutorials and lectures, I also became familiarized with two other ADTs called queue and tree. Although I understood the application of stacks and queue, I still could not understand why they are called abstract data types. Moreover, I was unable to discern the difference of ADTs from other built-in data types such as list, dict, str and tuple, etc,. Hence, in today’s slog, I will be giving a detailed summary on ADT as well as introducing the three examples of ADTs I encountered in class.
First of all, an abstract data type is a model for a particular data structure defined by the methods it can perform. One thing to keep in mind is that not only can ADT be implemented in python, it can also be implemented in other programming languages like C, java, etc,. This is because ADTs do not contain detailed codes on their implementation. In other words, ADT is concerned only with what the data is representing in general but not the the specifics for its construction.
Now, I will discuss the definition and purpose of stack. A stack is used to store countless data in an order in which new items are added to the top of the stack, while the top item always gets removed. Hence the acronym LIFO, which stands for “last-in-first-out” is used to describe stack. Furthermore, stack includes three basic operations. The first method is push(item), where the new data is added to the top of the stack. The second operation is pop() which functions to remove the top (also last) item from stack. And the last method that I was introduced to in class was isEmpty(), which returns True if the stack is empty, else False if the stack contains at least one item. Although Danny did not teach the class all the methods related to stack. I was able to learn them on my own due to my incessant curiosity, After researching online, I discovered that stack also included other operations such as peek(), which returns the topmost item from stack without making any modifications to the stack, and size(), which returns the number of items in the stack. Lastly, real life applications of stack are stacking of plates or books. To see the example calls on these methods, check the link:
The second ADT that I learned is queue. And I learned it in a tutorial as I was told to write my own code on implementation of queue. Similar to stack, a queue also stores data. However, it operates in a FIFO fashion, which stands for “first-in-first-out”. It includes three basic methods (these are the methods I was asked to write during my CSC148 lab). The first operation is enqueue(item) that adds a new item to the the rear of queue. In other words, as items are being added to a queue, the first item is being pushed to the top. Thus, the last added item is at the bottom of queue, which is different from that of stack (as aforementioned, the last item to be added locates at the top of the stack). The second function is dequeue() that serves to remove the first and topmost item from the queue. Lastly, similar to stack, queue also has a method called isEmpty() that returns True if queue contains no data, and false otherwise. Moreover, queue also has the operation size() that returns the number of items stored in it. The real life applications of queue are people lining up to board an airplane or buy tickets from a ticket booth. Lastly, its example calls can be viewed by clicking the link: http://interactivepython.org/runestone/static/pythonds/BasicDS/queues.html
.gif)
The third and last ADT I learned is tree. To begin, similar to stack and queue, tree also stores data. However, it stores data in a hierarchical order. Each item/object is called a node, and we refer to the bottom nodes that happen to branch out the top node as the children of the top node. Furthermore, nodes without any children is referred simply as leaves, whereas, the top most node is called the root. Functions for trees that I was taught in class and tutorials included determining the height of the tree, the number of children, etc,. So far, the class only looked at binary trees (trees where a node only has a maximum of 2 children, called the left and right subtree) in great detail. To sum up, the ADT tree is a real world tree flipped upside down. In my CSC148’s assignment two, I will be combining recursion with tree to assess every possible outcomes of the Tippy Game, and then return the best strategy for the player to win the game. (This idea is required in the class called StrategyMinimax).
In conclusion, throughout these 7 weeks of class, I learned about abstract data types and its three specific examples — stack, queue and tree. Up until now, the most difficult ADT I learned is tree. However, I have no problem understanding its structure and implementation, since my quizzes about count_leaves is perfect, and I was able to complete the labs regarding trees in a efficient and speedy manner. One thing about tree that I enjoy is its frequent application of recursion. This is because I find writing recursions challenging yet satisfying at the same time after reaching a solution. Hence I was elated to find out that I will be combining both tree and recursion in Assignment 2’s StrategyMinimax. So far, my group has completed the codes for TippyGameState and TippyMove, and we will be writing StrategyMinimax tomorrow. Hopefully, my group can finish the GameState by Monday. Lastly, the advantages of using abstract data types is that ADTs can be reused in future programs. Further, their implementations can be easily modified without having to make troublesome changes to the program that uses the ADTs.
Now, I will discuss the definition and purpose of stack. A stack is used to store countless data in an order in which new items are added to the top of the stack, while the top item always gets removed. Hence the acronym LIFO, which stands for “last-in-first-out” is used to describe stack. Furthermore, stack includes three basic operations. The first method is push(item), where the new data is added to the top of the stack. The second operation is pop() which functions to remove the top (also last) item from stack. And the last method that I was introduced to in class was isEmpty(), which returns True if the stack is empty, else False if the stack contains at least one item. Although Danny did not teach the class all the methods related to stack. I was able to learn them on my own due to my incessant curiosity, After researching online, I discovered that stack also included other operations such as peek(), which returns the topmost item from stack without making any modifications to the stack, and size(), which returns the number of items in the stack. Lastly, real life applications of stack are stacking of plates or books. To see the example calls on these methods, check the link: The second ADT that I learned is queue. And I learned it in a tutorial as I was told to write my own code on implementation of queue. Similar to stack, a queue also stores data. However, it operates in a FIFO fashion, which stands for “first-in-first-out”. It includes three basic methods (these are the methods I was asked to write during my CSC148 lab). The first operation is enqueue(item) that adds a new item to the the rear of queue. In other words, as items are being added to a queue, the first item is being pushed to the top. Thus, the last added item is at the bottom of queue, which is different from that of stack (as aforementioned, the last item to be added locates at the top of the stack). The second function is dequeue() that serves to remove the first and topmost item from the queue. Lastly, similar to stack, queue also has a method called isEmpty() that returns True if queue contains no data, and false otherwise. Moreover, queue also has the operation size() that returns the number of items stored in it. The real life applications of queue are people lining up to board an airplane or buy tickets from a ticket booth. Lastly, its example calls can be viewed by clicking the link: http://interactivepython.org/runestone/static/pythonds/BasicDS/queues.html The third and last ADT I learned is tree. To begin, similar to stack and queue, tree also stores data. However, it stores data in a hierarchical order. Each item/object is called a node, and we refer to the bottom nodes that happen to branch out the top node as the children of the top node. Furthermore, nodes without any children is referred simply as leaves, whereas, the top most node is called the root. Functions for trees that I was taught in class and tutorials included determining the height of the tree, the number of children, etc,. So far, the class only looked at binary trees (trees where a node only has a maximum of 2 children, called the left and right subtree) in great detail. To sum up, the ADT tree is a real world tree flipped upside down. In my CSC148’s assignment two, I will be combining recursion with tree to assess every possible outcomes of the Tippy Game, and then return the best strategy for the player to win the game. (This idea is required in the class called StrategyMinimax).In conclusion, throughout these 7 weeks of class, I learned about abstract data types and its three specific examples — stack, queue and tree. Up until now, the most difficult ADT I learned is tree. However, I have no problem understanding its structure and implementation, since my quizzes about count_leaves is perfect, and I was able to complete the labs regarding trees in a efficient and speedy manner. One thing about tree that I enjoy is its frequent application of recursion. This is because I find writing recursions challenging yet satisfying at the same time after reaching a solution. Hence I was elated to find out that I will be combining both tree and recursion in Assignment 2’s StrategyMinimax. So far, my group has completed the codes for TippyGameState and TippyMove, and we will be writing StrategyMinimax tomorrow. Hopefully, my group can finish the GameState by Monday. Lastly, the advantages of using abstract data types is that ADTs can be reused in future programs. Further, their implementations can be easily modified without having to make troublesome changes to the program that uses the ADTs.
No comments:
Post a Comment