MOD 3_ZYBOOKS 5_STACKS AND QUEUES Flashcards
(21 cards)
What is a stack?
A stack is an ADT in which items are only inserted on or removed from the top of a stack.
What do the stack push and pop operations do?
The stack push operation inserts an item on the top of the stack. The stack pop operation removes and returns the item at the top of the stack. Ex: After the operations “Push 7”, “Push 14”, “Push 9”, and “Push 5”, “Pop” returns 5. A second “Pop” returns 9.
What does LIFO mean for stacks?
A stack is referred to as a last-in first-out ADT.
A stack can be implemented using which 3 data stuctures?
1) Linked list
2) Array
3) Vector
VIEW: Common stack ADT operations.
A stack is often implemented using a linked list, with the list’s ____ node being the stack’s top.
Head
How are stack push and pop operations performed on lists?
A push operation is performed by creating a new list node, assigning the node’s data with the item, and prepending the node to the list.
A pop operation 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.
VIEW: Stack push and pop implementation.
What is a queue?
What do the enqueue and dequeue operations do?
A queue is an ADT in which items are inserted at the end of the queue and removed from the front of the queue.
The queue enqueue operation inserts an item at the end of the queue.
The queue dequeue operation removes and returns the item at the front of the queue.
Ex: After the operations “Enqueue 7”, “Enqueue 14”, and “Enqueue 9”, “Dequeue” returns 7. A second “Dequeue” returns 14.
What does FIFO mean in terms of queues?
A queue is referred to as a first-in first-out ADT.
A queue ADT is similar to waiting in line at the grocery store. A person enters at the end of the line and exits at the front. British English actually uses the word “queue” in everyday vernacular where American English uses the word “line”.
A queue can be implemented using which 2 data structures?
1) Linked list
2) Array
VIEW: Some common operations for a queue ADT.
A queue is often implemented using a linked list, with the list’s ____ node representing the queue’s front, and the list’s ____ node representing the queue’s end.
Head, tail
For queues, how are enqueueing and dequeueing performed on lists?
Enqueueing an item is performed by creating a new list node, assigning the node’s data with the item, and appending the node to the list.
Dequeuing is performed by assigning a local variable with the head node’s data, removing the head node from the list, and returning the local variable.
VIEW: Stack.h: Stack implementation using the LinkedList() class.
A stack can be implemented in C++ using a class with a single LinkedList data member. The Stack class has two functions, Push() and Pop(). Push() adds a node to the top of the stack’s list by calling LinkedList’s Prepend() function. Pop() removes the head of the stack’s list by calling the LinkedList’s RemoveAfter() function and then returns the removed node’s data. The GetHeadData() function is added to the LinkedList class so that the Stack class’s Pop() function can get the head node’s data before removing the node.
VIEW: Demo: Stack implementation using the LinkedList() class.
VIEW: Queue.h: Queue implementation using the LinkedList() class.
A queue can also be implemented in C++ using a class with a single LinkedList data member and class functions Enqueue() and Dequeue(). Enqueue() adds a node to the end of the queue’s list by calling LinkedList’s Append() function. The Dequeue() function removes the queue’s head node by calling LinkedList’s RemoveAfter() function.
VIEW: Demo: Queue implementation using the LinkedList() class.
What is a deque?
What do the push-front and push-back operations do?
What do the pop-front and pop-back operations do?
A deque (double-ended queue) is an ADT in which items can be inserted and removed at both the front and back.
The deque push-front operation inserts an item at the front of the deque, and the push-back operation inserts at the back of the deque.
The pop-front operation removes and returns the item at the front of the deque, and the pop-back operation removes and returns the item at the back of the deque.
Ex: After the operations “push-back 7”, “push-front 14”, “push-front 9”, and “push-back 5”, “pop-back” returns 5. A subsequent “pop-front” returns 9.
What does the deque peek operation do?
In addition to pushing or popping at the front or back, a deque typically supports peeking at the front and back of the deque and determining the length. A peek operation returns an item in the deque without removing the item.
VIEW: Common deque ADT operations.
