CSI 2110 Lecture Notes - Lecture 4: History Of The Web Browser, Linked List, Text Editor

• School: University of Ottawa
• Department: Computer Science
• Course: CSI 2110
• Professor: Lucia Moura

Document Summary

Main methods push(o) inserts object o at top of stack removes and returns top object pop() (error if the stack is empty) Support methods returns # of objects in stack size() isempty() returns boolean indicating if stack is empty. Returns top object without removing top() (error if the stack is empty) Auxiliary data structure for algorithms (eg. implanting a queue with 2 stacks) Example: evaluating an arithmetic expression with 2 stacks. Example: checking for balanced parenthesis in an arithmetic expression. Stack, s, consists of an array with n elements and an integer t that indicates the index of the top element in the stack. Space usage is o(n), where n is the size of the array determined when the stack is initiated, and is independent from the # of elements on the stack (n<=n) The main drawback to this implementation is that the arraystack is a static structure and has a fixed capacity.