0ms C implementation using only an array and top to simulate stack


  • 0
    Y
    typedef struct {
        int *arr;
        int top;
    } Queue;
    
    /* Create a queue */
    void queueCreate(Queue *queue, int maxSize) {
        queue->arr=(int*)malloc(maxSize*sizeof(int));
        queue->top=0;
    }
    
    /* Push element x to the back of queue */
    void queuePush(Queue *queue, int element) {
        int top=queue->top++;
        int i;
        if(top==0){
            queue->arr[top]=element;
        }
        else{
            for(i=top-1;i>=0;i--) queue->arr[i+1]=queue->arr[i];
            queue->arr[0]=element;
        }
    }
    
    /* Removes the element from front of queue */
    void queuePop(Queue *queue) {
        queue->top--;
    }
    
    /* Get the front element */
    int queuePeek(Queue *queue) {
        int top=queue->top;
        return queue->arr[top-1];
    }
    
    /* Return whether the queue is empty */
    bool queueEmpty(Queue *queue) {
        return !queue->top;
    }
    
    /* Destroy the queue */
    void queueDestroy(Queue *queue) {
        queue->top=0;
    }

  • 0
    P

    ehhh, When u push a element, u will use O(n). But the true queue need O(1) only.It because the dataset is sooo small, or u will see.


  • 0
    T

    The solution is alright because the question asks for implementing queue with stack, so O(n) is desired.


  • 0
    P

    You are right.But why no do better?


Log in to reply
 

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