Abstract data types are the interfaces that tells us what are the possible commands or things we can do in a data structure. There are many situations wherein we would employ ADTs. One example would be the “undo-redo” commands we have in most applications we have in our computers. The application would record or the actions, commands or the things we do in a PC and log that somewhere. When we do an error and want to undo what we recently did, the PC would go to that last action we did. This is an example of a stack ADT. We do a “push” operation every time we do an action and that is saved in a log file, and every time we undo, we do a “pop” operation.
Another real-life example of ADTs is when we go shopping and we go in a queue to purchase what we buy. The line goes in a first-in, first-out. The first in the queue is the first to leave, the last in the queue is the last to leave.
I would use ADTs in situations wherein I want to build commands for a particular machine or application. It’s useful because it makes things on the surface easy, while all the work, the behavior of the code and the like are hidden beneath that interface. Another example would be making a game, with characters moving by the pressing the keys on the keyboard, the movement is coded within the game. What we see during gameplay are sets of implementations that is used to be the game as it is. Though we do not really see this implementations, but the interfaces.
The difficulty I had in writing the tests is creating the interface themselves. With the instructions I had that was in C++ (which I never learned), I had to carefully translate it into python and understand it. I thought of what I could do to create those interface. I searched in the internet and look for “abstract data types implementation in python” and other similar searches and I found out that I had to use classes. I’m not really familiar with object-oriented programming yet, so I had to self-study more of it. Fortunately, when I got lost and I had questions, I had some of my friends to go to (They were big help!). So, when I understood the concept of classes, I realized I could create the interfaces without them, but my code would be so-so messy. I had to go back and understand further what each of the ADTs’ operation and create their interface. After weeks, I did it. The testing part wasn’t that hard. I just to test the interfaces I had created.
We need to write interfaces because of simplification. We need to “translate” the low-level implementation we have on the code into something more high-level and more understandable. The interface tells us what our implementation in a data structure is capable of doing, whatever it is. For example, a calculator. The interface is the is buttons we have in it. However, the magic is done inside, where all the code or should we say the implementation is. With interfaces, the lay person could understand directly what a machine does.
The three ADTs I have chosen to test are Queue, Stack and Deque.
Queue
Below is the code I used and the terminal for the test.
class Queue:
def __init__(self):
self.items = []
def add(self, item):
self.items.append(item)
def remove(self):
if (self.size() == 0):
raise "Nothing to remove since queue is empty!"
else:
return self.items.pop(0)
def display(self):
print(self.items)
def size(self):
return len(self.items)Test
# test for Queue
print("Testing for Queue")
queue = adts.Queue()
# test for adding in a queue
print("--- Adding in a queue ---")
queue.add(5)
queue.display()
queue.add(8)
queue.display()
queue.add(3)
queue.display()
# test for removing in a queue
print("--- Removing in a queue ---")
queue.remove()
queue.display()
queue.remove()
queue.display()
queue.remove()
queue.display()
# test for removing from an empty queue
print("--- Removing from an empty queue ---")
queue.remove()
queue.display()
Stack
Below is the code I used and the terminal for the test.
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if (self.size() == 0):
raise "Nothing to remove since queue is empty!"
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if (self.size() == 0):
raise "Nothing to remove since queue is empty!"
else:
return self.items.pop()
def display(self):
print(self.items)
def size(self):
return len(self.items)
Test
# test for Stack
print("Testing for Stack")
stack = adts.Stack()
# test for pushing in a stack
print("--- Pushing in a stack ---")
stack.push(5)
stack.display()
stack.push(10)
stack.push(15)
stack.display()
# test for popping in a stack
print("--- Popping in a stack ---")
stack.pop()
stack.display()
stack.pop()
stack.display()
stack.pop()
stack.display()
# test for popping from an empty stack
print("--- Popping from an empty stack ---")
stack.pop()
Deque
Below is the code I used and the terminal for the test.
class Deque:
def __init__(self):
self.items = []
def addFirst(self, item):
self.items = [item] + self.items
def removeFirst(self):
assert len(self.items) == 0, "Nothing to remove since queue is empty!"
return self.items.pop(0)
def addLast(self, item):
self.items = self.items + [item]
def removeLast(self):
assert len(self.items) == 0, "Nothing to remove since queue is empty!"
return self.items.pop()
def display(self):
print(self.items)
def size(self):
return len(self.items)
Final Code Used:
For the interfaces:
class Queue:
def __init__(self):
self.items = []
def add(self, item):
self.items.append(item)
def remove(self):
if (self.size() == 0):
raise "Nothing to remove since queue is empty!"
else:
return self.items.pop(0)
def display(self):
print(self.items)
def size(self):
return len(self.items)
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if (self.size() == 0):
raise "Nothing to remove since stack is empty!"
else:
return self.items.pop()
def display(self):
print(self.items)
def size(self):
return len(self.items)
class Deque:
def __init__(self):
self.items = []
def addFirst(self, item):
self.items = [item] + self.items
def removeFirst(self):
if (self.size() == 0):
raise "Nothing to remove since the sequence is empty!"
else:
return self.items.pop(0)
def addLast(self, item):
self.items = self.items + [item]
def removeLast(self):
if (self.size() == 0):
raise "Nothing to remove since the sequence is empty!"
else:
return self.items.pop()
def display(self):
print(self.items)
def size(self):
return len(self.items)
class List:
def __init__(self):
self.elements = []
def size(self):
return len(self.elements)
def get(self, index):
if ((self.size()-1) < index):
raise "Your chosen index does not exist. It's out of bounds."
else:
for i in range(self.size()):
if i == index:
return self.elements[i]
def set(self, index, item):
for i in range(self.size()):
if i == index:
self.elements[i] = item
def add(self, index, item):
self.elements.insert(index, item)
def remove(self, index):
if (self.size() == 0):
raise "Nothing to remove since queue is empty!"
else:
return self.elements.pop(index)
def display(self):
print(self.elements)
class USet:
def __init__(self):
self.elements = set()
def size(self):
return len(self.elements)
def add(self, item):
self.elements.add(item)
def remove(self, item):
self.elements.remove(item)
def find(self, item):
for i in self.elements:
if i == item:
return item
return None
def display(self):
print(self.elements)
class SSet:
def __init__(self):
self.elements = set()
def size(self):
return len(self.elements)
def add(self, item):
self.elements.add(item)
def remove(self, item):
self.elements.remove(item)
def find(self, item):
for i in self.elements:
if i == item:
return item
return None
def display(self):
print(self.elements)
For the tests:
import adts
# test for Queue
print("Testing for Queue")
queue = adts.Queue()
# test for adding in a queue
print("--- Adding in a queue ---")
queue.add(5)
queue.display()
queue.add(8)
queue.display()
queue.add(3)
queue.display()
# test for removing in a queue
print("--- Removing in a queue ---")
queue.remove()
queue.display()
queue.remove()
queue.display()
queue.remove()
queue.display()
# test for removing from an empty queue
print("--- Removing from an empty queue ---")
# queue.remove()
# queue.display()
print("\n")
# test for Stack
print("Testing for Stack")
stack = adts.Stack()
# test for pushing in a stack
print("--- Pushing in a stack ---")
stack.push(5)
stack.display()
stack.push(10)
stack.push(15)
stack.display()
# test for popping in a stack
print("--- Popping in a stack ---")
stack.pop()
stack.display()
stack.pop()
stack.display()
stack.pop()
stack.display()
# test for popping from an empty stack
print("--- Popping from an empty stack ---")
# stack.pop()
print("\n")
# test for Deque
print("Testing for Deque")
my_deque = adts.Deque()
# test for adding first in a sequence
print("--- Adding first in a sequence ---")
my_deque.addFirst(5)
my_deque.display()
my_deque.addFirst(2)
my_deque.display()
my_deque.addFirst(-13)
my_deque.display()
# test for adding last in a sequence
print("--- Adding last in a sequence ---")
my_deque.addLast(9)
my_deque.display()
my_deque.addLast(11)
my_deque.display()
my_deque.addLast(17)
my_deque.display()
# test for removing first in a sequence
print("--- Removing first in a sequence ---")
my_deque.removeFirst()
my_deque.display()
# test for removing last in a sequence
print("--- Removing last in a sequence ---")
my_deque.removeLast()
my_deque.display()
# test for removing elements from a sequence until it is empty
print("--- Removing elements from a sequence until it is empty ---")
my_deque.removeLast()
my_deque.display()
my_deque.removeFirst()
my_deque.display()
my_deque.removeLast()
my_deque.display()
my_deque.removeFirst()
my_deque.display()
# test for removing elements from an empty sequence
print("--- Removing elements from an empty sequence ---")
my_deque.removeFirst()
Chav's Blog 