Stacks and Queues - Chapter 3

Question 1

A blank is an ADT in which items are only inserted on or removed from the top

Answer 1

stack

Question 2

The stack blank operation inserts an item on the top of the stack.

Answer 2

push

Question 3

The stack blank operation removes and returns the item at the top of the stack.

Answer 3

pop

Question 4

A stack is referred to as a blank ADT.

Answer 4

last-in first-out

Question 5

A stack can be implemented using a blank, blank, or blank.

Answer 5

linked list, an array, or a vector

Question 6

Inserts x on top of stack

Answer 6

Push(stack, x)

Question 7

Returns and removes item at top of stack

Answer 7

Pop(stack)

Question 8

Returns but does not remove item at top of stack

Answer 8

Peek(stack)

Question 9

Returns true if stack has no items

Answer 9

IsEmpty(stack)

Question 10

Returns the number of items in the stack

Answer 10

GetLength(stack)

Question 11

blank and blank operations should not be applied to an empty stack; the resulting behavior may be undefined.

Answer 11

Pop and Peek

Question 12

A stack is often implemented using a blank, with the list’s head node being the stack’s top.

Answer 12

linked list

Question 13

A stack is often implemented using a linked list, with the list’s head node being the stack’s top. A blank is performed by creating a new list node, assigning the node’s data with the item, and prepending the node to the list. A blank is performed by assigning a local variable with the head node’s data, removing the head node from the list, and then returning the local variable.

Answer 13

push
pop

Question 14

A stack can be implemented with an array. Two variables are needed in addition to the array:

Answer 14

allocationSize: an integer for the array’s allocated size.
length: an integer for the stack’s length.

Question 15

An blank is a stack with no upper limit on length

Answer 15

unbounded stack

Question 16

An unbounded stack’s blank can increase indefinitely, so the stack’s array allocation size must also be able to increase indefinitely.

Answer 16

length

Question 17

A blank is a stack with a length that does not exceed a maximum value. The maximum is commonly the initial allocation size

Answer 17

bounded stack

Question 18

A bounded stack with a length equal to the maximum length is said to be blank.

Answer 18

full

Question 19

The Stack class implementation that follows uses a Python list. A Python list does not have a blank, so implementing reallocation is not needed. Therefore, implementation is simpler than an implementation with a fixed size array.

Answer 19

fixed size

Question 20

A blank is an ADT in which items are inserted at the end of the queue and removed from the front of the queue

Answer 20

queue

Question 21

The queue blank operation inserts an item at the end of the queue.

Answer 21

enqueue

Question 22

The queue blank operation removes and returns the item at the front of the queue.

Answer 22

dequeue

Question 23

A queue is referred to as a blank ADT.

Answer 23

first-in first-out

Question 24

A queue can be implemented using a blank or a blank.

Answer 24

linked list or an array

Question 25

The blank module implements multi-producer, multi-consumer queues.

Answer 25

queue

Question 26

The queue module is especially useful in blank when information must be exchanged safely between multiple threads.

Answer 26

threaded programming

Question 27

In a FIFO queue, the blank tasks added are the first retrieved.

Answer 27

first

Question 28

In a LIFO queue, the blank added entry is the first retrieved (operating like a stack).

Answer 28

most recently

Question 29

With a blank queue, the entries are kept sorted (using the heapq module) and the lowest valued entry is retrieved first.

Answer 29

priority

Question 30

Constructor for a FIFO queue. maxsize is an integer that sets the upperbound limit on the number of items that can be placed in the queue. Insertion will block once this size has been reached, until queue items are consumed. If maxsize is less than or equal to zero, the queue size is infinite.

Answer 30

class queue.Queue(maxsize=0)

Question 31

Constructor for a LIFO queue. maxsize is an integer that sets the upperbound limit on the number of items that can be placed in the queue. Insertion will block once this size has been reached, until queue items are consumed. If maxsize is less than or equal to zero, the queue size is infinite.

Answer 31

class queue.LifoQueue(maxsize=0)

Question 32

Constructor for a priority queue. maxsize is an integer that sets the upperbound limit on the number of items that can be placed in the queue. Insertion will block once this size has been reached, until queue items are consumed. If maxsize is less than or equal to zero, the queue size is infinite.

Answer 32

class queue.PriorityQueue(maxsize=0)

Question 33

Constructor for an unbounded FIFO queue. Simple queues lack advanced functionality such as task tracking.

Answer 33

Class queue.SimpleQueue

Question 34

Exception raised when non-blocking get() (or get_nowait()) is called on a Queue object which is empty.

Answer 34

exception queue.Empty

Question 35

Exception raised when non-blocking put() (or put_nowait()) is called on a Queue object which is full.

Answer 35

exception queue.Full

Question 36

Return the approximate size of the queue. Note, qsize() > 0 doesn’t guarantee that a subsequent get() will not block, nor will qsize() < maxsize guarantee that put() will not block.

Answer 36

Queue.qsize()

Question 37

Return True if the queue is empty, False otherwise. If empty() returns True it doesn’t guarantee that a subsequent call to put() will not block. Similarly, if empty() returns False it doesn’t guarantee that a subsequent call to get() will not block.

Answer 37

Queue.empty()

Question 38

Return True if the queue is full, False otherwise. If full() returns True it doesn’t guarantee that a subsequent call to get() will not block. Similarly, if full() returns False it doesn’t guarantee that a subsequent call to put() will not block.

Answer 38

Queue.full()

Question 39

Put item into the queue. If optional args block is true and timeout is None (the default), block if necessary until a free slot is available. If timeout is a positive number, it blocks at most timeout seconds and raises the Full exception if no free slot was available within that time. Otherwise (block is false), put an item on the queue if a free slot is immediately available, else raise the Full exception (timeout is ignored in that case).

Answer 39

Queue.put(item, block=True, timeout=None)

Question 40

Equivalent to put(item, block=False).

Answer 40

Queue.put_nowait(item)

Question 41

Remove and return an item from the queue. If optional args block is true and timeout is None (the default), block if necessary until an item is available. If timeout is a positive number, it blocks at most timeout seconds and raises the Empty exception if no item was available within that time. Otherwise (block is false), return an item if one is immediately available, else raise the Empty exception (timeout is ignored in that case).

Answer 41

Queue.get(block=True, timeout=None)

Question 42

Equivalent to get(False)

Answer 42

Queue.get_nowait()

Question 43

Indicate that a formerly enqueued task is complete. Used by queue consumer threads. For each get() used to fetch a task, a subsequent call to task_done() tells the queue that the processing on the task is complete.

Answer 43

Queue.task_done()

Question 44

Blocks until all items in the queue have been gotten and processed.

Answer 44

Queue.join()

Question 45

Inserts x at end of the queue

Answer 45

Enqueue(queue, x)

Question 46

Returns and removes item at front of queue

Answer 46

Dequeue(queue)

Question 47

Returns but does not remove item at the front of the queue

Answer 47

Peek(queue)

Question 48

Returns true if queue has no items

Answer 48

IsEmpty(queue)

Question 49

Returns the number of items in the queue

Answer 49

GetLength(queue)

Question 50

Blank and blank operations should not be applied to an empty queue; the resulting behavior may be undefined.

Answer 50

Dequeue and Peek

Question 51

A queue is often implemented using a blank, with the list's head node representing the queue's front, and the list's tail node representing the queue's end.

Answer 51

linked list

Question 52

A queue can be implemented with an blank. Two variables are needed: length: an integer for the queue's length. front_index: an integer for the queue's front item index.

Answer 52

array

Question 53

A blank is a queue with a length that does not exceed a specified maximum value.

Answer 53

bounded queue

Question 54

An additional variable, max_length, is needed. max_length is commonly assigned at construction time and blank for the queue's lifetime.

Answer 54

does not change

Question 55

A bounded queue with a length equal to the maximum length is said to be blank.

Answer 55

full

Question 56

An blank is a queue with a length that can grow indefinitely.

Answer 56

unbounded queue

Question 57

If max_length is blank, the queue is unbounded.

Answer 57

negative

Question 58

If max_length is blank, the queue is bounded.

Answer 58

nonnegative

Question 59

Compares self.length and self.max_length. If equal, the queue is full and so no change occurs and False is returned. Compares self.length and len(self.queue_list). If equal, a resize operation occurs. Computes the enqueued item's index as (self.front_index + self.length) % len(self.queue_list) and assigns to queue_list at that index. Ex: Enqueueing 42 into a queue with front index 2, length 3, and queue_list length 8 assigns queue_list at index (2 + 3) % 8 = 5 with 42. Increments the length attribute and then returns True.

Answer 59

An enqueue operation

Question 60

Makes a copy of the list item at front_index. Decrements length. Increments front_index, resetting to 0 if the incremented value equals the allocation size. Returns the list item from step 1.

Answer 60

A dequeue operation

Question 61

Using the implementation from above, worst-case time complexities are the same whether the queue is bounded or unbounded: blank for enqueue and blank for dequeue.

Answer 61

O(N) O(1)

Question 62

A blank can be implemented in Python using a class with a single LinkedList data member. The class has two methods, push() and pop().

Answer 62

stack

Question 63

Blank adds a node to the top of the stack's list by calling LinkedList's prepend() method. blank removes the head of the stack's list by calling the LinkedList's remove_after() method and then returns the removed node's data.

Answer 63

push() pop()

Question 64

A blank can also be implemented in Python using a class with a single LinkedList data member and class methods enqueue() and dequeue().

Answer 64

queue

Question 65

blank adds a node to the end of the queue's list by calling LinkedList's append() method.

Answer 65

enqueue()

Question 66

The blank removes the queue's head node and returns the removed node's data.

Answer 66

dequeue() method

Question 67

A blank is an ADT in which items can be inserted and removed at both the front and back.

Answer 67

deque (pronounced "deck" and short for double-ended queue)

Question 68

Yhe deque blank operation inserts an item at the front of the deque, and the blank operation inserts at the back of the deque.

Answer 68

push-front push-back

Question 69

The blank operation removes and returns the item at the front of the deque, and the blank operation removes and returns the item at the back of the deque.

Answer 69

pop-front pop-back

Question 70

A blank operation returns an item in the deque without removing the item.

Answer 70

peek

Question 71

Inserts x at the front of the deque

Answer 71

PushFront(deque, x)

Question 72

Inserts x at the back of the deque

Answer 72

PushBack(deque, x)

Question 73

Returns and removes item at front of deque

Answer 73

PopFront(deque)

Question 74

Returns and removes item at back of deque

Answer 74

PopBack(deque)

Question 75

Returns but does not remove the item at the front of deque

Answer 75

PeekFront(deque)

Question 76

Returns but does not remove the item at the back of deque

Answer 76

PeekBack(deque)

Question 77

Returns true if the deque is empty

Answer 77

IsEmpty(deque)

Question 78

Returns the number of items in the deque

Answer 78

GetLength(deque)