lOMoARcPSD|33062721
CP264 Final Review
Data Structures II (Wilfrid Laurier University)
Scan to open on Studocu
Studocu is not sponsored or endorsed by any college or university
Downloaded by Bal Boi ()
, lOMoARcPSD|33062721
CP264 Final Review
Queue
Abstract Queue: Linearly ordered collection of data elements with enqueue, dequeue, and peek operations
o Enqueue operation inserts element into collection
Linearly order of elements determined by time they're inserted
Front element is earliest inserted element; Rear is last inserted element
o Dequeue operation removes/deletes front element
o Peek operation gets front element
Queue Data Structure: Implementation of abstract queue
Queue Characteristic → First-In-First-Out (FIFO): Deletes first inserted element
Time and space complexities for queue operations → time O(1), space O(1)
Array Queue
Simple Array Queue: Queue implementation with array representation, where front and rear
variable represent index positions that deletions and insertions are done respectively
Drawbacks:
o Length of queue is bound by length of its array
o Wastes space if length of queue is shorter than length of array
Linked List Queue
Fixes drawbacks of array queues → length is dynamic + doesn’t waste space
Linked List Queue: Uses singly linked list to store queue data values; uses two pointers front and
rear to represent front and rear positions
Deques (Double-ended Queue)
Dequeue (Double-ended Queue): Queue where elements can be inserted/deleted at either end
Priority Queue
Priority Queue: Queue where each element is assigned a priority; priority of element used to
determine order in which elements are processed
Rule of processing elements of priority queue:
1. Element with higher priority is processed before element with lower priority
2. Two elements of same priority processed by first come first serve order
Applications of Queues
Whenever an algorithm needs to remember data items and a FIFIO is required for item processing,
queue data structure can be an option
1. Used to store intermediate data within algorithm for FIFO retrieval (e.g. Breadth-first search)
2. Used as waiting lists for single shared resource (e.g. printer, disk, CPU, network device)
3. Used in OS for handling interrupts; If interrupts must be handled in order of arrival, FIFO queue
is appropriate data structure
4. Used to transfer data asynchronously (e.g. Pipes, file I/O, sockets)
5. Used in simulations for services
6. Used for play lists, adding songs to the end, playing from the front of the list.
7. Priority queues are in OS for processes execution management.
8. Used to remember the path of explorations if FIFO retrieval is needed.
1
Downloaded by Bal Boi ()
, lOMoARcPSD|33062721
Stack
Abstract Stack: Linearly ordered collections of data elements with push, pop, and peek operations
Stack Characteristic → Last-In-First-Out (LIFO): Pops the most recently pushed element
Stack Data Structure: Implementation of abstract stack
Stack: Linear data structure with push and pop operations satisfying LIFO property
Why is only one variable needed for accessing a stack data structure?
1. Stack operations only work on one side of the stack list, one variable does the jobs.
2. It’s more time efficient to maintain one variable than more variables.
3. It’s more space efficient to use one variable than more stack data structure.
2. Time and space complexities for stack operations -> time O(1), space O(1)
Array Stack
Array Stack: Stack representation by an array, top variable represents index position where
push, pop, and peek operations are done
Linked List Stack
Linked List Stack: Use singly linked list to implement stack, pointer top points to first node
Array vs. Linked List Stack
Array Stack Linked List Stack
Pros: Pros:
Easy to implement No size constraint
More time efficient in operation More space efficient with
dynamic memory allocation
Cons: Cons:
Limitation on maximum size Use more time on operations
Less space efficient when stack
size is less than array size
When is it better to an array stack or a linked list stack?
o Applying stacks in an application, if the maximum size of a stack is known and not big,
then an array stack is a better choice, otherwise a linked list stack is preferred.
Applications of Stacks
1. Back tracking
2. Reversing a list
3. Parentheses checking
4. Infix/Prefix/Postfix expressions and evaluation
5. Conversion from infix to postfix expressions
6. Function call stack and recursion functions
2
Downloaded by Bal Boi ()
CP264 Final Review
Data Structures II (Wilfrid Laurier University)
Scan to open on Studocu
Studocu is not sponsored or endorsed by any college or university
Downloaded by Bal Boi ()
, lOMoARcPSD|33062721
CP264 Final Review
Queue
Abstract Queue: Linearly ordered collection of data elements with enqueue, dequeue, and peek operations
o Enqueue operation inserts element into collection
Linearly order of elements determined by time they're inserted
Front element is earliest inserted element; Rear is last inserted element
o Dequeue operation removes/deletes front element
o Peek operation gets front element
Queue Data Structure: Implementation of abstract queue
Queue Characteristic → First-In-First-Out (FIFO): Deletes first inserted element
Time and space complexities for queue operations → time O(1), space O(1)
Array Queue
Simple Array Queue: Queue implementation with array representation, where front and rear
variable represent index positions that deletions and insertions are done respectively
Drawbacks:
o Length of queue is bound by length of its array
o Wastes space if length of queue is shorter than length of array
Linked List Queue
Fixes drawbacks of array queues → length is dynamic + doesn’t waste space
Linked List Queue: Uses singly linked list to store queue data values; uses two pointers front and
rear to represent front and rear positions
Deques (Double-ended Queue)
Dequeue (Double-ended Queue): Queue where elements can be inserted/deleted at either end
Priority Queue
Priority Queue: Queue where each element is assigned a priority; priority of element used to
determine order in which elements are processed
Rule of processing elements of priority queue:
1. Element with higher priority is processed before element with lower priority
2. Two elements of same priority processed by first come first serve order
Applications of Queues
Whenever an algorithm needs to remember data items and a FIFIO is required for item processing,
queue data structure can be an option
1. Used to store intermediate data within algorithm for FIFO retrieval (e.g. Breadth-first search)
2. Used as waiting lists for single shared resource (e.g. printer, disk, CPU, network device)
3. Used in OS for handling interrupts; If interrupts must be handled in order of arrival, FIFO queue
is appropriate data structure
4. Used to transfer data asynchronously (e.g. Pipes, file I/O, sockets)
5. Used in simulations for services
6. Used for play lists, adding songs to the end, playing from the front of the list.
7. Priority queues are in OS for processes execution management.
8. Used to remember the path of explorations if FIFO retrieval is needed.
1
Downloaded by Bal Boi ()
, lOMoARcPSD|33062721
Stack
Abstract Stack: Linearly ordered collections of data elements with push, pop, and peek operations
Stack Characteristic → Last-In-First-Out (LIFO): Pops the most recently pushed element
Stack Data Structure: Implementation of abstract stack
Stack: Linear data structure with push and pop operations satisfying LIFO property
Why is only one variable needed for accessing a stack data structure?
1. Stack operations only work on one side of the stack list, one variable does the jobs.
2. It’s more time efficient to maintain one variable than more variables.
3. It’s more space efficient to use one variable than more stack data structure.
2. Time and space complexities for stack operations -> time O(1), space O(1)
Array Stack
Array Stack: Stack representation by an array, top variable represents index position where
push, pop, and peek operations are done
Linked List Stack
Linked List Stack: Use singly linked list to implement stack, pointer top points to first node
Array vs. Linked List Stack
Array Stack Linked List Stack
Pros: Pros:
Easy to implement No size constraint
More time efficient in operation More space efficient with
dynamic memory allocation
Cons: Cons:
Limitation on maximum size Use more time on operations
Less space efficient when stack
size is less than array size
When is it better to an array stack or a linked list stack?
o Applying stacks in an application, if the maximum size of a stack is known and not big,
then an array stack is a better choice, otherwise a linked list stack is preferred.
Applications of Stacks
1. Back tracking
2. Reversing a list
3. Parentheses checking
4. Infix/Prefix/Postfix expressions and evaluation
5. Conversion from infix to postfix expressions
6. Function call stack and recursion functions
2
Downloaded by Bal Boi ()
