Data Structures Test 2 Review Queues Flashcards
Singly Linked List
a structure consisting of a sequence of nodes
A singly linked list stores a _________ to the first node (head) and last (tail)
pointer
In a singly linked list, each node stores…
an elementa link to the next node
template class SLinkedListNode { public: Type elem; [WHAT GOES HERE?] };
SLinkedListNode *next;
Singly Linked List Operation: insertFront(e):
inserts an element on the front of the list
Singly Linked List Operation: removeFront():
returns and removes the element at the front of the list
Singly Linked List Operation: insertBack(e):
inserts an element on the back of the list
Singly Linked List Operation: removeBack():
returns and removes the element at the end of the list
Stack with a Singly Linked List: The _______ element of the stack is the ______ ______ of the list
topfirst node
Stack with a Singly Linked List: The space used is ______ and each operation of the Stack ADT takes _______ time
O(n)O(1)
Stack Operation: push(e) is most like what Singly Linked List Operation?
insertFront(e)
Stack Operation: pop() is most like what Singly Linked List Operation?
removeFront()
What 2 Singly Linked List Operations do not work with Stack Operations?
insertBack(e)removeBack()
With minor alteration or addition, top() could be very similar to…
removeFront()
_______ and ________ would require the addition of a counter that increments each time push() is called and decrements when pop() is called
size() isEmpty()
Queues store…
arbitrary objects
Main queue operations:
enqueue(e)dequeue()
Enqueue(e): aka addQueue, aka push
inserts an element at the end of the queue
Dequeue(): aka deleteQueue, aka pop
removes and returns the element at the front of the queue
Auxiliary queue operations:
front()size()isEmpty()
Less common queue operations
back()isFullQueue()
front():
returns the element at the front without removing it
size():
returns the number of elements stored
isEmpty():
returns a Boolean value indicating if there are no elements in the queue
back():
returns the element at the back without removing it
isFullQueue():
returns if queue is full
In a queue, insertions are at the _____ of the queue and removals are at the ______ of the queue
endfront
Queue exceptions: Attempting to execute dequeue or front on an empty queue throws a(n)…
EmptyQueueException
template class queueADT { public: virtual bool isEmptyQueue() const = 0; }
// function to determing whether the queue is empty// post condition: returns true if the queue is empty, otherwise returns false
template class queueADT { public: virtual bool isFullQueue() const = 0; }
// function to determine whether the queue is full// post condition: returns true if the queue is full, otherwise returns false
template class queueADT { public: virtual void initializeQueue() const = 0; }
// function to initialize the queue to an empty state// post condition: the queue is empty
template class queueADT { public: virtual Type front() const = 0; }
// function to return the first element of the queue// precondition: the queue exists and is not empty// post condition: if the queue is empty, the program terminates; otherwise, the first element of the queue is returned
template class queueADT { public: virtual Type back() const = 0; }
// function to return the last element of the queue// precondition: the queue exists and is not empty// post condition: if the queue is empty, the program terminates; otherwise, the first element of the queue is returned
template class queueADT { public: virtual void addQueue(const Type& queueElement) = 0; }
// function to add queueElement to the queue// precondition: the queue exists and is not full// post condition: the queue is changed and queueElement is added to the queueaka pushaka enqueue
template class queueADT { public: virtual void deleteQueue() const = 0; }
// function to remove the first element of the queue// precondition: the queue exists and is not empty// post condition: the queue is changed and the first element is removed from the queueaka popaka dequeue
Main queue operation: enqueue(e) is most like what Singly Linked List Operation?
insertBack(e)
Main queue operation: dequeue() is most like what Singly Linked List Operation?
removeFront()
Main queue operation: front() would require a minor alteration or addition to LinkedList and would be very similar to…
removeFront()
Doubly Linked List
a structure consisting of a sequence of nodes
