Stack & Queue
Stacks
Stack is an abstract data type, LIFOs (Last-In-First-Out).
1. Basic operation
push(x)
=insert_beg
pop()
=delete_beg
is_empty()
=is_empty
(for linked list)
2. Stacks as arrays
To avoid calling allocate_memory
all the time, we need to know the maximum size of the stack in advance.
1 | // Initialize an empty stack: |
Queues
Queue is an abstract data type, FIFOs (First-In-First-Out)
![](/2020/04/13/ds2/queue.png)
1. Basic operation
enqueue(x)
dequeue()
is_empty()
2. Queue as a linked list
In this case, all operations take constant time.
![](/2020/04/13/ds2/QasL.png)
enqueue = insert_end
dequeue = delete_beg
3. Queue stored in an array: Circular queue
1 | // Initialize an empty queue: |
1 | boolean is_empty(){ |
Other
1. div
and mod
Note that a div b
is always an integer and
(a div b)*b + a mod b = a
.
Consequently: