Applied machine learning 神经网络.ppt

Stacks and Queues CSC220 Data Structure Winter 2004-5 Abstract Data Type Abstract Data Type as a design tool Concerns only on the important concept or model No concern on implementation details. Stack Queue is an example of ADT An array is not ADT. What is the difference? Stack Queue vs. Array Arrays are data storage structures while stacks and queues are specialized DS and used as programmer’s tools. Stack – a container that allows push and pop Queue - a container that allows enqueue and dequeue No concern on implementation details. In an array any item can be accessed, while in these data structures access is restricted. They are more abstract than arrays. Questions? Array is not ADT Is Linked list ADT? Is Binary-tree ADT? Is Hash table ADT? What about graph? Stacks Allows access to only the last item inserted. An item is inserted or removed from the stack from one end called the “top” of the stack. This mechanism is called Last-In-First-Out (LIFO). A Stack Applet example Stack operations Placing a data item on the top is called “pushing”, while removing an item from the top is called “popping” it. push and pop are the primary stack operations. Some of the applications are : microprocessors, some older calculators etc. Example of Stack codes First example stack ADT and implementation C:\Documents and Settings\box\My Documents\CS\CSC\220\ReaderPrograms\ReaderFiles\Chap04\Stack\stack.java push and pop operations are performed in O(1) time. Example of Stack codes Reversed word What is it? ABC - CBA C:\Documents and Settings\box\My Documents\CS\CSC\220\ReaderPrograms\ReaderFiles\Chap04\Reverse\reverse.java Example of Stack codes BracketChecker (balancer) A syntax checker (compiler) that understands a language containing any strings with balanced brackets ‘{‘ ‘[‘ ‘(‘ and ‘)’, ‘]’, ‘}’ S - Bl S1 Br S1 - Bl string Br Bl - ‘{‘ | ‘[‘ | ‘(‘ Br - ‘)’, | ‘]’, | ‘}’ C:\Documents and Settings\box\My Documents\CS\CSC\220\ReaderPrograms\ReaderFiles\Chap