Lecture Notes onStacks15-122: Principles of Imperative ComputationFrank PfenningLecture 10February 10, 20111 IntroductionIn this lecture we introduce another commonly used data structure calleda stack. We practice again writing an interface, and then implementing theinterface using linked lists as for queues. We also discuss how to checkwhether a linked list is circular or not.2 Stack InterfaceStacks are similar to queues in that we can insert and remove items. But weremove them from the same end that we add them, which makes stacks aLIFO (Last In First Out) data structure.Here is our interface/* type elem must be defined */typedef struct stack* stack;bool stack_empty(stack S); /* O(1) */stack stack_new(); /* O(1) */void push(stack S, elem e); /* O(1) */elem pop(stack S); /* O(1) */We want the creation of a new (empty) stack as well as pushing and pop-ping an item all to be constant-time operations.We are being slightly more abstract here than in the case of queues inthat we do not write, in this file, what type the elements of the stack haveLECTURE NOTES FEBRUARY 10, 2011Stacks L10.2to 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. Wesay that the implementation is generic or polymorphic in the type of theelements. Unfortunately, neither C nor C0 provide a good way to enforcethis in the language and we have to rely on programmer discipline.3 Stack ImplementationThe idea is to reuse linked lists. But since all operations work on one endof the list, we do not need two pointers but just one which we call top. Atypical stack then has the following form:3" 1"2"top"data" next"bo.om"X" X"Note that the end of the linked list is marked with the special NULL pointerthat 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 thelist starting at top ends in bottom, which is the same as checking that thisis a list segment (as introduced in the last lecture).bool is_stack (stack S) {LECTURE NOTES FEBRUARY 10, 2011Stacks L10.3if (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 toNULL 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 datafield and then its next field to the current top of the stack. Finally, we needto update the top field of the stack to point to the new list item. While thisis simple, it is still a good idea to draw a diagram. We go from3" 1"2"top"data" next"bo.om"X" X"LECTURE NOTES FEBRUARY 10, 2011Stacks L10.4to3" 1"2"top"data" next"4"X" X"bo0om"data" next"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 toppointer to follow the next pointer from the top of the stack. As in the caseof dequeuing an element from the previous lecture, the list item that pre-viously constituted the top of the stack will no longer be accessible and begarbage collected as needed by the runtime system. We go from3" 1"2"top"data" next"bo.om"X" X"LECTURE NOTES FEBRUARY 10, 2011Stacks L10.5to3" 1"2"top"data" next"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 simpleand pervasive data structure.4 Detecting CircularityChecking whether a stack or a queue satisify their data structure invari-ant raises an interesting question: what if, somehow, we created a list thatLECTURE NOTES FEBRUARY 10, 2011Stacks L10.6contains a cycle, such as1" 3"2" 4"start"data" next"5"6"In that case, following next pointers until we reach NULL actually neverterminates. The program for checking a segment will get into an infiniteloop.In general, contracts should terminate and have no effects. It is marginallyacceptable if a contract diverges, because it will not incorrectly claim thatthe contract it satisfied, but it would clearly be better if it explicitly rejecteda circular list. But how do we check that? Before you read on, you shouldseriously think about the problem, like our class did in lecture.LECTURE NOTES FEBRUARY 10, 2011Stacks L10.7Here 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 startpointer. Then when we advance p we run through an auxiliary loop tocheck if the next element is already in the list. The code would be some-thing likebool 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.LECTURE NOTES FEBRUARY 10, 2011Stacks L10.8The idea for a more efficient solution is to create two pointers, let’s namethem 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. Ifthe slower one t ever gets into a loop, the other pointer h will overtake itfrom behind. And this is the only way that this is possible. Let’s try it onour list. We show the state of t and h on every iteration.1" 3"2" 4"data" next"5"6"t" h"1" 3"2" 4"data" next"5"6"t"h"1" 3"2" 4"data" next"5"6"t"h"LECTURE NOTES FEBRUARY 10, 2011Stacks L10.91" 3"2" 4"data" next"5"6"t"h"In code:bool is_circular(list l){ if (l == NULL) return false;{ list t = l; // tortoiselist h = l->next; // harewhile (t != h)//@loop_invariant