Stacks and QueuesDecision Time: Exam Weighting ProposalADTs as Software ToolsDocumentation of the LibrariesDocumentation for the Stack ClassThe Stack MetaphorFunction Calls and Stack FramesMethods in the Stack<x> ClassExercise: Stack ProcessingThe LaIR QueueMethods in the Queue<x> ClassExercise: Queue Test ProgramMethods in the Map<x> ClassMethods in the Lexicon ClassThe EndStacks and QueuesEric RobertsCS 106BApril 10, 2009Decision Time: Exam Weighting Proposal•For many years, I’ve been thinking about the possibility of reducing the weight of the final if we can do something collectively about the Honor Code problem.•Here is my proposal: The weight of the final will be15% + 5% for each Honor Code case filed this quarterThe weight assigned to the homework will be whatever is left after the announced weights are assigned to the various other components, subject to a minimum of 15%.•Thus, if no Honor Code cases come up this quarter, the final will count for 15%, which is exactly the same as the midterm. The homework would count for 60%.•If we file three Honor Code cases (as we did last quarter), the final will count for 30% and the homework for 45%. And so on . . .ADTs as Software Tools•Over the relatively short history of software development, one of the clear trends is the increasing power of the tools available to you as a programmer.•One of the best explanations of the importance of tools is the book Software Tools by Brian Kernighan and P. J. Plauger. Even though it was published in 1976, its value and relevance have not diminished over time.•The primary theme of the book is that the best way to extend your reach in programming is to build on the tools of others.Documentation of the LibrariesDocumentation for the Stack ClassThe Stack Metaphor•A stack is a data structure in which the elements are accessible only in a last-in/first-out order.•The fundamental operations on a stack are push, which adds a new value to the top of the stack, and pop, which removes and returns the top value.•One of the most common metaphors for the stack concept is a spring-loaded storage tray for dishes. Adding a new dish to the stack pushes any previous dishes downward. Taking the top dish away allows the dishes to pop back up.Function Calls and Stack Frames skip simulationFactEnter n: 33! = 6int main() { cout << "Enter n: "; int n = GetInteger(); cout << n << "! = " << Fact(n) << endl; return 0;}n36int Fact(int n) { if (n == 0) { return 1; } else { return n * Fact(n - 1); }}n32int Fact(int n) { if (n == 0) { return 1; } else { return n * Fact(n - 1); }}n26int Fact(int n) { if (n == 0) { return 1; } else { return n * Fact(n - 1); }}n11int Fact(int n) { if (n == 0) { return 1; } else { return n * Fact(n - 1); }}n0Local variables and return addresses are stored in a stack.Methods in the Stack<x> Classstack.size()Returns the number of values pushed onto the stack.stack.isEmpty()Returns true if the stack is empty. stack.push(value)Pushes a new value onto the stack.stack.pop()Removes and returns the top value from the stack.stack.peek()Returns the top value from the stack without removing it.stack.clear()Removes all values from the stack.Exercise: Stack ProcessingOperatorMatchingEnter string: { s = 2 * (a[2] + 3); x = (1 + (2)); }Brackets are properly nestedEnter string: (a[2] + b[3)Brackets are incorrectEnter string:Write a C++ program that checks whether the bracketing operators (parentheses, brackets, and curly braces) in a string are properly matched. As an example of proper matching, consider the string{ s = 2 * (a[2] + 3); x = (1 + (2)); }If you go through the string carefully, you discover that all the bracketing operators are correctly nested, with each open parenthesis matched by a close parenthesis, each open bracket matched by a close bracket, and so on.The LaIR QueueMethods in the Queue<x> Classqueue.size()Returns the number of values in the queue.queue.isEmpty()Returns true if the queue is empty. queue.enqueue(value)Adds a new value to the end of the queue (which is often called its tail).queue.dequeue()Removes and returns the value at the front of the queue (which is called its head).queue.peek()Returns the value at the head of the queue without removing it.queue.clear()Removes all values from the queue.Exercise: Queue Test ProgramWrite a simple simulation of a queue application in which the user can either enter a name that is entered into a queue or the command serve, which dequeues and displays the first name. Extend the program to support quit and list commands.QueueTestProgram> FredFred has been added to the queue> DaveDave has been added to the queue> listThe queue contains: Fred Dave> serveFred has been helped> listThe queue contains: Dave> serveDave has been helpedMethods in the Map<x> Classmap.size()Returns the number of key/value pairs in the map.map.isEmpty()Returns true if the map is empty. map.put(key, value) or map[key] = value;Makes an association between key and value, discarding any existing one.map.get(key) or map[key]Returns the most recent value associated with key.map.containsKey(key)Returns true if there is a value associated with key.map.remove(key)Removes key from the map along with its associated value, if any.map.clear()Removes all key/value pairs from the map.Methods in the Lexicon Classlexicon.size()Returns the number of key/value pairs in the lexicon.lexicon.isEmpty()Returns true if the lexicon is empty. lexicon.add(word)Adds true to the lexicon, always in lowercase.lexicon.addWordsFromFile(filename)Adds all the words in the specified file to the lexicon.lexicon.containsWord(word)Returns true if the lexicon contains the specified word.lexicon.containsPrefix(prefix)Returns true if the lexicon contains any word beginning with prefix.lexicon.clear()Removes all words from the lexicon.The