Content

Data Structures and Abstract Data Types Measuring Performance Choosing a Data Structure for a Given Application Stack ADT Queue ADT Deque ADT Priority Queue Generating Permutations <- Go Back

EECS 281: Data Structures and Algorithms

Section 01

Stack, Queue, and Priority Queue ADTs

University of Michigan at Ann Arbor

Last Edit Date: 05/02/2023

Disclaimer and Term of Use:

1. We do not guarantee the accuracy and completeness of the summary content. Some of the course material may not be included, and some of the content in the summary may not be correct. You should use this file properly and legally. We are not responsible for any results from using this file

2. This personal note is adapted from Professor Marcus Darden and David Paoletti. Please contact us to delete this file if you think your rights have been violated.

3. This work is licensed under a Creative Commons Attribution 4.0 International License.

---

Data Structures and Abstract Data Types

• Need a way to store and organize data in order to faciliate access and modifications.

• An abstract data type (ADT) combines data with valid operations and their behaviors on stored data

  • Example: insert, delete, access, and so on.

  • ADTs define an interface.

• A data structure provides a concrete implementation of an ADT.

Measuring Performance

• Several design choices for implementing ADTs

  • Contiguous data (arrays or vectors)

  • Connected data (pointers, linked lists, or 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, and so on

• We formalize performance measurements with complexity analysis.

Example:

Suppose we have a singly-linked list below. How many operations are needed to insert a value at the end of this singly-linked list?

To add an extra node at the end of the singly-linked list, we first need to access the first three nodes, then check whether the node has a next pointer that is a nullptr. There are 6 steps here. Once we find out the valid place to insert, we need to create a new node, insert value, and update the singly linked list. There are 9 steps here.

Try it out:

Open in new window

If we generalize our time complexity, which means if we have a singly-linked list with $n$ nodes, then there are $2 \times n + 3$ steps to insert a node at the end of the singly-linked list.

Note: Linear function is important - coefficients and constants don't matter much. If we use Big-O notation, we can say this function push_back() has $O(n)$ (linear) time complexity.

Choosing a Data Structure for a Given Application

• What to look for

  • The right operations (example: add_elt, remove_elt)

  • The right behavior (example: push_back, pop_back)

  • The right trade-offs for runtime complexities

  • Memory overhead

• Potential concern

  • Limiting interface to avoid problems (example: no insert_mid)

• Examples:

  • Order tracking at a fast food drive-through (pipeline)

  • Interrupted phone calls to a receptionist

  • A todo list

Stack ADT

i. Interface

Supports insertion / removal in last in first out (LIFO) order.

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 the stack
empty()	Check if stack has no elements

Examples:

• Web browser's "back" feature

• Text editor's "Undo" feature

• Function calls in C++

ii. Implementation

Method	Contiguous Implementation	Linked Implementation
push(object)	1. If needed, allocate a bigger array and copy data 2. Add new element at top_ptr, increment top_ptr	Insert new node at head_ptr, increment size
pop()	Decrement top_ptr	Delete node at head_ptr, decrement size
object &top()	Dereference top_ptr - 1	Dereference head_ptr
size()	Subtract base_ptr from top_ptr pointer	Return size
empty()	Check if base_ptr == top_ptr	Check if size == 0 or head_ptr == nullptr

Note:

• Contiguous implementation includes ADTs such as array and vector:

• Linked implementation includes ADT such as singly linked list:

iii. Time Complexity

Method	Contiguous Implementation	Linked Implementation
push(object)	Constant (linear when resizing vector)	Constant
pop()	Constant	Constant
object &top()	Constant	Constant
size()	Constant	Constant (with tracked size)
empty()	Constant	Constant

• 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

  • Pointers between nodes as well as the actual data payload

iv. Library

• Use the C++ STL stack: #include <stack>

• For a stack, we can choose the following containers:

  • std::deque<> (Default)

  • std::list<> (Optional, doubly-linked list)

  • std::vector<> (Optional)

• All operations are implemented generically on top of the given container (no specialized code based on given container)

Queue ADT

i. Interface

Supports insersion / removal in first in first out (FIFO) order.

Method	Description
push(object)	Add element to back of queue
pop()	Remove element at front of queue
object &top()	Return reference to element at front of queue
size()	Number of elements in the queue
empty()	Check if queue has no elements

Example:

• Waiting in line for lunch

• Adding songs to the end of a playlist

ii. Implementation

Method	Contiguous Implementation	Linked 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	Append node after tail_ptr, increment size
pop()	Increment front_idx, decrement size	Delete node at head_ptr, decrement size
object &top()	Return reference to element at front_idx	Dereference head_ptr
size()	Return size	Return size
empty()	Check if size == 0	Return head_ptr == nullptr

Note:

• Contiguous implementation includes ADTs such as array and vector:

• Linked implementation includes singly-linked list:

iii. Time Complexity

Method	Contiguous Implementation	Linked Implementation
push(object)	Constant (linear when resizing vector)	Constant
pop()	Constant	Constant
object &top()	Constant	Constant
size()	Constant	Constant (with tracked size)
empty()	Constant	Constant

• 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

  • Pointers between nodes as well as the actual data payload

iv. Library

• Use the C++ STL stack: #include <queue>

• For a queue, we can choose the following containers:

  • std::deque<> (Default)

  • std::list<> (Optional, doubly-linked list)

• All operations are implemented generically on top of the given container (no specialized code based on given container)

Deque ADT

i. Introduction

• "Deque" is an abbreviation of Double-Ended Queue.

• "Dequeue" is another name for removing something from a 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.

• Allows efficient insertion and removal from the front and the back

• The following are some methods of the deque ADT:

  • push_front(item): adds a new item to the front of the deque

  • push_back(item): adds a new item to the back of the deque

  • pop_front(): removes the front item from the deque

  • pop_back(): removes the rear item from the deque

  • front(): returns the front item

  • back(): returns the rear item

  • size(): returns the number of items in the deque

  • empty(): tests to see whether the deque is empty

• We can traverse a deque using iterator

• STL includes constant time operator[]()

ii. Simple Deque Implementation

• Contiguous (circulat buffer)

  • front_idx and back_idx both get incremented / decremented

• Linked (Doubly-linked list)

  • Singly-linked does not support efficient removal

  • Other operations map directly to doubly-linked list operations

iii. Library

• Use #include <deque>

• Stack / Queue-like behavior at both ends

• Random access with [] or .at()

Priority Queue

i. Introduction

• Each datum paired with a priority value

  • Priority values are usually numbers

  • Should be able to compare pirority values (<)

• Supports insertion of data and inspection

• Supports removal of datum with highest priority

  • "Most important" determined by given ordering

Example:

1. Emergency Call Center

• Operators receives 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

2. Hospital queue for arriving patients

3. Load balancing on servers

ii. Interface

Supports insertion, with removal in descending priority order.

Method	Description
push(object)	Add object to priority queue
pop()	Remove highest priority element
const object &top()	Return a reference to highest priority element
size()	Number of elements in the priority queue
empty()	Check if priority queue has no elements

iii. Time Complexity

	Insert	Remove
Unordered sequence containeer	Constant	Linear
Sorted sequence container	Linear	Constant
Heap	Logarithmic	Logarithmic
Array of linked lists (for priorities f small integers)	Constant	Constant

Array of linked list looks like the following, where the priority values are used as index values in array.

iv. A Customizable Container

• By default, std::priority_queue<> uses std::less<> to determine relative priority of two elements.

• A "default priority queue" is a "max-priority queue", where the largest element has highest priority.

• If a "min-priority queue" is desired, customize with std::greater<>, so the smallest element has highest priority.

• If the priority queue 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.

v. std::priority_queue<>

• STL will maintain a Heap in any random access container

  • #include <queue>

• Common std::priority_queue<> declarations

  • "Max" priority queue uses std::less<>: std::priority_queue<T> myPQ;

  • Priority queue uses a custom comparator type COMP: std::priority_queue<T, vector<T>, COMP> myPQ;

• Manual priority queue implementation with standard library functions

  • #include <algorithm>

  • std::make_heap()

  • std::push_heap()

  • std::pop_heap()

Generating Permutations

Given $N$ elements, generate all $N$-elelment permutations

• In gredients of a solution

  • One recursive function

  • One stack

  • One queue

• Move elements between the two containers

Example:

Input: {1, 2, 3}
Output: {
  {1, 2, 3},
  {1, 3, 2},
  {2, 3, 1},
  {2, 1, 3},
  {3, 1, 2},
  {3, 2, 1}
}

1. Helper Function Implementation

 1     template <typename T>
 2     ostream &operator<<(ostream &out, const stack<T> &s) { 
 3       // display the contents of a stack on a single line 
 4       // e.g., cout << my_stack << endl; 
 5       stack<T> tmpStack = s; // deep copy
 6       while (!tmpStack.empty()) {
 7         out << tmpStack.top() << ' ';
 8         tmpStack.pop(); 
 9       } // while
10       return out; 
11     } // operator<<()

2. Helper Function Implementation (Better)

 1     template<typename T>
 2     ostream &operator<<(ostream &output, const vector<T> &v) {
 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<<()

3. Permutation Implementation

 1     template <typename T>
 2     void genPerms(vector<T> &perm, deque<T> &unused) {
 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()

4. Sample Driver

 1     int main() {
 2       size_t n;
 3       cout << "Enter n: " << flush;
 4       while (!(cin >> n)) {  // leep going while NO integer
 5         cin.clear();
 6         cin.ignore(numeric_limits<streamsize>::max(), '\n');
 7         cout << "Enter n: " << flush;
 8       }  // while
 9  
10       vector<size_t> perm;
11       deque<size_t> unused(n);
12       iota(unused.begin(), unused.end(), 1);
13       genPerms(perm, unused);
14       return 0;
15     }  // main

© Sample Academy