COP 3540 Data Structures with OOPA Different Kind of StructureAccess (interface)StacksSlide 5PowerPoint PresentationSlide 7Notes:Delimiter MatchingDelimiter Matching – moreDelimiters – the AlgorithmSlide 12Slide 13Slide 14Stack as a Conceptual AidQueuesQueues - terminologyQueues – moreSlide 19Slide 20Efficiency of QueuesQuestions?1/ 23COP 3540 Data Structures with OOP Chapter 4Stacks and Queues2/ 23A Different Kind of StructureStacks, queues, and priority queues – different kinds of storage structures.Different data structures have different sets of problems that they are most suited to representing.Consider Arrays – as a data storage structure:very useful.easy to insert into, delete from, and search for specific items.3/ 23Access (interface)Arrays: theoretically, access is immediate via index or by searching through cells sequentially.If ordered, can access more quickly via binary searchOnly one item can be accessed. ‘That’ is the interface.’In abstract data structures (stacks, queues, trees, priority queues), real access (that is, how do we get to it…) is:defined a bit differently and is controlled by an interface that is normally not visible to the user.4/ 23StacksStacks - access to only one item at a time.Think of a stack of dishes.It is a LIFO data structure.Extremely useful tool in programming:Evaluate parenthesized expressions, Evaluate arithmetic expressions even with lots of parentheses, Traversing binary trees, Searching vertices of a graph, and much more. Consider stacked-based architecture and calling sequences / return addresses….5/ 23StacksStacks are conceptual (logical), abstract structures.We can envision them.Really no such thing as a real stack! But we are interested in how we can implement the logical structure on a machine. Basic operations – four. Know these!:Push (onto top of stack)Pop (top item off of stack)Stack overflow (stack full) – cannot push! •(normally error condition or special processing needed. Same for underflow…)Stack underflow (stack empty) – cannot pop!Let’s look at Java Code for a Stack6/ 23class StackApp{ public static void main(String[] args) { StackX theStack = new StackX(10); // makes new stack of size 10.//note: argument sent to the Stack object for use by constructor// note: we DO NOT KNOW how the stack actually looks!!!!!// that is, we do NOT know what the underlying data structure looks like!!!!! theStack.push(20); // push items onto stack theStack.push(40); // These are ‘logical’ operations!!! theStack.push(60); (How to evaluate??) theStack.push(80); while( !theStack.isEmpty() ) // until it's empty, delete item from stack { long value = theStack.pop(); // what is author doing here??? System.out.print(value); // display it System.out.print(" "); } // end while System.out.println(""); } // end main()} // end class StackApp7/ 23// stack.java demonstrates stacks Note: I have taken liberties with the ‘{‘ to fit this code on one page.class StackX { private int maxSize; // size of stack array private long[] stackArray; // recall: ‘instance variables’ private int top; // top of stack//-------------------------------------------------------------- public StackX(int s) // constructor // (How can you tell this is the Constructor??) { // ONLY NOW CAN WE SEE STACK IS IMPLEMENTED AS AN ARRAY ! maxSize = s; // set array size // Recall: ‘ local variables’ Where are they known?? stackArray = new long[maxSize]; // Create array; ARRAY IS OF ‘LONGS’ //’long’ is a primitive data structure; how longs are implemented and // accessed are defined in system. No need for separate class for this. top = -1; // no items yet } // end StackX() DISCUSS//-------------------------------------------------------------- public void push(long j) { // put item on top of stack stackArray[++top] = j; // increment top, insert item //  tell me exactly how this works!! } // end push() // How many operators do you see?//-------------------------------------------------------------- public long pop() { // take item from top of stack return stackArray[top--]; // access item, decrement top // tell me exactly how this works!! }// end pop () //recall: What is the ‘other kind’ of variable?????//-------------------------------------------------------------- public long peek() { // peek at top of stack return stackArray[top]; // when we come into this object, the pointer is } // end peek() // pointing to the topmost element.//-------------------------------------------------------------- public boolean isEmpty() { // true if stack is empty return (top == -1); // tell me exactly how this works!! } // end isEmpty()//-------------------------------------------------------------- public boolean isFull() { // true if stack is full //Ah ha! We see (above) that the Stack is ‘implemented’ as return (top == maxSize-1); // an array! But it doesn’t have to be!!!!! }} // end class StackX // Storage structure transparent to client. Good!!! Why???8/ 23Notes:Always check to see if there are items on the stack before popping the stack or if there is room before pushing the stackisFull? isEmpty? Appropriate error routines are up to the developer / userBest approach: in Push() and Pop(), check for isEmpty and isFull within these methods.Regardless, they need to be specified.Go through Reversing a Word routine in book.We will look at Delimiter Matching.9/ 23Delimiter MatchingStacks are used a lot to temporarily store tokens like a char or parts of arithmetic expressions having parentheses in them and later retrieve them when we have a number of delimiters.‘Delimiters’ = normally special characters (e.g. commas, white space, braces, brackets, parentheses, …)They normally set something off or bracket something.Delimiters (but not white spaces) must always ‘balance’ – the first right parenthesis balances the ‘most recent’ unbalanced left parenthesis, etc.10/ 23Delimiter Matching – moreConsider: x = (a+b*(c/d**4-e/(2*a)-5)-14.2/g);How do you and the