Array representation

Use an array of capacity CAP and an integer top initialised to -1. Empty means top == -1. Full means top == CAP - 1. Valid stored elements occupy indices 0 through top.

Algorithms

1. push(x): reject a full stack; otherwise increment top and store x.
2. pop: reject an empty stack; otherwise return a[top] and decrement top.
3. peek: reject an empty stack; otherwise read a[top] without removing it.

Failure handling

Overflow means a push cannot be accommodated by the chosen representation. Underflow means removal or reading was requested from an empty stack. Use a status result and a separate output parameter instead of a special data value that could also be a legitimate stored item.

Applications

Stacks support undo histories, nested calls, expression processing and backtracking. Their access order is different from a queue’s arrival-order rule. A stack is not automatically sorted by value.

Complexity

A bounded array push, pop or peek needs a fixed number of tests and assignments, so each is O(1). Storage for capacity c is O(c). Traversing or printing all n elements is O(n). The complete program demonstrates successful operations; accompanying checks also exercise empty and full cases.

Diagram or flowchart

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#define CAP 6
struct Stack { int values[CAP]; int top; };
int push(struct Stack *s, int value)
{
    if (s->top == CAP - 1) { return 0; }
    s->values[++s->top] = value; return 1;
}
int pop(struct Stack *s, int *out)
{
    if (s->top < 0) { return 0; }
    *out = s->values[s->top--]; return 1;
}
int peek(const struct Stack *s, int *out)
{
    if (s->top < 0) { return 0; }
    *out = s->values[s->top]; return 1;
}

int main(void)
{
    struct Stack s = {{0}, -1};
    int value;
    if (!push(&s, 10) || !push(&s, 20)) { puts("Full"); return 1; }
    if (pop(&s, &value)) { printf("Popped = %d\n", value); }
    if (peek(&s, &value)) { printf("Top = %d\n", value); }
    return 0;
}

Popped = 20
Top = 10

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• April/May 2023 · Q1(a) · 2 marks

  Give examples of a stack.

  Paper DS01 · page 1
• February 2024 · Q2(b) · 5 marks

  Explain array-based push and pop.

  Paper DS03 · page 1
• March 2022 · Q2(a) · 8 marks

  Write a program implementing stack operations.

  Paper DS05 · page 1

View all matching source questions →

Push

1. Allocate a node and check success before modifying the stack.
2. Store the value and set new->next to top.
3. Set top to the new node.

Pop

1. If top is NULL, report underflow.
2. Save the current top node and its value.
3. Move top to old->next.
4. Free the old owned node and return success with the saved value.

Example

Pushing 10 then 20 creates 20 → 10 → NULL. Pop removes 20 first and leaves 10 as top. Removing the only remaining node makes top NULL. This matches the same LIFO contract as the array implementation.

Capacity and ownership

There is no preset array capacity in this version, but memory is finite and malloc can fail. Calling it unlimited would be incorrect. Every successful push creates owned storage that must later be released by pop or destruction. Read the link before freeing its node.

Complexity

Each operation uses O(1) link work, excluding the allocator’s implementation-dependent cost. A linked stack with n items needs O(n) node storage, including next links. It avoids shifting elements but adds allocation overhead and less predictable physical locality than an array.

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int push(struct Node **top, int value)
{
    struct Node *node = malloc(sizeof *node);
    if (node == NULL) { return 0; }
    node->data = value; node->next = *top; *top = node; return 1;
}
int pop(struct Node **top, int *out)
{
    if (*top == NULL) { return 0; }
    struct Node *old = *top; *out = old->data; *top = old->next; free(old); return 1;
}

int main(void)
{
    struct Node *top = NULL;
    int value;
    if (!push(&top, 10) || !push(&top, 20)) {
        while (pop(&top, &value)) { }
        puts("Allocation failed"); return 1;
    }
    while (pop(&top, &value)) { printf("%d\n", value); }
    return 0;
}

20
10

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• April/May 2023 · Q2 · 10 marks

  Write and explain push and pop algorithms using a linked list.

  Paper DS01 · page 1
