Lecture 9 Stacks and Queues 15 122 Principles of Imperative Computation Spring 2023 Frank Pfenning Andr Platzer Rob Simmons In this lecture we introduce queues and stacks as data structures e g for managing tasks They follow similar principles of organizing the data Each provides simple functions for adding and removing elements But they differ in terms of the order in which the elements are removed They can be implemented easily as an abstract data type in C0 like the abstract ssa t type of self sorting arrays that we discussed in the previous lec tures Today we will not talk about the implementation of stacks and queues we will implement them in the next lecture Relating this to our learning goals we have Computational Thinking We illustrate the power of abstraction by con sidering new data structures from the client side Algorithms and Data Structures Queues and stacks are two important data structures to understand Programming Use and design of interfaces 1 The Stack Interface Stacks are data structures that allow us to insert and remove items They operate like a stack of papers or books on our desk we add new things to the top of the stack to make the stack bigger and remove items from the top as well to make the stack smaller This makes stacks a LIFO Last In First Out data structure the data we have put in last is what we will get out rst Before we consider the implementation of a data structure it is helpful to consider the interface We then program against the speci ed interface Based on the description above we require the following functions typedef stack t LECTURE NOTES Carnegie Mellon University 2023 Lecture 9 Stacks and Queues bool stack empty stack t S requires S NULL O 1 check if stack empty 2 stack t stack new O 1 create new empty stack ensures result NULL ensures stack empty result void push stack t S string x O 1 add item on top of stack requires S NULL ensures stack empty S string pop stack t S O 1 remove item from top requires S NULL requires stack empty S Like ssa t the abstract type stack t is representing a mutable data struc ture where pushing and popping modi es the contents of the stack There fore we will again be explicit in the interface that stacks are pointers to allocated memory though we won t be explicit about what they point to We want the creation of a new empty stack as well as pushing and popping an item all to be constant time operations as indicated by O 1 Furthermore pop is only possible on non empty stacks This is a funda mental aspect of the interface to a stack that a client can only read data from a non empty stack So we include this as a requires contract in the interface One thing to observe is that there s nothing special about the string type here It would be nice to have a data structure that was generic and able to work with strings integers arrays and so on but we will discuss that possibility later 2 Using the Stack Interface We play through some simple examples to illustrate the idea of a stack and how to use the interface above We write a stack as x1 x2 xn where x1 is the bottom of the stack and xn is the top of the stack We push elements on the top and also pop them from the top If we re feeling artis tic we can draw stacks with arrows to emphasize that we re pushing and popping from the top Lecture 9 Stacks and Queues 3 Here is a more complex example showing the effect of several steps on the state of assignable variables and allocated memory where the stack data structure resides Remember that we think of the assignable S like a pointer or an array it is not literally an arrow but a number representing the address of the in memory representation of the stack 3 Abstraction An important point about formulating a precise interface to a data structure like a stack is to achieve abstraction This means that as a client of the data structure we can only use the functions in the interface In particular we are not permitted to use or even know about details of the implementation of stacks Let s consider an example of a client side program We would like to examine the element at the top of the stack without removing it from the stack Such a function would have the declaration string peek stack t S requires S NULL stack empty S If we knew how stacks were implemented we might be able to implement as clients of the stack data structure something like this 1 string peek stack t S 2 requires is stack S stack empty S 3 return S data S top 4 5 Lecture 9 Stacks and Queues 4 However we don t know how stacks are implemented so we cannot do this As clients of the stack data structure we only know about the functions pro vided by the interface However it is possible to implement the peek oper ation correctly without violating the abstraction The idea is that we pop the top element off the stack remember it in a temporary variable and then push it back onto the stack before we return 1 string peek stack t S 2 requires S NULL stack empty S 3 string x pop S push S x return x 4 5 6 7 Depending on the implementation of stacks this might be less ef cient than a library side implementation of peek However as long as push and pop are still a constant time operations peek will still be constant time O 1 4 Computing the Size of a Stack Let s exercise our data structure once more by considering how to imple ment a function that returns the size of a stack using only the interface In the next lecture we ll consider how to do this on the library s side exploit ing the data representation Here s the signature of a client side implementation int stack size stack t S requires S NULL ensures result 0 Lecture 9 Stacks and Queues 5 We encourage you to consider this problem and program it before you read on First we reassure ourselves that it will not be a simple operation We do not have access to the array in fact as the client we cannot know that there is an array so the only thing we can do is pop all the elements off the stack This can be accomplished with a while loop that nishes as soon as the stack is empty 1 int stack size stack t S 2 requires S NULL 3 ensures result 0 4 int count 0 while stack empty S 5 6 7 8 9 10 11 pop S count return count However this function has a big problem in order to compute the size we have to destroy the …