Deque solution accepted as best 0ms in C, well-commented


  • 0
    typedef struct //using deque to imitate the two stacks operation avoid extra O(N) space wasting;
    {
        int *stack;
        int begin; //begin -> point to the exact first front element;
        int end; //end -> point to the next element of the last element to be easily indicate the empty case;
        int maxSize;
    } Queue;
    
    void queueCreate(Queue *queue, int maxSize)
    {
        queue->stack = (int*)malloc(sizeof(int)*maxSize);
        queue->begin = 0;
        queue->end = 0;
        queue->maxSize = maxSize; //record the maxSize for checking;
    }
    
    void queuePush(Queue *queue, int element)
    {
        if(queue->end == queue->maxSize) //reach its valid end, we have to rearrange the stack;
        {
            for(int i = queue->begin; i < queue->end; i++)
                queue->stack[i-queue->begin] = queue->stack[i];
            queue->begin = 0;
            queue->end -= queue->begin;
        }
        queue->stack[queue->end++] = element;
    }
    
    void queuePop(Queue *queue)
    {
        queue->begin++;
    }
    
    int queuePeek(Queue *queue)
    {
        return queue->stack[queue->begin];
    }
    
    bool queueEmpty(Queue *queue)
    {
        return queue->begin == queue->end;
    }
    
    void queueDestroy(Queue *queue)
    {
        free(queue->stack);
        /*free(queue); this part cannot be executed*/
    }

  • 0
    H

    @LHearen I think the queue->end should not equal to MaxSize, max(queue->end) will be MaxSize-1


Log in to reply
 

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