We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Queue using Two Stacks
  2. Discussions

Queue using Two Stacks

  • jesselarrew
     + 1 comment

    Summary

    Here is a pure C solution. The standard C library doesn't include any pre-canned data structure implementations, so this solution includes a home-grown stack and queue implementation.

    Approach

    The main idea is to implement a queue (FIFO) using two stacks (LIFO) where each stack manages one end of the queue. The nifty part is that both stacks manage the same memory buffer. The 'rear' stack grows upward and is initially empty, whereas the 'front' stack grows downward and is initially full. Enqueue operations are only done on the 'rear' stack (i.e. push operations to an initially empty stack), and dequeue operations are only done to the 'front' stack (i.e. pop operations on a stack that is 'upside down' in memory and initially full).

    Code

    #include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <stdint.h>
#include <errno.h>
#include <stdbool.h>

//#define DEBUG

#ifdef DEBUG
#define dbg_print(fmt, ...)    fprintf(stderr, (fmt), __VA_ARGS__)
#else
#define dbg_print(fmt, ...)
#endif

/*
 * LIFO Stack Implementation.
 */
typedef int stack_data_t;

struct stack {
    stack_data_t *elements;
    size_t size;
    size_t top;
    bool is_initialized;
    bool is_growing_up;
};

static int stack_clear(struct stack *stack)
{
    int status = EXIT_FAILURE;

    if (!stack || stack->size == 0) {
        status = -EINVAL;
        goto out;
    }

    stack->top = 0;
    dbg_print("stack %p: top is %lu.\n", stack, stack->top);

    status = EXIT_SUCCESS;
out:
    return status;
}

static int stack_fill(struct stack *stack)
{
    int status = EXIT_FAILURE;

    if (!stack || stack->size == 0) {
        status = -EINVAL;
        goto out;
    }

    stack->top = stack->size;
    dbg_print("stack %p: top is %lu.\n", stack, stack->top);

    status = EXIT_SUCCESS;
out:
    return status;
}

void stack_free(struct stack *stack)
{
    if (!stack) {
        return;
    }

    dbg_print("freeing stack %p.\n", stack);

    if (stack->is_initialized && stack->elements) {
        dbg_print("stack %p: freeing %p.\n", stack, stack->elements);
        free(stack->elements);
    }
    memset(stack, 0, sizeof(*stack));
}

int stack_init(struct stack *stack, size_t size, bool is_growing_up)
{
    int status = EXIT_FAILURE;
    
    if (!stack || size == 0) {
        status = -EINVAL;
        goto out;
    }

    stack->elements = calloc(size, sizeof(stack_data_t));
    if (!stack->elements) {
        status = -ENOMEM;
        goto out;
    }

    stack->size = size;
    stack->is_growing_up = is_growing_up;

    status = stack_clear(stack);
    if (status != EXIT_SUCCESS) {
        goto out_free;
    }

    stack->is_initialized = true;

    status = EXIT_SUCCESS;
out_free:
    if (status != EXIT_SUCCESS) {
        stack_free(stack);
    }
out:
    return status;
}

/*
 * NOTE: For safety purposes, an uninitialized stack
 * is treated as both full and empty. This maximizes
 * the likelihood that execution is directed to an
 * error path if stack_is_empty/full() is called
 * without first checking if the stack is initialized.
 */

bool stack_is_full(const struct stack *stack)
{
    return stack && stack->is_initialized ? stack->top == stack->size
                                          : true;
}

bool stack_is_empty(const struct stack *stack)
{
    return stack && stack->is_initialized ? stack->top == 0
                                          : true;
}

int stack_push(struct stack *stack, int value)
{
    int status = EXIT_FAILURE;
    
    if (!stack) {
        status = -EINVAL;
        goto out;
    }
    
    if (!stack->is_initialized) {
        status = -ENODATA;
        goto out;
    }

    if (stack_is_full(stack)) {
        status = -ENOBUFS;
        goto out;
    }

    size_t index = stack->is_growing_up ? stack->top
                                        : stack->size - 1 - stack->top;
    stack->elements[index] = value;
    stack->top++;
    dbg_print("stack %p: top is %lu (%d).\n",
              stack, stack->top, stack->elements[index]);

    status = EXIT_SUCCESS;
out:
    return status;
}

