Using queues to implement stack accepted best in C, well-commented


  • 0

    Actually it seems rather weird to use queue to imitate the stack using array -> I even sometimes do not know what exactly I am doing; but since we should use only the operations of queue to implement the push, pop and top of the stack, we have to do it exactly that way -> otherwise it will lose completely its purpose and meaning.

    The following code is only to use queue operations which can easily be replaced totally by actual operations of queue.


    typedef struct
    {
        int  *queue0; //the major queue where all elements being stored;
        int  *queue1; //assistant queue for imitation;
        int size; //used to record the size of queue0;
        int maxSize;
    } Stack;
    
    void stackCreate(Stack *stack, int maxSize)
    {
        stack->maxSize = maxSize;
        stack->size = 0;
        stack->queue0 = (int*)malloc(sizeof(int)*maxSize);
        stack->queue1 = (int*)malloc(sizeof(int)*maxSize);
    }
    
    void stackPush(Stack *stack, int element)
    {
        stack->queue0[stack->size++] = element;
    }
    
    void stackPop(Stack *stack)
    {
        int size = stack->size;
        for(int i = 0; i < size-1; i++) //popping queue0 to queue1 all elements except for the last;
            stack->queue1[i] = stack->queue0[i];
        stack->size--; //delete the last element in queue0;
        for(int i = 0; i < size-1; i++) //popping queue1 back to queue0 and update stack->size;
            stack->queue0[i] = stack->queue1[i];
    }
    
    int stackTop(Stack *stack)
    {
        int size = stack->size;
        for(int i = 0; i < size-1; i++) //popping queue0 to queue1 all elements except for the last;
            stack->queue1[i] = stack->queue0[i];
        int ret = stack->queue0[size-1]; //pop the last from queue0;
        for(int i = 0; i < size-1; i++) //popping queue1 back to queue0;
            stack->queue0[i] = stack->queue1[i];
        return ret;
    }
    
    bool stackEmpty(Stack *stack)
    {
        return stack->size == 0;
    }
    
    void stackDestroy(Stack *stack)
    {
        free(stack->queue0);
        free(stack->queue1);
    }

Log in to reply
 

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