Stacks and queues using arrays

Learning outcomes

Implement bounded stack and queue operations, evaluate a postfix expression, and distinguish circular queues, deques and priority queues.

6.1 Stack operations

A stack follows last in, first out (LIFO). Push adds an item at the top; pop removes it; peek observes it without removal. With an array and a count size, occupied slots are [0, size). Push writes a[size] then increases size. Pop decreases size then returns a[size].

Check size == capacity before push and size == 0 before pop or peek. A failed operation must not change the stack. Each successful operation takes Θ(1) time in a fixed-capacity array.

6.2 Expressions and the operand order

To evaluate a binary postfix expression, scan tokens left to right. Push each operand. At an operator, pop the right operand first, then the left; compute left operator right and push the result. Reject an operator with fewer than two operands and reject an expression that ends with anything other than one result. Also validate tokens and arithmetic operations such as division by zero.

For infix-to-postfix conversion, output operands immediately. Keep operators on a stack. Before pushing a new operator, pop operators of higher precedence, or equal precedence when the new operator is left-associative. Push (; at ), pop until the matching ( and discard that pair. At the end, pop remaining operators. Mismatched parentheses are errors. Associativity matters for any right-associative operator included in the expression language; C's ^ is bitwise XOR, not exponentiation.

For a mathematical expression language in which ↑ denotes right-associative exponentiation, A ↑ B ↑ C means A ↑ (B ↑ C). Its postfix form is A B C ↑ ↑; popping an equal-precedence ↑ too early would instead impose left association. A unary function such as log consumes one operand, so log(A + B) becomes A B + log. Extend the evaluator's arity checks for such functions; the binary-only algorithm above is not sufficient for them.

Other stack uses include delimiter matching, depth-first search and backtracking. Real source-code delimiter checking must understand strings and comments; counting every bracket character is not a complete parser. To convert 14 to binary, successive remainders are 0, 1, 1, 1; popping them gives 1110. Zero needs its own output case.

6.3 Queue operations

A queue follows first in, first out (FIFO). Enqueue inserts at the rear; dequeue removes from the front. Printer requests, buffers and breadth-first search use this ordering.

A simple non-circular array implementation advances front and rear only to the right. When rear reaches the array end, earlier vacated slots cannot be reused without shifting or resetting. This is a limitation of that implementation, not of the queue ADT.

6.4 Circular queue with an explicit count

Use a strictly positive capacity C, front index f and count n. The next insertion index is (f + n) % C. Enqueue writes there and increments n. Dequeue reads slot f, sets f = (f + 1) % C, and decrements n. Empty means n = 0; full means n = C. All C slots are usable.

The dash denotes an unused logical slot; bytes need not be cleared. Never mix these full/empty conditions with a different convention that deliberately leaves one slot unused. Both designs work, but their invariants differ.

6.5 Deques and priority queues

A deque permits insertion and removal at both ends. A circular array can implement all four operations in constant time. An input-restricted deque permits insertion at only one end; an output-restricted deque permits removal at only one end.

A priority queue removes the item with the highest defined priority, not necessarily the earliest arrival. Specify whether a smaller or larger numeric value means higher priority and how equal priorities are handled. A stable policy uses FIFO within equal priorities.

These are implementation costs, not universal costs for the ADT. A binary heap supports O(1) inspection of the extreme key at its root.

Practice

1. Evaluate postfix 8 3 - 2 * and explain why operand order matters.
2. A capacity-four ring has front 3 and count 2. Which slots are occupied and where is the next enqueue?
3. Compare a deque with a priority queue using one application for each.
4. Design tests for full-to-nonfull and one-element-to-empty transitions.
5. Convert (A + B) * C - D to postfix.

/* C11. bounded stack and circular queue. */
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#define CAP 4

typedef struct { int data[CAP]; size_t size; } Stack;
typedef struct { int data[CAP]; size_t front, size; } Queue;
static bool push(Stack *s, int value)
{
    if (s->size == CAP) return false;
    s->data[s->size++] = value;
    return true;
}
static bool pop(Stack *s, int *out)
{
    if (s->size == 0) return false;
    *out = s->data[--s->size];
    return true;
}
static bool peek(const Stack *s, int *out)
{
    if (s->size == 0) return false;
    *out = s->data[s->size - 1];
    return true;
}
static bool enqueue(Queue *q, int value)
{
    if (q->size == CAP) return false;
    size_t rear = (q->front + q->size) % CAP;
    q->data[rear] = value;
    ++q->size;
    return true;
}
static bool dequeue(Queue *q, int *out)
{
    if (q->size == 0) return false;
    *out = q->data[q->front];
    q->front = (q->front + 1) % CAP;
    --q->size;
    return true;
}
int main(void)
{
    Stack s = {{0}, 0}; Queue q = {{0}, 0, 0}; int value = 0;
    assert(!pop(&s, &value) && !peek(&s, &value));
    for (int i = 1; i <= CAP; ++i) assert(push(&s, i));
    assert(!push(&s, 5)); assert(peek(&s, &value) && value == 4);
    printf("Stack:");
    for (int i = CAP; i > 0; --i) {
        assert(pop(&s, &value) && value == i); printf(" %d", value);
    }
    putchar('\n'); assert(!pop(&s, &value));
    assert(!dequeue(&q, &value));
    for (int i = 1; i <= CAP; ++i) assert(enqueue(&q, i));
    assert(!enqueue(&q, 5));
    assert(dequeue(&q, &value) && value == 1);
    assert(dequeue(&q, &value) && value == 2);
    assert(enqueue(&q, 5) && enqueue(&q, 6));
    printf("Queue after wraparound:");
    for (int i = 3; i <= 6; ++i) {
        assert(dequeue(&q, &value) && value == i); printf(" %d", value);
    }
    putchar('\n'); assert(!dequeue(&q, &value));
    for (int i = 0; i < 100; ++i) {
        assert(enqueue(&q, i)); assert(dequeue(&q, &value) && value == i);
    }
    puts("stack/queue tests passed");
    return 0;
}