int stack_pop(struct stack *stack, int *value)
{
    int status = EXIT_FAILURE;
    
    if (!stack || !value) {
        status = -EINVAL;
        goto out;
    }

    if (!stack->is_initialized) {
        status = -ENODATA;
        goto out;
    }

    if (stack_is_empty(stack)) {
        status = -ENOBUFS;
        goto out;
    }

    stack->top--;
    size_t index = stack->is_growing_up ? stack->top
                                        : stack->size - 1 - stack->top;
    *value = stack->elements[index];
    dbg_print("stack %p: top is %lu (%d).\n",
              stack, stack->top, stack->elements[index]);

    status = EXIT_SUCCESS;
out:
    return status;
}

int stack_peek(const struct stack *stack, stack_data_t *value, size_t index)
{
    int status = EXIT_FAILURE;
    
    if (!stack || !value) {
        status = -EINVAL;
        goto out;
    }

    if (!stack->is_initialized) {
        status = -ENODATA;
        goto out;
    }

    if (index >= stack->top) {
        status = -ERANGE;
        goto out;
    }

    *value = stack->is_growing_up ? stack->elements[index]
                                  : stack->elements[stack->size - 1 - index];
    dbg_print("peek @ index %lu: %d\n", index, *value);

    status = EXIT_SUCCESS;
out:
    return status;
}

/*
 * FIFO Queue Implementation.
 */
typedef stack_data_t queue_data_t;

struct queue {
    struct stack front;
    struct stack rear;
    bool is_initialized;
    size_t count;
};

int queue_init(struct queue *q, size_t size)
{
    int status = EXIT_FAILURE;
    
    if (!q || size == 0) {
        status = -EINVAL;
        goto out;
    }

    /* The 'rear' stack is initially empty. */
    status = stack_init(&q->rear, size, true);
    if (status != EXIT_SUCCESS) {
        goto out;
    }

    /*
     * The 'front' stack manages the same memory buffer
     * as the 'rear', but it grows in the opposite direction
     * and is treated as being initially full.
     */
    q->front.elements = q->rear.elements;
    q->front.size = q->rear.size;
    q->front.is_growing_up = !q->rear.is_growing_up;
    stack_fill(&q->front);
    q->front.is_initialized = true;
    
    q->count = 0;
    q->is_initialized = true;

    status = EXIT_SUCCESS;
out:
    return status;
}

void queue_free(struct queue *q)
{
    if (!q) {
        return;
    }

    if (q->is_initialized) {
        /*
         * The front and rear stacks both manage the same
         * memory buffer, so we only need to free one of
         * them.
         */
        stack_free(&q->rear);
    }
    memset(q, 0, sizeof(*q));
}

size_t queue_count(const struct queue *q)
{
    return q && q->is_initialized ? q->count
                                  : 0;
}

/*
 * NOTE: For safety purposes, an uninitialized queue
 * is treated as both full and empty. This maximizes
 * the likelihood that execution is directed to an
 * error path if queue_is_empty/full() is called
 * without first checking if the queue is initialized.
 */

bool queue_is_empty(const struct queue *q)
{
    return queue_count(q) == 0;
}

bool queue_is_full(const struct queue *q)
{
    return queue_count(q) == q->rear.size;
}

int queue_enqueue(struct queue *q, queue_data_t value)
{
    int status = EXIT_FAILURE;

    if (!q) {
        status = -EINVAL;
        goto out;
    }

    if (!q->is_initialized) {
        status = -ENODATA;
        goto out;
    }

    if (queue_is_full(q)) {
        status = -ENOBUFS;
        goto out;
    }

    /*
     * As elements are enqueued and dequeued, the top of the
     * front and rear stacks will drift upward. To ensure
     * continuous operation, have the rear stack wrap
     * circularly when the end of the buffer is reached.
     * Note that this is done only after checking that there
     * is still empty space in the queue!
     */
    if (stack_is_full(&q->rear)) {
        status = stack_clear(&q->rear);
        if (status != EXIT_SUCCESS) {
            goto out;
        }
    }

    status = stack_push(&q->rear, value);
    if (status != EXIT_SUCCESS) {
        goto out;
    }
    
    /* Check for counter overflow */
    if (q->count + 1 < q->count) {
        status = -E2BIG;
        goto out;
    }

    q->count++;
out:
    return status;
}

