Some of the topics we discussed today are covered in these sections of Problem Solving with Algorithms:
Here are some more notes.
An abstract data type specifies a set of operations that an object may provide. In the next few lectures of this course, we will see various abstract data types including stacks, queues, sets, and dictionaries.
We will see that for most abstract data types there are different possible implementations using various data structures. We'll also see that the big-O running time of operations will often vary between implementations.
A stack is an abstract data type that provides two operations called 'push' and 'pop'. push(x) adds a value x to a stack, and pop() removes the value that was most recently pushed and returns it. This is like a stack of sheets of paper on a desk, where sheets can be added or removed at the top.
In other words, a stack is a last in first out (LIFO) data structure: the last element that was added is the first to be removed.
Often a stack will provide an additional operation is_empty that returns true if it contains no elements.
Before we implement a stack, let's look at how one can be used:
# initially 's' is an empty stack
s.push(4)
s.push(8)
for i in range(1, 6) do
s.push(i)
while not s.is_empty() do
print(pop(s), end = ' ')
print()This code will write
5 4 3 2 1 8 4
An easy way to implement a stack in Python is using a list, i.e. an array:
class ArrayStack:
def __init__(self):
self.a = []
def is_empty(self):
return len(self.a) == 0
def push(self, x):
self.a.append(x)
def pop(self):
assert not self.is_empty(), 'stack is empty'
return self.a.pop()The implementation is straightforward. The list contains all stack elements, with the top of the stack (i.e. the most recently pushed element) at the end of the list.
With this implementation, 'push' will run in O(1) on average, since that is the running time of append(). 'pop' will always run in O(1).
Let's now study a broadly useful data structure that we might alternatively use to implement a stack, namely a linked list. A linked list looks like this:
An element of a linked list is called a node.
A node contains one or more values, plus a pointer to the next node
in the list. The first node of a linked list is called its head.
The last node of a linked list is its tail. The tail always
points to None
(in Python, or its equivalent such as nil in other
languages).
By the way, we will sometimes illustrate a linked list more compactly:
2 → 4 → 7 → None
The two pictures above denote the same structure; the first is simply more detailed.
Note that a Python list is not a linked list! A Python list is an array. :)
Here is a node type for a linked list in Python:
class Node:
def __init__(self, val, next):
self.val = val
self.next = nextWe can build the 3-element linked list pictured above as follows:
>>> r = Node(7, None) >>> q = Node(4, r) >>> p = Node(2, q)
Now p refers
to the head of the list, and q and r refer to successive elements:
Through p, we can get to the values in the list:
>>> p.val 2 >>> p.next.val 4 >>> p.next.next.val 7
We can traverse a linked list using a loop that moves to the next list node on each iteration. Here's a function that takes a pointer to the head of a linked list, and returns its length:
def list_len(head):
n = head
count = 0
while n != None:
n = n.next # move to the next node
count += 1
return count
By modifying the function only slightly, we can write a function that computes the sum of all values in a linked list:
def list_sum(head):
n = head
total = 0
while n != None:
total += n.val
n = n.next # move to the next node
return total
Let's now write a function that takes an integer n and constructs a linked list containing the values from 1 to n. One easy way to do that is to build the list in reverse order, just like when we built a list above with the values 2, 4, and 7. On each step, we will prepend a node to the existing list.
def list_1_to_n():
head = None
for i in range(n, 0, -1): # n, n - 1, ... 1
p = Node(i, head)
head = p
return head
As this function runs, the local variable 'head' points to the beginning of the list that we've built so far. On each loop iteration, the function allocates a new node by calling the Node constructor function. As it does so, it makes the new node point to the existing list, by passing 'head' as the value for the 'next' attribute. After that, it modifies 'head' to point to the newly allocated node.
We can write many more functions that operate on linked lists, performing operations such as inserting nodes, deleting nodes, and so on. To get practice with this, we will solve various linked list exercises in our tutorials.
We
can implement a stack using a linked list. Our
class
LinkedStack will
have an attribute
'head'
that points to the head of the list:
The stack operations are fairly straightforward:
class LinkedStack:
def __init__(self):
self.head = None
def is_empty(self):
return self.head == None
def push(self, x):
n = Node(x, self.head)
self.head = n
def pop(self):
assert self.head != None, 'stack is empty'
x = self.head.val
self.head = self.head.next
return xNotice that the push() method allocates a node n that points to the previous head, then records n as the new list head. In other words, it prepends a new node to the list. This is similar to the activity in the list_1_to_n() function above.
If
we implement a stack using an array (i.e. a Python list), the push
operation will take
O(1) on average but O(N) in the worst case, where N is the current
stack size. Our linked list-based implementation performs
differently: push always runs in O(1) (assuming that
object allocations run in constant time).
Queues are another important abstract data type. A queue provides two operations called 'enqueue' and 'dequeue'. enqueue(x) adds an element to the tail of a queue, and dequeue() removes the element at the head and returns it. A queue is something like people waiting in a line: you must join at the back of the line, and the person at the front of the line is served next.
In other words, queues are a first in first out (FIFO) data structure: the first value added to a queue will be the first one to be removed.
A queue can be used like this:
# initially 'q' is an empty queue q.enqueue(4) q.enqueue(77) q.enqueue(12) print(q.dequeue()) # writes 4 print(q.dequeue()) # writes 77
A naive implementation of a queue in Python will store elements in an array, i.e. a Python list. It might look like this:
class ArrayQueue:
def __init__(self):
self.a = []
def is_empty(self):
return len(self.a) == 0
def enqueue(self, x):
self.a.append(x)
def dequeue(self):
return self.a.pop(0)
With this implementation, is_empty() will run in O(1), and enqueue() will run in O(1) on average. However, dequeue() will run in O(N), because all array elements must shift leftward by one position when the first element is deleted. So this is a poor choice of implementation if N might be large.
We can implement a queue more efficiently using a linked list. To do so, we will keep pointers to both the head (first node) and tail (last node) in the list, which will allow us to enqueue or dequeue elements in O(1):
Here is an implementation:
class LinkedQueue:
def __init__(self):
self.head = self.tail = None
def isEmpty(self):
return self.head == None
def enqueue(self, x):
n = Node(x, None)
if self.head == None:
self.head = self.tail = n
else:
self.tail.next = n
self.tail = n
def dequeue(self):
assert self.head != None, 'queue is empty'
x = self.head.val
self.head = self.head.next
return x