02_Containers_and_Permutations
Lecture 2
Stacks and Queues
EECS 281: Data Structures & Algorithms
Data Structures and
Abstract Data Types
Data Structures & Algorithms
3
Data Structures and ADTs
• Need a way to store and organize data in
order to facilitate access and modifications
• An abstract data type (ADT) combines
data with valid operations and their
behaviors on stored data
– e.g., insert, delete, access
– ADTs define an interface
• A data structure provides a concrete
implementation of an ADT
4
Measuring Performance
• Several design choices for implementing ADTs
– Contiguous data (arrays or vectors)
– Connected data (pointers or linked lists/trees)
• Runtime speed and size of data structure
– How much time is needed to perform an operation?
(count number of steps)
– How much space is needed to perform an operation?
(count size of data and pointers/metadata)
– How does size/number of inputs affect these results?
(constant, linear, exponential, etc.)
• We formalize performance measurements with
complexity analysis
5
• How many operations are needed to insert
a value at the end of this singly-linked list?
• Can you generalize this for a list with n
elements?
Analysis Example
1 3 6 nullptr
head_ptr
7
Choosing a Data Structure
for a Given Application
• What to look for
– The right operations (e.g., add_elt, remove_elt)
– The right behavior (e.g., push_back, pop_back)
– The right trade-offs for runtime complexities
– Memory overhead
• Potential concern
– Limiting interface to avoid problems (e.g., no insert_mid)
• Examples
– Order tracking at a fast-food drive-through (pipeline)
– Interrupted phone calls to a receptionist
– Your TODO list
Data Structures and
Abstract Data Types
Data Structures & Algorithms
Basic Containers: Stack
Data Structures & Algorithms
10
Stack ADT: Interface
• Supports insertion/removal in LIFO order
– Last In, First Out
Method Description
push(object) Add object to top of the stack
pop() Remove top element
object &top() Return a reference to top element
size() Number of elements in stack
empty() Checks if stack has no elements
• Web browser’s “back” feature
• Text editor’s “Undo” feature
• Function calls in C++
Examples
11
Method Implementation
push(object) 1. If needed, allocate a bigger array and copy data
2. Add new element at top_ptr, increment top_ptr
pop() Decrement top_ptr
object &top() Dereference top_ptr – 1
size() Subtract base_ptr from top_ptr pointer
empty() Check if base_ptr == top_ptr
Stack: Implementation – Array/Vector
Keep a pointer (top_ptr) just past the last element
base_ptr
top_ptr
How many steps/operations for each method?
12
Stack: Implementation – Linked List
Method Implementation
push(object) Insert new node at head_ptr, increment size
pop() Delete node at head_ptr, decrement size
object &top() Dereference head_ptr
size() Return size
empty() Check if size == 0 or head_ptr == nullptr
Singly-linked is sufficient
How many steps/operations for each method?
head_ptr
Is an array or linked list more efficient for stacks?
size = 4
nullptr
*Alternative approach: eliminate size, count nodes each time
13
Stack: Which Implementation?
• The asymptotic complexities of each are similar
• The constant factor attached to the complexity is lower for vector
– Constant number of operations, but there is “less” to do
– The linked list must allocate memory for each node individually!
• The linked list also has higher memory overhead
– i.e. Pointers between nodes as well as the actual data payload
Method Array/Vector Linked List
push(object) Constant (linear when
resizing vector)*
Constant
pop() Constant Constant
object &top() Constant Constant
size() Constant Constant (with tracked size)
empty() Constant Constant
*Averages out to constant with many pushes (amortized constant)
14
STL Stacks: std::stack<>
• Code: #include
• You can choose the underlying container
• All operations are implemented generically
on top of the given container
– No specialized code based on given container
Stack
Default Underlying Container std::deque<>
Optional Underlying Container std::list<>✝
std::vector<>
✝std::list<> is a doubly-linked list
Basic Containers: Stack
Data Structures & Algorithms
Basic Containers: Queue
Data Structures & Algorithms
17
Queue ADT: Interface
Method Description
push(object) Add element to back of queue
pop() Remove element at front of queue
object &front() Return reference to element at front of queue
size() Number of elements in queue
empty() Checks if queue has no elements
• Supports insertion/removal in FIFO order
– First In, First Out
• Waiting in line for lunch
• Adding songs to the end of a playlist
Examples
18
1. back_idx == front_idx
since array is empty
back_idx
front_idx
Event Sequence
Queue: Implementation – Circular Buffer
Circular
array with
capacity 3
size = 0
19
back_idx
front_idx
1. back_idx == front_idx
since array is empty
2. push element
Event Sequence
Queue: Implementation – Circular Buffer
Circular
array with
capacity 3
size = 1
20
front_idx
1. back_idx == front_idx
since array is empty
2. push element
3. push element
Event Sequence
back_idx
Queue: Implementation – Circular Buffer
Circular
array with
capacity 3
size = 2
21
front_idx
1. back_idx == front_idx
since array is empty
2. push element
3. push element
4. push element
Event Sequence
back_idx
Queue: Implementation – Circular Buffer
Circular
array with
capacity 3
size = 3
22
Circular
array with
capacity 3
1. back_idx == front_idx
since array is empty
2. push element
3. push element
4. push element
5. push element (need to
allocate more memory)*
Circular
array with
capacity 6
Event Sequence
* When allocating more memory, it is common to double memory
front_idx
back_idx
Queue: Implementation – Circular Buffer
front_idx
back_idx
size = 3
size = 4
23
1. back_idx == front_idx
since array is empty
2. push element
3. push element
4. push element
5. push element (need to
allocate more memory)*
6. pop element
Event Sequence
front_idx
back_idx
Queue: Implementation – Circular Buffer
Circular
array with
capacity 6
size = 3
* When allocating more memory, it is common to double memory
24
1. back_idx == front_idx
since array is empty
2. push element
3. push element
4. push element
5. push element (need to
allocate more memory)*
6. pop element
7. pop element
Event Sequence
Queue: Implementation – Circular Buffer
front_idx
back_idx
Circular
array with
capacity 6
size = 2
25
Queue: Implementation – Circular Buffer
Method Implementation
push(object) 1. If size == capacity, reallocate larger array
and copy over elements, “unrolling” as you go
unroll: start front_idx at 0, insert all elements
2. Insert value at back_idx, increment size and
back_idx, wrapping around either as needed
pop() Increment front_idx, decrement size
object &front() Return reference to element at front_idx
size() Return size
empty() Check if size == 0
How many steps/operations for each method?
front_idx back_idx
Use a circular array
size = 3
26
Queue: Implementation – Linked List
Method Implementation
push(object) Append node after tail_ptr, increment size
pop() Delete node at head_ptr, decrement size
object &front() Deference head_ptr
size() Return size
empty() Return head_ptr == nullptr
Singly-linked is sufficient
How many steps/operations for each method?
head_ptr nullptr
tail_ptr
*Alternative approach: count nodes when needed
size = 4
27
• The asymptotic complexities of each are similar
• The constant factor attached to the complexity is lower for vector
– Constant number of operations, but there is “less” to do
– The linked list must allocate memory for each node individually!
• The linked list also has higher memory overhead
– i.e. Pointers between nodes as well as the actual data payload
Queue: Which Implementation?
Method Array/Vector Linked List
push(object) Constant (linear when
resizing vector)*
Constant
pop() Constant Constant
object &front() Constant Constant
size() Constant Constant (with tracked size)
empty() Constant Constant
*Averages out to constant with many pushes (amortized constant)
28
STL Queues: std::queue<>
• Code: #include
• You can choose the underlying container
• All operations are implemented generically
on top of the given container
– No specialized code based on given container
Queue
Default Underlying Container std::deque<>
Optional Underlying Container std::list<>
Basic Containers: Queue
Data Structures & Algorithms
Basic Containers: Deque
Data Structures & Algorithms
31
Deque Terminology Clarification
• “Deque” is an abbreviation of Double-Ended
Queue.
Pronounced “deck”
• “Dequeue” is another name for removing
something from a queue.
Pronounced “dee-queue”
• The STL includes std::deque<>, which is an
implementation of a Deque, and is usually based
on a growable collection of fixed-sized arrays.
32
Deque ADT: a queue and stack in one
(Double-ended Queue)
• ADT that allows efficient insertion and removal
from the front and the back
• 6 major methods
– push_front(), pop_front(), front()
– push_back(), pop_back(), back()
• Minor methods
– size(), empty()
• Can traverse using iterator
• STL incudes constant time operator[]()
33
Simple Deque Implementation
Doubly-linked list
– Singly-linked doesn’t support efficient removal
– Other operations map directly to doubly-linked list
operations
head_ptr
front_idx back_idx
Circular Buffer
– front_idx and back_idx both get
incremented/decremented
tail_ptr
34
STL Deque, Two Internal Views
Taken from: https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl
and http://cpp-tip-of-the-day.blogspot.com/2013/11/how-is-stddeque-implemented.html
https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl
http://cpp-tip-of-the-day.blogspot.com/2013/11/how-is-stddeque-implemented.html
35
STL Deques: std::deque<>
• Code: #include
• Stack/Queue-like behavior at both ends
• Random access with [] or .at()
Basic Containers: Deque
Data Structures & Algorithms
Customizable Containers:
Priority Queue
Data Structures & Algorithms
38
What is a Priority Queue?
• Each datum paired with a priority value
– Priority values are usually numbers
– Should be able to compare priority values (<)
• Supports insertion of data and inspection
• Supports removal of datum with highest priority
– ”Most important” determined by given ordering
Like a group of bikers
where the fastest ones
exit the race first
39
Priority Queue Example:
Emergency Call Center
1. Level 2 call comes in
0
1
2
• Operators receive calls and assign levels of urgency
• Lower numbers indicate more urgent calls
• Calls are dispatched (or not dispatched) by computer to
police squads based on urgency
nullptr
nullptr
nullptr
40
Priority Queue Example:
Emergency Call Center
1. Level 2 call comes in
2. Level 2 call comes in 0
1
2
• Operators receive calls and assign levels of urgency
• Lower numbers indicate more urgent calls
• Calls are dispatched (or not dispatched) by computer to
police squads based on urgency
nullptr
nullptr
nullptr
41
Priority Queue Example:
Emergency Call Center
1. Level 2 call comes in
2. Level 2 call comes in
3. Level 1 call comes in
0
1
2
• Operators receive calls and assign levels of urgency
• Lower numbers indicate more urgent calls
• Calls are dispatched (or not dispatched) by computer to
police squads based on urgency
nullptr
nullptr
nullptr
42
Priority Queue Example:
Emergency Call Center
1. Level 2 call comes in
2. Level 2 call comes in
3. Level 1 call comes in
4. A call is dispatched
0
1
2
• Operators receive calls and assign levels of urgency
• Lower numbers indicate more urgent calls
• Calls are dispatched (or not dispatched) by computer to
police squads based on urgency
nullptr
nullptr
nullptr
43
Priority Queue Example:
Emergency Call Center
1. Level 2 call comes in
2. Level 2 call comes in
3. Level 1 call comes in
4. A call is dispatched
5. Level 0 call comes in
0
1
2
• Operators receive calls and assign levels of urgency
• Lower numbers indicate more urgent calls
• Calls are dispatched (or not dispatched) by computer to
police squads based on urgency
nullptr
nullptr
nullptr
44
Priority Queue Example:
Emergency Call Center
1. Level 2 call comes in
2. Level 2 call comes in
3. Level 1 call comes in
4. A call is dispatched
5. Level 0 call comes in
6. A call is dispatched
0
1
2
• Operators receive calls and assign levels of urgency
• Lower numbers indicate more urgent calls
• Calls are dispatched (or not dispatched) by computer to
police squads based on urgency
nullptr
nullptr
nullptr
45
Priority Queue ADT: Interface
• Supports insertion, with removal in descending
priority order
Method Description
push(object) Add object to the priority queue
pop() Remove highest priority element
const object &top() Return a reference to highest priority element
size() Number of elements in priority queue
empty() Checks if priority queue has no elements
• Hospital queue for arriving patients
• Load balancing on servers
Examples
46
Priority Queue Implementations
Array of Linked Lists
0
1
2
3
Priority value
used as index
value in array
Insert Remove
Unordered sequence container Constant Linear
Sorted sequence container Linear Constant
Heap Logarithmic Logarithmic
Array of linked lists
(for priorities of small integers)
Constant Constant
nullptr
nullptr
nullptr
nullptr
47
A Customizable Container
• By default std::priority_queue<> uses std::less<> to
determine relative priority of two elements
• A ”default PQ” is a “max-PQ”, where the largest element
has highest priority
• If a “min-PQ” is desired, customize with std::greater<>,
so the smallest element has highest priority
• If the PQ will hold elements that cannot be compared
with std::less<> or std::greater<>, customize with
custom comparator (function object)
• Custom comparators can work with objects, perform tie-
breaks on multiple object members, and other
functionality
48
std::priority_queue<>
• STL will maintain a Heap in any random access
container
– #include
• Common std::priority_queue<> declarations
– “Max” PQ using std::less<>
std::priority_queue
– PQ using a custom comparator type, COMP
std::priority_queue
• Manual priority queue implementation with standard
library functions
– #include
– std::make_heap()
– std::push_heap()
– std::pop_heap()
Customizable Containers:
Priority Queue
Data Structures & Algorithms
Generating Permutations
Data Structures & Algorithms
51
Algorithm Engineering:
Juggling with Stacks and Queues
• Task: given N elements, generate
all N-element permutations
• Ingredients of a solution
– One recursive function
– One stack
– One queue
• Technique: moving elements
between the two containers
52
Permutations Example
Input: {1, 2, 3}
Output: {
{1, 2, 3},
{1, 3, 2},
{2, 3, 1},
{2, 1, 3},
{3, 1, 2},
{3, 2, 1}
}
53
Implementation: Helper Function
1 template
2 ostream &operator<<(ostream &out, const stack
3 // display the contents of a stack on a single line
4 // e.g., cout << my_stack << endl;
5 stack
6 while (!tmpStack.empty()) {
7 out << tmpStack.top() << ' ';
8 tmpStack.pop();
9 } // while
10 return out;
11 } // operator<<()
54
Better Helper Function
1 template
2 ostream &operator<<(ostream &out, const vector
3 // display the contents of a vector on a single line
4 // e.g., cout << my_vec << endl;
5 for (auto &el : v) {
6 out << el << ' ';
7 } // for
8 return out;
9 } // operator<<()
55
Implementation
1 template
2 void genPerms(vector
3 // perm is only a “prefix” until unused is empty
4 if (unused.empty()) {
5 cout << perm << '\n';
6 return;
7 } // if
8 for (size_t k = 0; k != unused.size(); ++k) {
9 perm.push_back(unused.front());
10 unused.pop_front();
11 genPerms(perm, unused);
12 unused.push_back(perm.back());
13 perm.pop_back();
14 } // for
15 } // genPerms()
56
Implementation: Sample Driver
1 int main() {
2 size_t n;
3 cout << "Enter n: " << flush;
4 while (!(cin >> n)) { // keep going while NO integer
5 cin.clear();
6 cin.ignore(numeric_limits
7 cout << "Enter n: " << flush;
8 } // while
9
10 vector
11 deque
12 iota(unused.begin(), unused.end(), 1);
13 genPerms(perm, unused);
14 return 0;
15 } // main()
57
Implement to Test
Q: how does the genPerms() compare to
STL’s function std::next_permutation() ?
http://en.cppreference.com/w/cpp/algorithm/next_permutation
A: each method has its advantages and
can be more appropriate in some situations
http://en.cppreference.com/w/cpp/algorithm/next_permutation
58
Another Implementation
1 template
2 void genPerms(vector
3 if (permLength == path.size()) {
4 // Do something with the path
5 return;
6 } // if
7 if (!promising(path, permLength))
8 return; // this partial permutation isn’t better
9 for (size_t i = permLength; i < path.size(); ++i) {
10 swap(path[permLength], path[i]);
11 genPerms(path, permLength + 1);
12 swap(path[permLength], path[i]);
13 } // for
14 } // genPerms()
Generating Permutations
Data Structures & Algorithms