int queue_dequeue(struct queue *q, queue_data_t *value)
{
    int status = EXIT_FAILURE;
    
    if (!q || !value) {
        status = -EINVAL;
        goto out;
    }

    if (!q->is_initialized) {
        status = -ENODATA;
        goto out;
    }

    if (queue_is_empty(q)) {
        status = -ENOBUFS;
        goto out;
    }

    /*
     * As elements are enqueued and dequeued, the top of the
     * front and rear stacks will drift upward. To ensure
     * continuous operation, have the front stack wrap
     * circularly when the end of the buffer is reached.
     * Note that this is done only after checking that there
     * are occupied spaces in the queue!
     */
    if (stack_is_empty(&q->front)) {
        status = stack_fill(&q->front);
        if (status != EXIT_SUCCESS) {
            goto out;
        }
    }

    status = stack_pop(&q->front, value);
    if (status != EXIT_SUCCESS) {
        goto out;
    }

    /* Check for counter underflow */
    if (q->count - 1 > q->count) {
        status = -E2BIG;
        goto out;
    }

    q->count--;
out:
    return status;
}

int queue_print_front(const struct queue *q)
{
    int status = EXIT_FAILURE;
    stack_data_t front = 0;

    if (!q) {
        status = -EINVAL;
        goto out;
    }

    if (!q->is_initialized) {
        status = -ENODATA;
        goto out;
    }

    status = stack_peek(&q->front, &front, q->front.top - 1);
    if (status != EXIT_SUCCESS) {
        goto out;
    }

    dbg_print("front element is %d\n", front);
    printf("%d\n", front);

    status = EXIT_SUCCESS;
out:
    return status;
}

int read_int(int *value)
{
    int status = EXIT_FAILURE;
    
    if (!value) {
        status = EINVAL;
        goto out;
    }

    errno = 0;
    int rc = scanf("%d", value);
    if (rc != 1) {
        if (rc != EOF) {
            errno = rc;
        }
        perror("scanf");
        status = -errno;
        goto out;
    }
    
    dbg_print("scanf read: %d\n", *value);
    
    status = EXIT_SUCCESS;
out:
    return status;
}

enum query_type {
    QUERY_TYPE_INVALID    = 0,
    QUERY_TYPE_ENQUEUE    = 1,
    QUERY_TYPE_DEQUEUE    = 2,
    QUERY_TYPE_PRINT      = 3,
    
    QUERY_TYPE_LIMIT
};

int main()
{
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
#define MIN_QUERIES 1
#define MAX_QUERIES 100000
#define MIN_Q_VALUE 1
#define MAX_Q_VALUE 1000000000

    int status = EXIT_FAILURE;
    int queries = 0;
    struct queue q;

    /* Read the number of queries */
    status = read_int(&queries);
    if (status != EXIT_SUCCESS) {
        errno = -status;
        perror("read_int");
        goto out;
    }

    if (queries < MIN_QUERIES || queries > MAX_QUERIES) {
        fprintf(stderr, "Number of queries must be between %u and %u.\n",
                MIN_QUERIES, MAX_QUERIES);
        status = -ERANGE;
        goto out;
    }

    /* Initialize the queue */
    status = queue_init(&q, queries);
    if (status != EXIT_SUCCESS) {
        errno = -status;
        perror("queue_init");
        goto out;
    }

    /* Process each query */
    for (size_t i = 0; i < queries; i++) {
        enum query_type query = QUERY_TYPE_INVALID;
        int value = 0;
        size_t count = queue_count(&q);

        dbg_print("queue count is %lu.\n", count);

        /* Read the query type */
        status = read_int(&value);
        if (status != EXIT_SUCCESS) {
            errno = -status;
            perror("read_int");
            goto out_free;
        }

        query = (enum query_type)value;

        switch(query) {
        case QUERY_TYPE_ENQUEUE:
            /* Read the value to enqueue */
            status = read_int(&value);
            if (status != EXIT_SUCCESS) {
                errno = -status;
                perror("read_int");
                goto out_free;
            }

            status = queue_enqueue(&q, value);
            if (status != EXIT_SUCCESS) {
                errno = -status;
                perror("queue_enqueue");
                goto out_free;
            }
            break;

        case QUERY_TYPE_DEQUEUE:
            status = queue_dequeue(&q, &value);
            if (status != EXIT_SUCCESS) {
                errno = -status;
                perror("queue_dequeue");
                goto out_free;
            }
            break;

        case QUERY_TYPE_PRINT:
            status = queue_print_front(&q);
            if (status != EXIT_SUCCESS) {
                errno = -status;
                perror("queue_print_front");
                goto out_free;
            }
            break;

        default:
            fprintf(stderr, "Invalid query '%d'.\n", query);
            status = -EINVAL;
            goto out_free;
        }
    }
out_free:
    queue_free(&q);
out:
    exit(status);
}