C Solution (0ms) - using two `realloc` based queues


  • 0
    #define queue_new(q, type)        type *q; int q##Size
    #define queue_init(q)             q = NULL; q##Size = 0
    #define queue_peek(q)             q[0]
    #define queue_empty(q)            (q##Size == 0)
    #define queue_size(q)             q##Size
    #define queue_enqueue(q, type, x) q = realloc(q, ++q##Size * sizeof(type)); q[q##Size - 1] = x
    #define queue_dequeue(q, type)    memcpy(q, q + 1, --q##Size * sizeof(type)); \
                                      q = realloc(q, q##Size * sizeof(type))
    #define queue_swap(q1, q2, type)  do { \
                                           type *tmp = q1; q1 = q2; q2 = tmp; \
                                           int i = q1##Size; q1##Size = q2##Size; q2##Size = i; \
                                      } while (0)
    typedef struct {
        queue_new(q1, int);
        queue_new(q2, int);
    } Stack;
    
    /* Create a stack */
    void stackCreate(Stack *stack, int maxSize) {
        queue_init(stack->q1);
        queue_init(stack->q2);
    }
    
    /* Push element x onto stack */
    void stackPush(Stack *stack, int element) {
        queue_enqueue(stack->q1, int, element);
    }
    
    /* Get the top element */
    int stackTop(Stack *stack) {
        int element = -1;
        while (!queue_empty(stack->q1)) {
            element = queue_peek(stack->q1);
            queue_dequeue(stack->q1, int);
            queue_enqueue(stack->q2, int, element);
        }
        queue_swap(stack->q1, stack->q2, int);
        return element;
    }
    
    /* Removes the element on top of the stack */
    void stackPop(Stack *stack) {
        while (queue_size(stack->q1) > 1) {
            queue_enqueue(stack->q2, int, queue_peek(stack->q1));
            queue_dequeue(stack->q1, int);
        }
        queue_dequeue(stack->q1, int);
        queue_swap(stack->q1, stack->q2, int);
    }
    
    /* Return whether the stack is empty */
    bool stackEmpty(Stack *stack) {
        return queue_empty(stack->q1) && queue_empty(stack->q2);
    }
    
    /* Destroy the stack */
    void stackDestroy(Stack *stack) {
        free(stack->q1);
        free(stack->q2);
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.