chap listsstacksand queues common problem for compilers and text editors is to determine if the parentheses (or other bracketsin string are balanced and properly nested for examplethe string "((())())()contains properly nested pairs of parenthesesbut the string ")()(does notand the string "())does not contain properly matching parentheses (agive an algorithm that returns true if string contains properly nested and balanced parenthesesand false otherwise use stack to keep track of the number of left parentheses seen so far hintat no time while scanning legal string from left to right will you have encountered more right parentheses than left parentheses (bgive an algorithm that returns the position in the string of the first offending parenthesis if the string is not properly nested and balanced that isif an excess right parenthesis is foundreturn its positionif there are too many left parenthesesreturn the position of the first excess left parenthesis return - if the string is properly balanced and nested use stack to keep track of the number and positions of left parentheses seen so far imagine that you are designing an application where you need to perform the operations insertdelete maximumand delete minimum for this applicationthe cost of inserting is not importantbecause it can be done off-line prior to startup of the time-critical sectionbut the performance of the two deletion operations are critical repeated deletions of either kind must work as fast as possible suggest data structure that can support this applicationand justify your suggestion what is the time complexity for each of the three key operations write function that reverses the order of an array of items projects deque (pronounced "deck"is like queueexcept that items may be added and removed from both the front and the rear write either an array-based or linked implementation for the deque one solution to the problem of running out of space for an array-based list implementation is to replace the array with larger array whenever the original array overflows good rule that leads to an implementation that is both space and time efficient is to double the current size of the array when there is an overflow re-implement the array-based list class of figure to support this array-doubling rule