程序员面试金典-0304-化栈为队

客官°小女子只卖身不卖艺 2022-10-06 15:52 119阅读 0赞

## 程序员面试金典-0304-化栈为队 ##

c语言不支持栈，可以用单链表来实现。

queue.push(1);
    queue.push(2);
    queue.peek();  // 返回 1
    queue.pop();   // 返回 1
    queue.empty(); // 返回 false

typedef struct node{
        
        int val;
        struct node * next;
    }Node;
    
    typedef struct {
        
        Node * head;
    } MyQueue;
    
    /** Initialize your data structure here. */
    
    MyQueue* myQueueCreate() {
        
        MyQueue * m = malloc(sizeof(MyQueue));
        Node * n = malloc(sizeof(Node));
        n->val = -1;
        n->next = NULL;
        m->head = n;
        return m;
    }
    
    /** Push element x to the back of queue. */
    void myQueuePush(MyQueue* obj, int x) {
        
        Node * t =  malloc(sizeof(Node));
        t->val = x;
        t->next = NULL;
    
        Node * h = obj->head;
        Node * temp = h;
        while(temp->next!=NULL){
        
            temp = temp->next;
        }
        temp->next=t;
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int myQueuePop(MyQueue* obj) {
        
        Node * h = obj->head;
        Node * t = h->next;
        int ret = t->val;
        h->next = t->next;
        free(t);
        return ret;
    }
    
    /** Get the front element. */
    int myQueuePeek(MyQueue* obj) {
        
        return obj->head->next->val;
    }
    
    /** Returns whether the queue is empty. */
    bool myQueueEmpty(MyQueue* obj) {
        
        if(obj->head->next == NULL)
            return true;
        else
            return false;
    }
    
    void myQueueFree(MyQueue* obj) {
        
        Node * h = obj->head;
        Node * temp = h->next;
        Node * t = temp;
        while(temp!=NULL){
        
            t = temp->next;
            free(temp);
            temp = t;
        }
        free(h);
        free(obj);
    }
    
    /**
     * Your MyQueue struct will be instantiated and called as such:
     * MyQueue* obj = myQueueCreate();
     * myQueuePush(obj, x);
     
     * int param_2 = myQueuePop(obj);
     
     * int param_3 = myQueuePeek(obj);
     
     * bool param_4 = myQueueEmpty(obj);
     
     * myQueueFree(obj);
    */