CSC 216 Lecture Notes - Lecture 17: Time Complexity, Escalator
Document Summary
Sometimes a less powerful, but highly optimized collection is useful. Two optimized collections: stack: retrieves elements in the reverse of the order they were added, queue: retrieves elements in the same order they were added. Abstract data type (adt): specification of a collection or data and the operations that can be performed on the data: describes what a collection does, not how the (cid:272)olle(cid:272)tio(cid:374) does(cid:374)"t. As a (cid:272)lie(cid:374)t, (cid:449)e do(cid:374)"t (cid:374)eed to k(cid:374)o(cid:449) the i(cid:374)ter(cid:374)al (cid:449)orki(cid:374)gs of a(cid:374) adt. We just (cid:374)eed to understand the idea of the collection and what operations it can perform. Understanding the runtime efficiency is also important for choosing a collection. Basic queue operations: add (enqueue): add an element to the back, remove(dequeue): remove the front element. Queues in computer science: operating systems: Queue of print jobs to send to the printer. Queue of network data packets to send: programming: Modeling a line of customers of clients.