c语言实现队列

刺骨的言语ヽ痛彻心扉 2022-12-24 05:00 108阅读 0赞

## C语言实现队列 ##

我的stack和queue都是用双向链表实现的，感觉链表实现起来容易一点，特别是不用注重考虑扩容的事情，这样一想java的hashmap实现确实挺重要的，怪不得经常面试的时候问起来。有机会就分享一下hashmap的源码吧。目前来说cJSON是我下一个想实现的，牵涉到二叉树和递归。  
先说这个队列吧，实在是简单。

用栈实现队列
    请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：
    
    实现 MyQueue 类：
    
    void push(int x) 将元素 x 推到队列的末尾
    int pop() 从队列的开头移除并返回元素
    int peek() 返回队列开头的元素
    boolean empty() 如果队列为空，返回 true ；否则，返回 false
     
    
    说明：
    
    你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
    你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
     
    
    进阶：
    
    你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
     
    
    示例：
    
    输入：
    ["MyQueue", "push", "push", "peek", "pop", "empty"]
    [[], [1], [2], [], [], []]
    输出：
    [null, null, null, 1, 1, false]
    
    解释：
    MyQueue myQueue = new MyQueue();
    myQueue.push(1); // queue is: [1]
    myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
    myQueue.peek(); // return 1
    myQueue.pop(); // return 1, queue is [2]
    myQueue.empty(); // return false
     
    
    提示：
    
    1 <= x <= 9
    最多调用 100 次 push、pop、peek 和 empty
    假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
    
    作者：力扣 (LeetCode)
    链接：https://leetcode-cn.com/leetbook/read/queue-stack/gvtxe/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

C语言实现，原则就是能跑过leetcode就行，但是显然leetcode某些方面对代码的NULL判断会弱一点，比如对空队列pop，所以就当是娱乐一下吧。

#include <stdlib.h>
    typedef int ELEMENT;
    typedef struct node{
        
        ELEMENT x;
        struct node * next;
        struct node * prev;
    }Node;
    
    typedef struct {
        
        Node * head;
        Node * rear;
    } MyQueue;
    
    /** Initialize your data structure here. */
    
    MyQueue* myQueueCreate() {
        
        MyQueue * q = malloc(sizeof(MyQueue));
        q -> head = NULL;
        q -> rear = NULL;
        return q;
    }
    
    Node * Node_init(int t)
    {
        
        Node * node = malloc(sizeof(Node));
        node -> x = t;
        node -> prev = NULL;
        node -> next = NULL;
        return node;
    }
    
    /** Push element x to the back of queue. */
    void myQueuePush(MyQueue* obj, int x) {
        
        Node * node = Node_init(x);
        if(obj==NULL)
            return;
        if(obj -> head == NULL)
        {
        
            obj -> head = node;
            obj -> rear = node;
        }
        else
        {
        
            obj -> rear -> next = node;
            node -> prev = obj -> rear; //将最后节点prev向前指向obj->rear
            obj -> rear = node;
        }
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int myQueuePop(MyQueue* obj) {
        
            int ret = obj -> head ->x;
            Node * t = obj -> head;
            obj -> head = t -> next;
            free(t);
            return ret;
    }
    
    /** Get the front element. */
    int myQueuePeek(MyQueue* obj) {
        
        return obj->head->x;
    }
    
    /** Returns whether the queue is empty. */
    bool myQueueEmpty(MyQueue* obj) {
        
        return (obj->head == NULL);
    }
    
    void myQueueFree(MyQueue* obj) {
        
        while(obj->head != NULL)
        {
        
            myQueuePop(obj);
        }
        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);
    */

感觉双向链表可以解决很多问题，但是类似于cJSON这种，需要parse JSON字符串，虽然是对字符串的处理，但其实也有点难度。freewheel当时二面面试我就是问的类似于JSON的处理，希望两周之内可以实现一个cJSON吧。需要补充一下二叉树的知识了。