Stacks and queues (array-backed)

Two ways to hold items

A stack and a queue both hold a line of items, but they differ in which item comes out next.
A stack is LIFO: Last In, First Out — like a pile of plates.
A queue is FIFO: First In, First Out — like a line of people.

A stack is LIFO

push adds an item on top. pop removes and returns the top item. peek looks at the top without removing it.
The last item you pushed is the first one you pop.
We store the items in an array data and an index top that counts how many are in.

Array-backed stack

With top as the count, the top item is at data[top - 1].
push: write at data[top], then top++. pop: top--, then return data[top].
(For these tasks the array is big enough; you do not need to check for "full".)

A queue is FIFO

enqueue adds an item at the back. dequeue removes and returns the item at the front.
The first item you enqueue is the first one you dequeue.
We keep two indexes: front (next to leave) and back (next free slot).

Array-backed queue

enqueue: write at data[back], then back++. dequeue: read data[front], then front++, and return it.
front chases back as items come and go.
(For these tasks the array is big enough; you do not need to wrap around or check for "empty".)

Common mistakes

A stack is last-in-first-out; a queue is first-in-first-out.
Check the structure is not empty before you pop or dequeue.

Now you try

The Stack and Queue structs are given in the starter. Use s->top, q->front, and q->back.
Do not write a main — the checker provides one.

Explore

Stacks and queues

A stack is LIFO; a queue is FIFO. Step through the operations.

The Stack struct (with data and a count top) is given. Complete void push(Stack *s, int v) and int pop(Stack *s) so the stack is LIFO. Do not write a main.

typedef struct {
    int data[64];
    int top;
} Stack;

/* push and pop so the stack is LIFO. Do not write main(). */
void push(Stack *s, int v) {
    /* store v at data[top], then top++ */
}

int pop(Stack *s) {
    return 0;   /* top--, then return data[top] */
}

Click Run to see the output here.

The Stack struct is given. Complete int peek(const Stack *s) so it returns the top item without removing it. Assume the stack is not empty. Do not write a main.

typedef struct {
    int data[64];
    int top;
} Stack;

/* Return the top item without removing it. Do not write main(). */
int peek(const Stack *s) {
    return 0;   /* the top item is at data[top - 1] */
}

Click Run to see the output here.

The Queue struct (with data, front, and back) is given. Complete void enqueue(Queue *q, int v) and int dequeue(Queue *q) so the queue is FIFO. Do not write a main.

typedef struct {
    int data[64];
    int front;
    int back;
} Queue;

/* enqueue and dequeue so the queue is FIFO. Do not write main(). */
void enqueue(Queue *q, int v) {
    /* store v at data[back], then back++ */
}

int dequeue(Queue *q) {
    return 0;   /* read data[front], then front++ */
}

Click Run to see the output here.