Data Structures II (Stacks, Queues, & Vectors) Flashcards
What is a Stack?
An abstract data type that uses first-in last-out ordering (FILO). That is to say that insertions and removals to/from a stack are in the top position only.
A good analogy is a stack of cafeteria trays. New trays are placed on top, and any time you want to remove a tray from the stack, you take it off the top.
What are the two primary operations of a stack class, and what do they do?
A stack class will have two primary operations:
push – adds an item onto the top of the stack
pop – removes the top item from the stack
How are stacks commonly used?
Typical application areas include compilers, operating systems, handling of program memory (nested function calls)
What is a Queue?
An abstract data type that uses first-in first-out (FIFO) ordering to its functionality. Insertions occur at the “end” of the queue, and removals from the “front” of the queue.
An analogy of this concept could be waiting in line for a ride at an amusement park. Get in line at the end. First come, first serve.
What are the two primary operations of a queue and what do they do?
A queue class will have two primary operations:
enqueue – adds an item into the queue (i.e. at the back of the line)
dequeue – removes an item from the queue (i.e. from the front of the line).
How are queues commonly used?
Typical application areas include print job scheduling, operating systems (process scheduling).
What is a vector?
A vector is a specific implementation of the sequence/list abstract data type. It is a data structure that stores items of the same type and is based on storage in an array.
What is the primary usage of a vector?
By encapsulating an array into a class (a vector class), we can use dynamic allocation to allow the internal array to be flexible in size and handle boundary issues of the array (error checking for out-of-bounds indices).
What are the main advantages and disadvantages of a vector?
Advantages: Random access - i.e. quick locating of data if the index is known.
Disadvantages: Inserts and Deletes are typically slow, since they may require shifting many elements to consecutive array slots
