Lecture Notes on Stacks 15 122 Principles of Imperative Computation Frank Pfenning Lecture 10 February 10 2011 1 Introduction In this lecture we introduce another commonly used data structure called a stack We practice again writing an interface and then implementing the interface using linked lists as for queues We also discuss how to check whether a linked list is circular or not 2 Stack Interface Stacks are similar to queues in that we can insert and remove items But we remove them from the same end that we add them which makes stacks a LIFO Last In First Out data structure Here is our interface type elem must be defined typedef struct stack stack bool stack empty stack S stack stack new void push stack S elem e elem pop stack S O 1 O 1 O 1 O 1 We want the creation of a new empty stack as well as pushing and popping an item all to be constant time operations We are being slightly more abstract here than in the case of queues in that we do not write in this file what type the elements of the stack have L ECTURE N OTES F EBRUARY 10 2011 Stacks L10 2 to be Instead we assume that at the top of the file or before this file is read we have already defined a type elem for the type of stack elements We say that the implementation is generic or polymorphic in the type of the elements Unfortunately neither C nor C0 provide a good way to enforce this in the language and we have to rely on programmer discipline 3 Stack Implementation The idea is to reuse linked lists But since all operations work on one end of the list we do not need two pointers but just one which we call top A typical stack then has the following form data next 3 top 2 1 X X bo om Note that the end of the linked list is marked with the special NULL pointer that cannot be dereferenced We define struct list elem data struct list next typedef struct list list struct stack list top list bottom To test if some structure is a valid stack we only need to check that the list starting at top ends in bottom which is the same as checking that this is a list segment as introduced in the last lecture bool is stack stack S L ECTURE N OTES F EBRUARY 10 2011 Stacks L10 3 if S NULL return false if S top NULL S bottom NULL return false return is segment S top S bottom To check if the stack is empty we only need to verify that top is NULL bool stack empty stack S requires is stack S return S top S bottom Creating a new stack is very simple since we only need to set top to NULL after allocating it stack stack new ensures is stack result ensures stack empty result stack S alloc struct stack list l alloc struct list does not need to be initialized S top l S bottom l return S To push an element onto the stack we create a new list item set its data field and then its next field to the current top of the stack Finally we need to update the top field of the stack to point to the new list item While this is simple it is still a good idea to draw a diagram We go from data next 3 top L ECTURE N OTES 2 1 X X bo om F EBRUARY 10 2011 Stacks L10 4 to data next data 4 next 3 top 2 1 X X bo0om In code void push stack S elem e requires is stack S ensures is stack S list l alloc struct list l data e l next S top S top l Finally to pop an element from the stack we just have to move the top pointer to follow the next pointer from the top of the stack As in the case of dequeuing an element from the previous lecture the list item that previously constituted the top of the stack will no longer be accessible and be garbage collected as needed by the runtime system We go from data next 3 top L ECTURE N OTES 2 1 X X bo om F EBRUARY 10 2011 Stacks L10 5 to data next 3 top 2 1 X X bo om In code elem pop stack S requires is stack S requires stack empty S ensures is stack S assert stack empty S elem e S top data S top S top next return e This completes the implementation of stacks which are a very simple and pervasive data structure 4 Detecting Circularity Checking whether a stack or a queue satisify their data structure invariant raises an interesting question what if somehow we created a list that L ECTURE N OTES F EBRUARY 10 2011 Stacks L10 6 contains a cycle such as data 1 next 2 3 4 6 5 start In that case following next pointers until we reach NULL actually never terminates The program for checking a segment will get into an infinite loop In general contracts should terminate and have no effects It is marginally acceptable if a contract diverges because it will not incorrectly claim that the contract it satisfied but it would clearly be better if it explicitly rejected a circular list But how do we check that Before you read on you should seriously think about the problem like our class did in lecture L ECTURE N OTES F EBRUARY 10 2011 Stacks L10 7 Here is the original is segment predicate bool is segment list start list end list p start while p end if p NULL return false p p next return true One the simplest solutions proposed in class keeps a copy of the start pointer Then when we advance p we run through an auxiliary loop to check if the next element is already in the list The code would be something like bool is segment list start list end list p start while p end if p NULL return false list q start while q p if q p next return false circular q q next p p next return true Unfortunately this solution requires O n2 time for a list with n elements whether it is circular or not Again consider if you can find a better solution before reading on L ECTURE N OTES F EBRUARY 10 2011 Stacks L10 8 The idea for a more efficient solution is to create two pointers let s name them t and h t traverses the list like the pointer p before in single steps h on the other hand skips two elements ahead for every step taken by p If the slower one t ever gets into a loop the other pointer h will overtake it from behind And this is the only way that this is possible Let s try it on our list We show the state of t and h on …