Stacks and Queues - Chapter 3 Flashcards
A blank is an ADT in which items are only inserted on or removed from the top
stack
The stack blank operation inserts an item on the top of the stack.
push
The stack blank operation removes and returns the item at the top of the stack.
pop
A stack is referred to as a blank ADT.
last-in first-out
A stack can be implemented using a blank, blank, or blank.
linked list, an array, or a vector
Inserts x on top of stack
Push(stack, x)
Returns and removes item at top of stack
Pop(stack)
Returns but does not remove item at top of stack
Peek(stack)
Returns true if stack has no items
IsEmpty(stack)
Returns the number of items in the stack
GetLength(stack)
blank and blank operations should not be applied to an empty stack; the resulting behavior may be undefined.
Pop and Peek
A stack is often implemented using a blank, with the list’s head node being the stack’s top.
linked list
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.
push
pop
A stack can be implemented with an array. Two variables are needed in addition to the array:
allocationSize: an integer for the array’s allocated size.
length: an integer for the stack’s length.
An blank is a stack with no upper limit on length
unbounded stack
An unbounded stack’s blank can increase indefinitely, so the stack’s array allocation size must also be able to increase indefinitely.
length
A blank is a stack with a length that does not exceed a maximum value. The maximum is commonly the initial allocation size
bounded stack
A bounded stack with a length equal to the maximum length is said to be blank.
full
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.
fixed size
A blank is an ADT in which items are inserted at the end of the queue and removed from the front of the queue
queue
The queue blank operation inserts an item at the end of the queue.
enqueue
The queue blank operation removes and returns the item at the front of the queue.
dequeue
A queue is referred to as a blank ADT.
first-in first-out
A queue can be implemented using a blank or a blank.
linked list or an array
The blank module implements multi-producer, multi-consumer queues.
queue
The queue module is especially useful in blank when information must be exchanged safely between multiple threads.
threaded programming
In a FIFO queue, the blank tasks added are the first retrieved.
first
In a LIFO queue, the blank added entry is the first retrieved (operating like a stack).
most recently
With a blank queue, the entries are kept sorted (using the heapq module) and the lowest valued entry is retrieved first.
priority
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.
class queue.Queue(maxsize=0)
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.
class queue.LifoQueue(maxsize=0)
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.
class queue.PriorityQueue(maxsize=0)
Constructor for an unbounded FIFO queue. Simple queues lack advanced functionality such as task tracking.
Class queue.SimpleQueue
Exception raised when non-blocking get() (or get_nowait()) is called on a Queue object which is empty.
exception queue.Empty
Exception raised when non-blocking put() (or put_nowait()) is called on a Queue object which is full.
exception queue.Full
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.
Queue.qsize()
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.
Queue.empty()
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.
Queue.full()
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).
Queue.put(item, block=True, timeout=None)
Equivalent to put(item, block=False).
Queue.put_nowait(item)
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).
Queue.get(block=True, timeout=None)
Equivalent to get(False)
Queue.get_nowait()
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.
Queue.task_done()
Blocks until all items in the queue have been gotten and processed.
Queue.join()
Inserts x at end of the queue
Enqueue(queue, x)
Returns and removes item at front of queue
Dequeue(queue)
Returns but does not remove item at the front of the queue
Peek(queue)
Returns true if queue has no items
IsEmpty(queue)
Returns the number of items in the queue
GetLength(queue)
Blank and blank operations should not be applied to an empty queue; the resulting behavior may be undefined.
Dequeue and Peek
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.
linked list
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.
array
A blank is a queue with a length that does not exceed a specified maximum value.
bounded queue
An additional variable, max_length, is needed. max_length is commonly assigned at construction time and blank for the queue’s lifetime.
does not change
A bounded queue with a length equal to the maximum length is said to be blank.
full
An blank is a queue with a length that can grow indefinitely.
unbounded queue
If max_length is blank, the queue is unbounded.
negative
If max_length is blank, the queue is bounded.
nonnegative
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.
An enqueue operation
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 dequeue operation
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.
O(N)
O(1)
A blank can be implemented in Python using a class with a single LinkedList data member. The class has two methods, push() and pop().
stack
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.
push()
pop()
A blank can also be implemented in Python using a class with a single LinkedList data member and class methods enqueue() and dequeue().
queue
blank adds a node to the end of the queue’s list by calling LinkedList’s append() method.
enqueue()
The blank removes the queue’s head node and returns the removed node’s data.
dequeue() method
A blank is an ADT in which items can be inserted and removed at both the front and back.
deque (pronounced “deck” and short for double-ended queue)
Yhe deque blank operation inserts an item at the front of the deque, and the blank operation inserts at the back of the deque.
push-front
push-back
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.
pop-front
pop-back
A blank operation returns an item in the deque without removing the item.
peek
Inserts x at the front of the deque
PushFront(deque, x)
Inserts x at the back of the deque
PushBack(deque, x)
Returns and removes item at front of deque
PopFront(deque)
Returns and removes item at back of deque
PopBack(deque)
Returns but does not remove the item at the front of deque
PeekFront(deque)
Returns but does not remove the item at the back of deque
PeekBack(deque)
Returns true if the deque is empty
IsEmpty(deque)
Returns the number of items in the deque
GetLength(deque)
