Chapter 10.1

Initially empty stack S
|-------+---+---+---+---+---+---|
| S     | 1 | 2 | 3 | 4 | 5 | 6 |
|-------+---+---+---+---+---+---|
| top=0 |   |   |   |   |   |   |
|-------+---+---+---+---+---+---|

PUSH(S, 4)
|-------+---+---+---+---+---+---|
| S     | 1 | 2 | 3 | 4 | 5 | 6 |
|-------+---+---+---+---+---+---|
| top=1 | 4 |   |   |   |   |   |
|-------+---+---+---+---+---+---|

PUSH(S, 1)
|-------+---+---+---+---+---+---|
| S     | 1 | 2 | 3 | 4 | 5 | 6 |
|-------+---+---+---+---+---+---|
| top=2 | 4 | 1 |   |   |   |   |
|-------+---+---+---+---+---+---|

PUSH(S, 3)
|-------+---+---+---+---+---+---|
| S     | 1 | 2 | 3 | 4 | 5 | 6 |
|-------+---+---+---+---+---+---|
| top=3 | 4 | 1 | 3 |   |   |   |
|-------+---+---+---+---+---+---|

POP(S) -> 3
|-------+---+---+---+---+---+---|
| S     | 1 | 2 | 3 | 4 | 5 | 6 |
|-------+---+---+---+---+---+---|
| top=2 | 4 | 1 | 3 |   |   |   |
|-------+---+---+---+---+---+---|

PUSH(S, 8)
|-------+---+---+---+---+---+---|
| S     | 1 | 2 | 3 | 4 | 5 | 6 |
|-------+---+---+---+---+---+---|
| top=3 | 4 | 1 | 8 |   |   |   |
|-------+---+---+---+---+---+---|

POP(S) -> 8
|-------+---+---+---+---+---+---|
| S     | 1 | 2 | 3 | 4 | 5 | 6 |
|-------+---+---+---+---+---+---|
| top=2 | 4 | 1 | 8 |   |   |   |
|-------+---+---+---+---+---+---|

We could store the elements of one stack from A[1] up to A[n], and store the elements of another stack from A[n] down to A[1].

Initially empty queue Q
|---------------+---+---+---+---+---+---|
| Q             | 1 | 2 | 3 | 4 | 5 | 6 |
|---------------+---+---+---+---+---+---|
| head=1 tail=1 |   |   |   |   |   |   |
|---------------+---+---+---+---+---+---|

ENQUEUE(Q, 4)
|---------------+---+---+---+---+---+---|
| Q             | 1 | 2 | 3 | 4 | 5 | 6 |
|---------------+---+---+---+---+---+---|
| head=1 tail=2 | 4 |   |   |   |   |   |
|---------------+---+---+---+---+---+---|

ENQUEUE(Q, 1)
|---------------+---+---+---+---+---+---|
| Q             | 1 | 2 | 3 | 4 | 5 | 6 |
|---------------+---+---+---+---+---+---|
| head=1 tail=3 | 4 | 1 |   |   |   |   |
|---------------+---+---+---+---+---+---|

ENQUEUE(Q, 3)
|---------------+---+---+---+---+---+---|
| Q             | 1 | 2 | 3 | 4 | 5 | 6 |
|---------------+---+---+---+---+---+---|
| head=1 tail=4 | 4 | 1 | 3 |   |   |   |
|---------------+---+---+---+---+---+---|

DEQUEUE(Q) -> 4
|---------------+---+---+---+---+---+---|
| Q             | 1 | 2 | 3 | 4 | 5 | 6 |
|---------------+---+---+---+---+---+---|
| head=2 tail=4 | 4 | 1 | 3 |   |   |   |
|---------------+---+---+---+---+---+---|

ENQUEUE(Q, 8)
|---------------+---+---+---+---+---+---|
| Q             | 1 | 2 | 3 | 4 | 5 | 6 |
|---------------+---+---+---+---+---+---|
| head=2 tail=5 | 4 | 1 | 3 | 8 |   |   |
|---------------+---+---+---+---+---+---|

DEQUEUE(Q) -> 1
|---------------+---+---+---+---+---+---|
| Q             | 1 | 2 | 3 | 4 | 5 | 6 |
|---------------+---+---+---+---+---+---|
| head=3 tail=5 | 4 | 1 | 3 | 8 |   |   |
|---------------+---+---+---+---+---+---|

QUEUE-EMPTY?(Q)
    return Q.head == Q.tail

QUEUE-FULL?(Q)
    if Q.head == 1
        return Q.tail == Q.length
    return Q.head == Q.tail + 1

ENQUEUE(Q, x)
    if QUEUE-FULL?(Q)
        error "the queue overflows"
    Q[Q.tail] = x
    if Q[Q.tail] == Q.length
        Q.tail = 1
    else Q.tail = Q.tail + 1

DEQUEUE(Q)
    if QUEUE-EMPTY?(Q)
        error "the queue underflows"
    x = Q[Q.head]
    if Q.head == Q.length
        Q.head = 1
    else Q.head = Q.head + 1
    return x

The ENQUEUE and DEQUEUE operations of deque are same as those of queue.

ENQUEUE-COUNTER(Q, x)
    if QUEUE-FULL?(Q)
        error "the queue overflows"
    if Q.head == 1
        Q.head = Q.length
    else Q.head = Q.head - 1
    Q[Q.head] = x

DEQUEUE-COUNTER(Q)
    if QUEUE-EMPTY?(Q)
        error "the queue underflows"
    if Q.tail == 1
        Q.tail = Q.length
    else Q.tail = Q.tail - 1
    return Q[Q.tail]

Assume the queue Q has two internal stacks Q.S1 and Q.S2.

ENQUEUE(Q, x)
    PUSH(Q.S1, x)

DEQUEUE(Q)
    if STACK-EMPTY(Q.S2)
        if STACK-EMPTY?(Q.S1)
            error "the queue underflows"
        else while not STACK-EMPTY?(Q.S1)
                 PUSH(Q.S2, POP(Q.S1))
    return POP(Q.S2)

The ENQUEUE operation takes \(O(1)\) running time, the DEQUEUE operation takes \(O(n)\) worst-case running time and \(O(1)\) running time on average.

Assume the stack S has two internal queues S.Q1 and S.Q2, and the queue supports QUEUE-EMPTY? operation.

PUSH(S, x)
    if QUEUE-FULL?(S.Q1)
        error "the stack overflows"
    ENQUEUE(S.Q1)

POP(S)
    if QUEUE-EMPTY?(S.Q1)
        error "the stack underflows"
    while not QUEUE-EMPTY(S.Q1)
        x = DEQUEUE(S.Q1)
        ENQUEUE(S.Q2, x)
    Q = S.Q1
    S.Q1 = S.Q2
    S.Q2 = Q
    return x