• August/September 2022 · Q2(b) · 7 marks

  Implement a stack using a singly linked list.

  Paper DS02 · page 1
• October 2020 · Q6(a) · 8 marks

  Write a program implementing a linked-list stack.

  Paper DS06 · page 1

View all matching source questions →

Initial state

Bottom to top: 10, 20, 50, 30, 90, 60. Capacity is 10 and the initial count is 6. The top is 60.

Operation trace

1. pop removes 60: top becomes 90.
2. push(30): top becomes 30.
3. push(40): top becomes 40.
4. pop removes 40: top becomes 30.
5. push(60): top becomes 60.
6. pop removes 60: top becomes 30.
7. pop removes that pushed 30: top becomes 90.
8. pop removes 90: top becomes the original 30.

Final state

Bottom to top: 10, 20, 50, 30. Peek is 30 and does not remove it. The count is 4. None of these operations reaches empty or exceeds capacity, so there is no underflow or overflow.

How to avoid mistakes

Record the complete remaining sequence or a clear top marker after each step. Distinguish a newly pushed 30 from an earlier equal value if labels help, but the final requested value is still 30. Never remove the bottom item for pop; that would violate LIFO.

Complexity

For k operations on the bounded array representation, each operation is O(1), so the trace requires O(k) work. This specific trace has a fixed eight operations. Writing every intermediate full stack for display can add output work beyond the stack operations themselves.

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• August/September 2022 · Q1(a) · 8 marks

  Starting stack bottom-to-top: 10, 20, 50, 30, 90, 60; capacity 10. Apply pop, push(30), push(40), pop, push(60), pop, pop, pop. Find the final peek value.

  Paper DS02 · page 1
• February 2024 · Q3(a) · 5 marks

  Starting stack bottom-to-top: 10, 20, 50, 30, 90, 60; capacity 10. Apply pop, push(30), push(40), pop, push(60), pop, pop, pop. Find the final peek value.

  Paper DS03 · page 1

View all matching source questions →

Algorithm

1. Output each operand. Push an opening parenthesis.
2. On a closing parenthesis, output operators up to its matching opening parenthesis and discard the pair.
3. For an incoming operator, output stacked operators with higher precedence; also output equal-precedence ones when the incoming operator is left-associative.
4. Push the incoming operator. At the end, output remaining operators and reject unmatched parentheses.

Worked paper expressions

A + B - C * D * E / F - G becomes AB+CD*E*F/-G-. Multiplication and division are left-associative here. In the older paper’s A+B-C*D*E$F$G, interpret $ as the stated exponent operator with right associativity. The result is AB+CD*EFG$$*-. $ is notation for this exercise, not a standard C arithmetic operator.

Grouping example

(A+B)*C becomes AB+C*. The parentheses require A+B to complete before the multiplication. Postfix needs no grouping parentheses because operand/operator order already records that grouping.

Program limits

The complete converter accepts single ASCII letters or digits as operands, binary +, -, *, / and $, parentheses and spaces. It checks operand/operator order. It does not claim to parse unary minus, decimal numbers or multi-character variable names.

Complexity

Each token is read once and each operator is pushed and popped at most once, giving O(n) token work and O(n) stack/output space. Parentheses and associativity must be handled correctly; comparing precedence alone is insufficient.

