How to Win Coding Competitions: Secrets of Champions
Week 2: Computational complexity. Linear data structures
Lecture 5: Stack. Queue. Deque
Pavel Krotkov
Saint Petersburg 2016
General overview
Stack, Queue and Deque are just interfaces.
2 / 10
General overview
Stack, Queue and Deque are just interfaces.
I sometimes it’s reasonable to limit set of possible operations on data structure
2 / 10
General overview
Stack, Queue and Deque are just interfaces.
I sometimes it’s reasonable to limit set of possible operations on data structure
I implementation of Stack and Queue can be based on Vector or Array
2 / 10
General overview
Stack, Queue and Deque are just interfaces.
I sometimes it’s reasonable to limit set of possible operations on data structure
I implementation of Stack and Queue can be based on Vector or Array
I different implementations will have different properties
2 / 10
Stack overview
Stack has only two possible operations.
I push — inserting element to the end of structure
3 / 10
Stack overview
Stack has only two possible operations.
I push — inserting element to the end of structure
I pop — removing element from the end of structure and returning its value
3 / 10
Stack overview
Stack has only two possible operations.
I push — inserting element to the end of structure
I pop — removing element from the end of structure and returning its value
Push operation
8
5 5
2 2
6 6
3 3
3 / 10
Stack overview
Pop operation
8
5 5
2 2
6 6
3 3
4 / 10
Stack overview
Pop operation
8
5 5
2 2
6 6
3 3
The end of the structure is called top of the stack.
4 / 10
Stack analysis
Stack can be implemented with vector or with list.
I both this data structures support inserting elements to and removing elements
from the end of the structure in constant time
5 / 10
Stack analysis
Stack can be implemented with vector or with list.
I both this data structures support inserting elements to and removing elements
from the end of the structure in constant time
Stack has numerous applications in different areas.
I various graph algorithms (DFS)
5 / 10
Stack analysis
Stack can be implemented with vector or with list.
I both this data structures support inserting elements to and removing elements
from the end of the structure in constant time
Stack has numerous applications in different areas.
I various graph algorithms (DFS)
I local variables and function calls during execution of yor program are stored in
stack
5 / 10
Stack analysis
Stack can be implemented with vector or with list.
I both this data structures support inserting elements to and removing elements
from the end of the structure in constant time
Stack has numerous applications in different areas.
I various graph algorithms (DFS)
I local variables and function calls during execution of yor program are stored in
stack
I during calculation of expressions written in Reverse Polish notation
5 / 10
Stack analysis
Stack can be implemented with vector or with list.
I both this data structures support inserting elements to and removing elements
from the end of the structure in constant time
Stack has numerous applications in different areas.
I various graph algorithms (DFS)
I local variables and function calls during execution of yor program are stored in
stack
I during calculation of expressions written in Reverse Polish notation
I etc.
5 / 10
Queue overview
Queue is a list organized by FIFO (first in - first out) rule.
6 / 10
Queue overview
Queue is a list organized by FIFO (first in - first out) rule. It supports two operations:
I enqueue — inserting element to the end of structure
I dequeue — removing element from the beginning of structure
6 / 10
Queue overview
Queue is a list organized by FIFO (first in - first out) rule. It supports two operations:
I enqueue — inserting element to the end of structure
I dequeue — removing element from the beginning of structure
Enqueue operation
3 6 2 5
3 6 2 5 8
6 / 10
Queue overview
Dequeue operation
3 6 2 5 8
6 2 5 8
7 / 10
Queue overview
Dequeue operation
3 6 2 5 8
6 2 5 8
I the end of queue is called tail
7 / 10
Queue overview
Dequeue operation
3 6 2 5 8
6 2 5 8
I the end of queue is called tail
I the beginning of queue is called head
7 / 10
Queue analysis
Queue implementation
8 / 10
Queue analysis
Queue implementation
I the easiest way to implement queue is based on list
I we just need to store links to the first and last elements of list
8 / 10
Queue analysis
Queue implementation
I the easiest way to implement queue is based on list
I we just need to store links to the first and last elements of list
I queue can be implemented with array, if maximum possible size of queue is known
beforehand
I we can reuse free elements at the beginning of array for storing new elements of
queue
8 / 10
Queue analysis
Queue implementation
I the easiest way to implement queue is based on list
I we just need to store links to the first and last elements of list
I queue can be implemented with array, if maximum possible size of queue is known
beforehand
I we can reuse free elements at the beginning of array for storing new elements of
queue
I queue can be implemented with vector
I some additional techniques of removing from the beginning of vector required
8 / 10
Queue analysis
Queue implementation
I the easiest way to implement queue is based on list
I we just need to store links to the first and last elements of list
I queue can be implemented with array, if maximum possible size of queue is known
beforehand
I we can reuse free elements at the beginning of array for storing new elements of
queue
I queue can be implemented with vector
I some additional techniques of removing from the beginning of vector required
I queue with amortized constant time of operations can be implemented with two
stacks
I details of implementation can be considered as a home work
8 / 10
Queue analysis
Queue implementation
I the easiest way to implement queue is based on list
I we just need to store links to the first and last elements of list
I queue can be implemented with array, if maximum possible size of queue is known
beforehand
I we can reuse free elements at the beginning of array for storing new elements of
queue
I queue can be implemented with vector
I some additional techniques of removing from the beginning of vector required
I queue with amortized constant time of operations can be implemented with two
stacks
I details of implementation can be considered as a home work
Queue usage.
I graph algorithms (BFS)
8 / 10
Queue analysis
Queue implementation
I the easiest way to implement queue is based on list
I we just need to store links to the first and last elements of list
I queue can be implemented with array, if maximum possible size of queue is known
beforehand
I we can reuse free elements at the beginning of array for storing new elements of
queue
I queue can be implemented with vector
I some additional techniques of removing from the beginning of vector required
I queue with amortized constant time of operations can be implemented with two
stacks
I details of implementation can be considered as a home work
Queue usage.
I graph algorithms (BFS)
I processing some queries in order of their arrival
8 / 10
Deque overview
Deque is a queue with allowed operations of removing element from the end and
inserting element to the beginning.
I implementation details are very similar to queue implementation details
I doubly linked list
I cycled array (if fixed maximum size)
I vector
9 / 10
Deque overview
Deque is a queue with allowed operations of removing element from the end and
inserting element to the beginning.
I implementation details are very similar to queue implementation details
I doubly linked list
I cycled array (if fixed maximum size)
I vector
I can be used as stack and as queue at the same time
9 / 10
Thank you
for your attention!
10 / 10
