Week10: Abstract Data Type

The thing I found hard is abstract data type, and also the ADT stack. However, I noticed I have not throughly talked about it yet. Thus, I decide to do some review on it.

First of all, we need to understand what is ADT. ADT is an abstract data type, it is defined by a set of operations(what it does), but without saying how they are implemented. Thus it seems abstract, and makes us wonder, if it cannot be implemented, then why it is useful. The fact is we can but we sometimes do not need to come up with methods and give specific implementation of the method at the same time. If the procedure is separated, then the task is simpler and clearer. Also, some well-known ADT can be used frequently by many people, and similarly, an algorithm can be used in many implementations. Next, there are two unfamiliar words distinguish the "idea of operations" and "implementations of operation". The first one is called the provider, the second one is called the implementor. The division of the work accelerates our process in programming. Another word is "interface", which means a set of operations that define an ADT.

One ADT we have talked for a lot of times is Stack. It consists of four operations: 1) __init__; 2) push; 3) pop; 4) is_empty. The implementation of them is called veneer, because it is very easy and using existing methods. One more thing to indicate, stack has LIFO("Last In, First Out") structure.

Here is how stack is implemented.

class Stack: def __init__(self): self.items = [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def is_empty(self): return (self.items == [])

(Source: http://openbookproject.net/thinkcs/python/english3e/stacks.html)

Thanks for reading!!