A stack is like a stack of papers.
* You can put new things on top of it
* You can get at the top thing on the stack.
Often called LIFO -- Last In First Out (Reverses order)
* Like a stack of trays in a cafeteria
* Bottom one gets moldy
A stack is a data structure supporting the following operations:
(make-stack) ---------- Makes a new empty stack
(insert thing stack) -- Returns a new stack with thing on top of `stack'.
** DOES NOT CHANGE THE ORIGINAL! Not a `!' **
(delete stack) ------- Returns a stack like `stack', but without
its top element.
(top stack) ----------- Returns the top element of the stack.
(empty? stack) -------- Is there anything on the stack?
They obey the contract:
(top (insert thing stack)) = thing
(delete (insert thing stack)) = stack
(empty? (make-stack)) = #t
(empty? (insert thing stack)) = #f
So, we can implement a stack with lists:
insert = cons
delete = head
top = tail
empty? = null?
This implementation is quite efficient:
* The operations all take O(1) time, independent of the size of the
stack.
NOTE: This implementation does NOT CHANGE list structures, it just creates new
ones to make a new stack after insert or delete operation.
>> This is all easy and standard and you know it all already. <<
----------------------------------------------------------------------
A queue has the same operation names as a stack, but they do slightly
different things:
* It's like a line of people at a cafeteria
- Waiting to pick trays off the stack?
* You can join at the back end of the line,
* But you leave at the front end.
* FIFO -- first in first out (maintains order)
- Nobody gets moldy
- Everything stays in the same order.
(make-queue) -----------
(insert thing queue) --- puts a thing at the tail end of the queue.
(delete queue) --------- deletes the head of the queue
(headq queue) ----------- returns the head of the queue
(empty? queue) ---------
Contract:
Let I be the number of insertions,
D be the number of deletions so far,
We must have I >= D at all times,
Let x_J be the J'th element inserted into the queue.
[We can be mathematicians, and start at 1, or computer scientists
and start at 0. Today, we'll be mathematicians.]
(headq queue) = x_(D+1) if I > D
= undefined if I = D
(empty? queue) = (= I D)
For example, suppose we insert a b c d e f in that order.
^ ^
head tail
Now:
I = 6, D = 0
(headq queue) = x_(D+1) = x_1 = a
Now, let's do a delete
a b c d e f
^ ^
head tail
I = 6, D = 1
(headq queue) = x_(D+1) = x_2 = b, which is right.
We could implement a queue as a list with the head -- oldest element
-- at the front.
headq = head
delete = tail
empty? = null?
but this makes insert be:
(method ((thing <object>) (q <list>)) (append q (list thing)))
which is O(n) time. We have to walk all the way down the list. This
is expensive.
We could also do it backwards -- the head at the last element -- but
that wouldn't help either: insert would be O(1), but delete and head
would be O(n).
We would like to have *both* the head *and* the tail available in constant
time.
Note: ths implementation of queues does NOT CHANGE list structures, it creates
a new list structure for each delete or insert operation.
----------------------------------------------------------------------
The tool we'll use is set!, but we will use it change portions of a list
structure instead of changing a value in a location as we have used it so
far.
-- Mutable Data Structures
Keep pointers to both ends of the list.
* When you insert something, add it to the list
* When you delete something, physically remove it from the list
NOW we're going to CHANGE EXISTING LIST STRUCTURES!
REMEMBER:
cons, head, and tail are NOT mutators.
* They *don't* change any data structures
* Though cons *does* allocate new memory.
* If you were thinking of them as changing things, STOP!
- It's WRONG!
- It will get you in TROUBLE
Just to remind you:
(define (x <list>) '(1 2 3))
(define (y <list>) (tail x))
x is STILL (1 2 3)
y is (2 3) the tail of that list.
List MUTATION or CHANGE is done using set! applied to the appropriate
part of a list structure, it has the effect of changing the structure.
(set! (head l) x) changes the head of list l to the element x
(set! (tail l) l') changes the tail of list l to the list l'
x is an element (it may be a list, but that list is then an element of l)
l' is a list, it is the rest of the new list that replaces l
Example:
(define (x <list>) (list 1 2 3))
;; We use list because it always makes new list structure.
;; '(1 2 3) isn't guaranteed to.
(define (y <list>) (cons 4 x))
>>> Draw box-and-pointer diagrams for x and y.
>>> Note that the tail of y is the same structure as x
(set! (head x) 10)
>>> Change head of x to 10
Now, x is (10 2 3).
ALSO y is (4 10 2 3)!
** x and y *share structure*
- Changing one of them can change the other one as well.
- This is MASSIVELY confusing.
NOTE: (set! x 10) just changes x, *not* y, because it changes the
value stored at x, not part of the structure stored at x (that
structure being what is shared with y). [!?!]
SO: as with all uses of operations that change things, such as set!,
we want to "package up" the use of change, keep there from being
unintended shared structures.
----------------------------------------------------------------------
Now, here's how to implement a queue with constant time insertions and
deletions.
Use a list structure with pointers to the beginning and end of the
list.
(define <queue> <list>)
Keep pointers to the beginning and the end of the list:
>>> Draw the box diagram of (1 2 3),
>>> q is a box whose head points to the 1-cell, tail to the 3-cell.
We'll read from the front of the list, and add to the rear.
(define (empty-queue? <method>)
(method ((q <queue>))
(null? (head q))))
(define (make-queue <method>)
(method ()
(cons '() '())))
(define (headq <method>)
(method ((q <queue>))
(if (empty-queue? q)
(error "Head of empty queue")
(head (head q)))))
Note: (head q) gives the front of the list, (caar q) gives the first
element of queue
(define (insert <method>)
(method ((x <object>) (q <queue>))
(bind (((new <list>)
(cons x '())))
(cond
((empty-queue? q)
(set! (head q) new)
(set! (tail q) new)
q)
(else:
;; make the tail of the last cell point to new
(set! (tail (tail q)) new)
;; make (tail q) be new
(set! (tail q) new)
q)))))
In the empty case, we need to make sure that the head and tail of q
point to the *same* cons cell, because there is just one thing in the
queue, the new element.
In the non-empty case, add the new element at the rear.
(define (delete <method>)
(method ((q <queue>))
(cond
((empty-queue? q)
(error "Cant delete from empty queue."))
(else:
;; Make (head q) be (tail (head q))
(set! (head q) (tail (head q)))
q))))
----------------------------------------------------------------------
(define (fred <queue>) (make-queue))
fred --> (())
>>> Draw b&p diagram.
(insert 1 foo)
>>> change B&P diagrams on the board.
>>> B&P diagrams: both head and tail of q point to a cons cell (1 . nil)
(headq foo)
---> 1
(insert 2 fred)
>>> Change B&P diagrams on the board.
>>>
(headq fred)
--> 1 still
(delete fred)
>>> Change B&P's so that both the head and tail of fred point to the (2 .
>>> nil)
Note: the remains, the cons cell (1 . [pointer-to-(2.nil)] ) are
INACCESSIBLE. Nobody has a pointer to it. It can't be reached by
anything the program does.
It is GARBAGE
It will eventually get GARBAGE COLLECTED, and its space recycled.
More on this later in the term...
----------------------------------------------------------------------
Summary:
* Stacks - LIFO,
* Queues - FIFO
O(1) implementations of basic operations.
Our O(1) queue implementation uses *mutation* to do this.
----------------------------------------------------------------------
you can implement queues functionally with amortized cost O(1) on both insert and remove. The idea is to represent the queue as two lists:
(define-class <queue> (<object>)
(front <list>) (rear <list>))
To insert into the queue, you cons onto the rear list. To remove from the queue, you take the head of the front list.
Of course, if the front list is empty, then you have to reverse the rear list and make it the front (resetting the rear to be null.)
; inserts x into the queue q
(define insert (method ((x <object>) (q <queue>))
(make <queue> front: (front q)
rear: (cons x (rear q))))
; removes the first element of the queue, returning
; the element and the new queue-loops forever if
; the queue is empty...
(define remove (method ((q <queue>))
(if (null? (front q)
(remove (make <queue> front:(reverse (rear q))
rear:'()))
(pair (head (front q))
(make <queue> front: (tail (front q))
rear: (rear q)))))
Any sequence of n inserts and removes takes time O(n)
(on average). Why? Inserts obviously take O(1) time. If we perform n removes, then at most one of the removes will involve a reverse which takes O(n) time. The other removes take constant time. So, the sum of the costs for doing n removes is c1*n + c2*n = O(n).
Note that I'm assuming you use the queue in a single-threaded fashion. That is, the sequence of inserts and removes is of the form:
(bind ((q1 (insert x1 empty-queue))
(q2 (insert x2 q1))
(q3 (insert x3 q2))
...
(qn (insert xn qn)
(pn (remove qn)) ; reverse happens here
(pn-1 (remove (tail pn)))
(pn-2 (remove (tail pn-1)))
...
(p2 (remove (tail p3)))
(p1 (remove (tail p2)))
Notice that no queue is used more than once (you always use the queue that is returned from insert or remove in the next expression.)