Data Structures and Algorithms Mid-Term Study Flashcards
The Queue ADT
-stores arbitrary objects- insertions and deletions follow the first-in, first-out scheme-insertions at the rear,removals at the front
enqueue()
inserts an element at the end of the queue
dequeue()
removes and returns the element at the front of the queue
object first() (Queue)
returns the element at the front without removing it
integer size() (Queue)
returns the number of elements stored
boolean isEmpty() (Queue)
indicates whether no elements are stored
Queue boundary cases
Attempting the execution of deqeueue() or first() on an empty queue returns null
Direct Applications for a Queue
- Waiting lists, bureaucracy- Access to shared resources- Multiprogramming
Indirect Applications for a Queue
- Auxiliary data structure for algoritms- Component of other data structures
Queue is limited to the __________ of the array.
size
Queue Performance runs in _________.
O(1)
enqueue() corresponds to what java.util.Queue?
add(e)offer(e)
dequeue() corresponds to what java.util.Queue?
remove()poll()
In a queue, first() corresponds to what java.util.Queue?
element()peek()
In a queue, size() corresponds to what java.util.Queue?
size()
In a queue, isEmpty() corresponds to what java.util.Queue?
isEmpty()
How do you impliment a round robin scheduler using a queue?
repeat the following steps:- e = Q.dequeue()- Service element e- Q.enqueue(e)
What method does a circular queue have that other queues don’t?
rotate()
List the methods of the Double Ended Queue.
enqueueLast(object)enqueueFirst(object)dequeueFirst()dequeueLast()
What does ADT stand for?
Abstract Data Type
What’s an example of an ADT?
A simple stock trading system.order buy(stock, shares, price)order sell(stock, shares, price)void cancel(order)
Stack
Follows Last in first out scheme.Think of the pez despenser!push(object)object pop()top()size()isEmpty()
What built in utility does java use for the stack?
java.util.Stack
Can the operations pop and top be performed even though the stack is empty?
Yes