Diagram or flowchart

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <string.h>
int read_line(char s[80])
{
    if (fgets(s, 80, stdin) == NULL) { return 0; }
    char *newline = strchr(s, '\n');
    if (newline != NULL) { *newline = '\0'; return 1; }
    int ch = getchar();
    if (ch == '\n' || ch == EOF) { return 1; }
    while ((ch = getchar()) != '\n' && ch != EOF) { }
    return 0;
}
int precedence(char op)
{
    if (op == '$') { return 3; }
    if (op == '*' || op == '/') { return 2; }
    if (op == '+' || op == '-') { return 1; }
    return 0;
}
int convert(const char input[], char output[80])
{
    char stack[80]; int top = -1, used = 0, need_operand = 1;
    for (int i = 0; input[i] != '\0'; ++i) {
        char ch = input[i];
        if (ch == ' ' || ch == '\t') { continue; }
        int operand = (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9');
        if (operand) {
            if (!need_operand) { return 0; }
            output[used++] = ch; need_operand = 0;
        } else if (ch == '(') {
            if (!need_operand) { return 0; }
            stack[++top] = ch;
        } else if (ch == ')') {
            if (need_operand) { return 0; }
            while (top >= 0 && stack[top] != '(') { output[used++] = stack[top--]; }
            if (top < 0) { return 0; }
            --top;
        } else if (precedence(ch) != 0) {
            if (need_operand) { return 0; }
            while (top >= 0 && stack[top] != '(' &&
                   (precedence(stack[top]) > precedence(ch) ||
                   (precedence(stack[top]) == precedence(ch) && ch != '$'))) {
                output[used++] = stack[top--];
            }
            stack[++top] = ch; need_operand = 1;
        } else { return 0; }
    }
    if (need_operand) { return 0; }
    while (top >= 0) { if (stack[top] == '(') { return 0; } output[used++] = stack[top--]; }
    output[used] = '\0'; return 1;
}

int main(void)
{
    char input[80], output[80];
    if (!read_line(input) || !convert(input, output)) { puts("Invalid expression"); return 1; }
    puts(output);
    return 0;
}

A+B-C*D*E/F-G

AB+CD*E*F/-G-

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• February 2024 · Q3(b) · 5 marks

  Convert A + B - C * D * E / F - G to postfix.

  Paper DS03 · page 1
• March 2021 · Q1(b) · 8 marks

  Write a C program to convert infix to postfix.

  Paper DS04 · page 1
• October 2020 · Q1(b) · 8 marks

  Convert A+B-C*D*E$F$G to postfix.

  Paper DS06 · page 1

View all matching source questions →

Algorithm

1. Read one token at a time. Push a numeric operand.
2. For a binary operator, require at least two stack values.
3. Pop right, then left; compute left operator right and push the result.
4. At the end, require exactly one result.

Worked trace

For 5 3 + 6 2 / * 3 5 * +: 5 and 3 give 8; 6 and 2 give 3 by integer division; 8 * 3 gives 24; 3 and 5 give 15; 24 + 15 gives 39. The answer is 39.

Invalid expressions

Reject insufficient operands, a zero divisor, unsupported tokens or more than one remaining value. An empty expression has no result. For 2 8 -, the result is -6, not 6, because the first popped value is 8 and belongs on the right.

Program limits

The supplied program uses whitespace-separated integer tokens and +, -, *, /. Each value and intermediate result is restricted to -1000000 through 1000000. The bound makes intermediate long long multiplication safe before the result check. It rejects out-of-range conversions and malformed tokens.

Complexity

Each of n tokens causes a fixed number of stack operations, giving O(n) token work after numeric token parsing. The stack can hold O(n) values. Parsing also depends on the total input-character count. The bounded demonstration buffer limits resource use without changing the underlying algorithm.

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
int read_line(char s[80])
{
    if (fgets(s, 80, stdin) == NULL) { return 0; }
    char *newline = strchr(s, '\n');
    if (newline != NULL) { *newline = '\0'; return 1; }
    int ch = getchar();
    if (ch == '\n' || ch == EOF) { return 1; }
    while ((ch = getchar()) != '\n' && ch != EOF) { }
    return 0;
}
int evaluate(char input[], long long *out)
{
    long long stack[40]; int count = 0;
    char *token = strtok(input, " \t");
    while (token != NULL) {
        if (strlen(token) == 1 && strchr("+-*/", token[0]) != NULL) {
            if (count < 2) { return 0; }
            long long right = stack[--count], left = stack[--count], value;
            if (token[0] == '+') { value = left + right; }
            else if (token[0] == '-') { value = left - right; }
            else if (token[0] == '*') { value = left * right; }
            else { if (right == 0) { return 0; } value = left / right; }
            if (value < -1000000 || value > 1000000) { return 0; }
            stack[count++] = value;
        } else {
            char *end; errno = 0;
            long long value = strtoll(token, &end, 10);
            if (end == token || *end != '\0' || errno == ERANGE || value < -1000000 || value > 1000000 || count == 40) { return 0; }
            stack[count++] = value;
        }
        token = strtok(NULL, " \t");
    }
    if (count != 1) { return 0; }
    *out = stack[0]; return 1;
}

int main(void)
{
    char input[80];
    long long result;
    if (!read_line(input) || !evaluate(input, &result)) { puts("Invalid expression"); return 1; }
    printf("Result = %lld\n", result);
    return 0;
}

5 3 + 6 2 / * 3 5 * +

Result = 39

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• September 2021 · Q6(b) · 8 marks

  Evaluate postfix 5 3 + 6 2 / * 3 5 * +, showing steps.

  Paper DS07 · page 1

View all matching source questions →

Algorithm

1. Push each opening (, [ or { symbol.
2. For a closing symbol, reject an empty stack.
3. Pop the latest opening and require the matching type.
4. After the complete input, accept only an empty stack.

Examples

{[()]} is balanced. ([)] is not: the closing ) arrives while [ is on top. A simple equal-count check would miss that incorrect nesting. An unmatched closing symbol fails immediately, and leftover openings fail at the end.

Stack role

The last unclosed opening must be the first one closed, which is exactly LIFO order. The stack records both the number and types of pending openings. A counter alone cannot describe every nested type combination.

Scope of the program

The example checks grouping symbols in a bounded ordinary line and ignores other characters. It is not a complete C lexer: brackets inside string literals or comments are not specially ignored. State this distinction when applying the algorithm to source-code validation.

Complexity

A line of n characters is scanned once. Each bracket is pushed or popped once, giving O(n) time. If every character is an opening symbol, the pending stack can contain O(n) symbols. The fixed-size demonstration stack matches its input capacity to avoid overflow.

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <string.h>
int read_line(char s[80])
{
    if (fgets(s, 80, stdin) == NULL) { return 0; }
    char *newline = strchr(s, '\n');
    if (newline != NULL) { *newline = '\0'; return 1; }
    int ch = getchar();
    if (ch == '\n' || ch == EOF) { return 1; }
    while ((ch = getchar()) != '\n' && ch != EOF) { }
    return 0;
}
int balanced(const char text[])
{
    char stack[80]; int top = -1;
    for (int i = 0; text[i] != '\0'; ++i) {
        char ch = text[i];
        if (ch == '(' || ch == '[' || ch == '{') { stack[++top] = ch; }
        else if (ch == ')' || ch == ']' || ch == '}') {
            if (top < 0) { return 0; }
            char opening = stack[top--];
            if ((ch == ')' && opening != '(') || (ch == ']' && opening != '[') || (ch == '}' && opening != '{')) { return 0; }
        }
    }
    return top == -1;
}

int main(void)
{
    char text[80];
    if (!read_line(text)) { puts("Invalid input"); return 1; }
    puts(balanced(text) ? "Balanced" : "Unbalanced");
    return 0;
}

{[()]}

Balanced

Postfix construction

1. Create a leaf and push its pointer for every operand.
2. For a binary operator, pop the right subtree first, then the left.
3. Create an operator node with those children and push it.
4. Require one final tree root; reject insufficient operands or leftover roots.

Example

For postfix AB+C*, first make leaves A and B and combine them under +. Then create C. Finally make * the root, with the + subtree on its left and C on its right. The tree represents (A+B)*C.

Traversals

Preorder visits root, left and right, producing *+ABC. Postorder visits left, right and root, producing AB+C*. Inorder visits left, root and right. To preserve exact expression grouping, include suitable parentheses; plain unparenthesised inorder text can lose the tree’s grouping.

Evaluation

For a leaf, obtain its operand value. For an operator node, evaluate its left and right subtrees and apply the operator with valid arithmetic. Reject zero division and out-of-range calculations according to the chosen numeric representation.

Complexity

Construction from n tokens uses O(n) node and stack space and O(n) structural work. Traversal visits each node once: O(n) time. Recursive traversal adds O(h) call depth for tree height h. Dynamically created nodes must be released when the tree is no longer needed.

Diagram or flowchart

Operations

1. Create an empty queue.
2. enqueue(x) adds x at the rear if capacity permits.
3. dequeue returns and removes the front item if non-empty.
4. front or peek reads the front item without removing it.

Example

Enqueue 10, then 20 and 30. The first dequeue returns 10, leaving 20 at the front. This differs from a stack, which would remove 30 first. Queue values need not be sorted by magnitude or priority.

Overflow and underflow

A bounded array queue overflows when its capacity is exhausted. A linked queue can fail when node allocation fails. Underflow occurs when an empty queue is asked to remove or expose a front element. Return a status separately from the data value.

Applications

Queues model printer jobs, arrival-order service requests, buffered work and BFS traversal. A priority queue is a different contract that chooses by priority rather than ordinary FIFO arrival order.

Array choices and complexity

A naive linear array can waste released front positions until reset or shifting occurs. A circular array reuses them with wraparound and gives O(1) enqueue/dequeue in the shown implementation. Printing n queued values takes O(n). Capacity c requires O(c) storage, with O(1) counters.

Diagram or flowchart

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#define CAP 3
struct Queue { int data[CAP]; int front, count; };
int enqueue(struct Queue *q, int value)
{
    if (q->count == CAP) { return 0; }
    q->data[(q->front + q->count) % CAP] = value; ++q->count; return 1;
}
int dequeue(struct Queue *q, int *out)
{
    if (q->count == 0) { return 0; }
    *out = q->data[q->front]; q->front = (q->front + 1) % CAP; --q->count; return 1;
}

int main(void)
{
    struct Queue q = {{0}, 0, 0}; int value;
    if (!enqueue(&q, 10) || !enqueue(&q, 20) || !enqueue(&q, 30)) { return 1; }
    if (dequeue(&q, &value)) { printf("Removed = %d\n", value); }
    if (!enqueue(&q, 40)) { return 1; }
    while (dequeue(&q, &value)) { printf("%d\n", value); }
    return 0;
}

Removed = 10
20
30
40

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• April/May 2023 · Q3(a) · 5 marks

  Describe queue overflow and underflow conditions.

  Paper DS01 · page 1
• April/May 2023 · Q3(b) · 5 marks

  Discuss applications of queues.

  Paper DS01 · page 1
• February 2024 · Q1(b) · 1 marks

  Give queue applications.

  Paper DS03 · page 1

View all matching source questions →

Representation

Keep an array, front index and count. The next insertion index is (front + count) % capacity. This convention avoids confusing full and empty states when front and rear indices happen to be equal. Other valid conventions may reserve a slot and use different conditions.

Enqueue

1. Reject count == capacity.
2. Store at (front + count) % capacity.
3. Increment count.

Dequeue

1. Reject count == 0.
2. Save the item at front.
3. Set front = (front + 1) % capacity and decrement count.
4. Return success and the saved item.

Example

With capacity 3, enqueue 10, 20 and 30, then dequeue 10. Enqueue 40 uses the newly available wrapped position. Logical order is 20, 30, 40 even though physical index order has wrapped. Display from front for count elements, applying modulo.

Complexity and constraints

Each operation performs fixed work, giving O(1) time. The array uses O(capacity) storage. Capacity must be positive before modulo is used. Do not combine the full condition from a reserved-slot implementation with this count-based implementation without changing the rest of the design.

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#define CAP 3
struct Queue { int data[CAP]; int front, count; };
int enqueue(struct Queue *q, int value)
{
    if (q->count == CAP) { return 0; }
    q->data[(q->front + q->count) % CAP] = value; ++q->count; return 1;
}
int dequeue(struct Queue *q, int *out)
{
    if (q->count == 0) { return 0; }
    *out = q->data[q->front]; q->front = (q->front + 1) % CAP; --q->count; return 1;
}

int main(void)
{
    struct Queue q = {{0}, 0, 0}; int value;
    if (!enqueue(&q, 10) || !enqueue(&q, 20) || !enqueue(&q, 30)) { return 1; }
    if (dequeue(&q, &value)) { printf("Removed = %d\n", value); }
    if (!enqueue(&q, 40)) { return 1; }
    while (dequeue(&q, &value)) { printf("%d\n", value); }
    return 0;
}

Removed = 10
20
30
40

Enqueue

1. Allocate and initialise a new node with next = NULL.
2. On allocation failure, leave the queue unchanged and report failure.
3. If empty, set front to the new node; otherwise link rear->next to it.
4. Set rear to the new node.

Dequeue

1. Reject an empty front.
2. Save the front node and value, then advance front.
3. If front becomes NULL, set rear = NULL too.
4. Free the removed node and return its value.

Example

Enqueue 10 and 20 produces front → 10 → 20 ← rear. Dequeue returns 10. Removing 20 then makes both pointers NULL. A later enqueue must correctly recreate both ends rather than using a dangling old rear.

Resource management

A linked queue is not literally unlimited: every new node requires available storage. Its owner should destroy all remaining nodes before abandoning the queue. A missing rear update on the final removal is a common correctness error.

Complexity

Enqueue and dequeue use O(1) link work, excluding allocator internals. Without rear, enqueue could need O(n) traversal. The n nodes occupy O(n) data and link storage, with fixed queue-descriptor space.

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
struct Queue { struct Node *front, *rear; };
int enqueue(struct Queue *q, int value)
{
    struct Node *node = malloc(sizeof *node);
    if (node == NULL) { return 0; }
    node->data = value; node->next = NULL;
    if (q->rear == NULL) { q->front = node; } else { q->rear->next = node; }
    q->rear = node; return 1;
}
int dequeue(struct Queue *q, int *out)
{
    if (q->front == NULL) { return 0; }
    struct Node *old = q->front; *out = old->data; q->front = old->next;
    if (q->front == NULL) { q->rear = NULL; }
    free(old); return 1;
}

int main(void)
{
    struct Queue q = {NULL, NULL}; int value;
    if (!enqueue(&q, 10) || !enqueue(&q, 20)) {
        while (dequeue(&q, &value)) { }
        puts("Allocation failed"); return 1;
    }
    while (dequeue(&q, &value)) { printf("%d\n", value); }
    return 0;
}

10
20

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• August/September 2022 · Q1(b) · 7 marks

  Implement a queue using a singly linked list.

  Paper DS02 · page 1

View all matching source questions →

Example

After inserting 10, 20 and 30, a stack pop returns 30 and a queue dequeue returns 10. Stack operations use top. Queue insertion uses rear and removal uses front. Neither rule requires numerical sorting.

Applications

Undo and nested expression processing fit stacks. Arrival-order jobs and BFS fit queues. Either ADT may use arrays or linked nodes; the access rule does not depend on one memory layout.

Two-stack queue

1. Keep an input stack and an output stack.
2. Enqueue pushes onto the input stack.
3. For dequeue, if output is empty, transfer every input item to output by repeated pop/push.
4. Pop output; if both are empty, report underflow.

Why it works

The transfer reverses input order so the earliest remaining item reaches output’s top. Keep using output until it empties before another transfer. Moving input on every dequeue regardless of output state would not follow this algorithm.

Complexity

One dequeue can require O(n) transfer work. Across a sequence of operations, each item moves from input to output at most once and is then removed, giving O(1) amortised stack-operation work per queue operation. This is not a claim that every individual dequeue is worst-case constant. The stored items need O(n) space, and bounded stacks still need a capacity policy.

Reference table

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• April/May 2023 · Q1(b) · 3 marks

  How can a queue be constructed using stacks?

  Paper DS01 · page 1
• September 2021 · Q1(b) · 7 marks

  Differentiate stack and queue.

  Paper DS07 · page 1

View all matching source questions →