Editing Amortized analysis (section)

===Queue===
Shown is a Python3 implementation of a [[Queue (abstract data type)|queue]], a [[FIFO (computing and electronics)|FIFO data structure]]:
<syntaxhighlight lang="python">
class Queue:
    # Initialize the queue with two empty lists
    def __init__(self):
        self.input = []  # Stores elements that are enqueued
        self.output = []  # Stores elements that are dequeued

    def enqueue(self, element):
        self.input.append(element)  # Append the element to the input list

    def dequeue(self):
        if not self.output:  # If the output list is empty
            # Transfer all elements from the input list to the output list, reversing the order
            while self.input:  # While the input list is not empty
                self.output.append(
                    self.input.pop()
                )  # Pop the last element from the input list and append it to the output list

        return self.output.pop()  # Pop and return the last element from the output list
</syntaxhighlight>

The enqueue operation just pushes an element onto the input array; this operation does not depend on the lengths of either input or output and therefore runs in constant time.

However the dequeue operation is more complicated.  If the output array already has some elements in it, then dequeue runs in constant time; otherwise, dequeue takes {{tmath|O(n)}} time to add all the elements onto the output array from the input array, where ''n'' is the current length of the input array.  After copying ''n'' elements from input, we can perform ''n'' dequeue operations, each taking constant time, before the output array is empty again. Thus, we can perform a sequence of ''n'' dequeue operations in only {{tmath|O(n)}} time, which implies that the amortized time of each dequeue operation is {{tmath|O(1)}}.<ref name=Grossman>{{cite web|last1=Grossman|first1=Dan|title=CSE332: Data Abstractions|url=http://courses.cs.washington.edu/courses/cse332/10sp/lectures/lecture21.pdf|website=cs.washington.edu|access-date=14 March 2015}}</ref>

Alternatively, we can charge the cost of copying any item from the input array to the output array to the earlier enqueue operation for that item.  This charging scheme doubles the amortized time for enqueue but reduces the amortized time for dequeue to {{tmath|O(1)}}.