Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Data Structure and Algorithms I > Stacks and Queues - Chapter 3 > Flashcards

Stacks and Queues - Chapter 3 Flashcards

1
Q

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

A

stack

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

push

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

pop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

A stack is referred to as a blank ADT.

A

last-in first-out

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

linked list, an array, or a vector

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Inserts x on top of stack

A

Push(stack, x)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Returns and removes item at top of stack

A

Pop(stack)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Returns but does not remove item at top of stack

A

Peek(stack)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Returns true if stack has no items

A

IsEmpty(stack)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Returns the number of items in the stack

A

GetLength(stack)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

Pop and Peek

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

linked list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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.

A

push
pop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

An blank is a stack with no upper limit on length

A

unbounded stack

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

length

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A

bounded stack

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A

full

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

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.

A

fixed size

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

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

A

queue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

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

A

enqueue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

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

A

dequeue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

A queue is referred to as a blank ADT.

A

first-in first-out

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

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

A

linked list or an array

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

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

A

queue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

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

A

threaded programming

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

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

A

first

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

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

A

most recently

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

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

A

priority

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

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.

A

class queue.Queue(maxsize=0)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

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.

A

class queue.LifoQueue(maxsize=0)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

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.

A

class queue.PriorityQueue(maxsize=0)

33
Q

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

A

Class queue.SimpleQueue

34
Q

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

A

exception queue.Empty

35
Q

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

A

exception queue.Full

36
Q

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.

A

Queue.qsize()

37
Q

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.

A

Queue.empty()

38
Q

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.

A

Queue.full()

39
Q

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).

A

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

40
Q

Equivalent to put(item, block=False).

A

Queue.put_nowait(item)

41
Q

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).

A

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

42
Q

Equivalent to get(False)

A

Queue.get_nowait()

43
Q

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.

A

Queue.task_done()

44
Q

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

A

Queue.join()

45
Q

Inserts x at end of the queue

A

Enqueue(queue, x)

46
Q

Returns and removes item at front of queue

A

Dequeue(queue)

47
Q

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

A

Peek(queue)

48
Q

Returns true if queue has no items

A

IsEmpty(queue)

49
Q

Returns the number of items in the queue

A

GetLength(queue)

50
Q

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

A

Dequeue and Peek

51
Q

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.

A

linked list

52
Q

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.

A

array

53
Q

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

A

bounded queue

54
Q

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

A

does not change

55
Q

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

A

full

56
Q

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

A

unbounded queue

57
Q

If max_length is blank, the queue is unbounded.

A

negative

58
Q

If max_length is blank, the queue is bounded.

A

nonnegative

59
Q

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.

A

An enqueue operation

60
Q

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.

A

A dequeue operation

61
Q

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.

A

O(N)
O(1)

62
Q

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

A

stack

63
Q

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.

A

push()
pop()

64
Q

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

A

queue

65
Q

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

A

enqueue()

66
Q

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

A

dequeue() method

67
Q

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

A

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

68
Q

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

A

push-front
push-back

69
Q

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.

A

pop-front
pop-back

70
Q

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

A

peek

71
Q

Inserts x at the front of the deque

A

PushFront(deque, x)

72
Q

Inserts x at the back of the deque

A

PushBack(deque, x)

73
Q

Returns and removes item at front of deque

A

PopFront(deque)

74
Q

Returns and removes item at back of deque

A

PopBack(deque)

75
Q

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

A

PeekFront(deque)

76
Q

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

A

PeekBack(deque)

77
Q

Returns true if the deque is empty

A

IsEmpty(deque)

78
Q

Returns the number of items in the deque

A

GetLength(deque)

Data Structure and Algorithms I (11 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions