使用satck實(shí)現(xiàn)queue

我使用的是 單向鏈表 實(shí)現(xiàn)的queue.

考察的是基本的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。

為了實(shí)現(xiàn)pop 和push 操作，需要設(shè)計(jì)兩個(gè)指針（我代碼中成了首位兩個(gè)節(jié)點(diǎn)），一個(gè)只想第一個(gè)元素，另一個(gè)只想最后一個(gè)元素，以便快速實(shí)現(xiàn)pop和push操作。

結(jié)構(gòu)體Node中的默認(rèn)構(gòu)造函數(shù)，也算是一個(gè)知識(shí)點(diǎn)吧。

同一段代碼，中午提交沒通過，晚上一點(diǎn)沒改再次提交竟然通過了。。。。真是沒脾氣。

發(fā)現(xiàn)一個(gè)問題，pop操作時(shí)，如果queue為空，應(yīng)該返回false.

代碼如下：

class MyQueue {public:    struct Node{        int data;        Node* ptr;        Node(const int x=0,Node* p=NULL):data(x),ptr(p){}    };    /** Initialize your data structure here. */    MyQueue() {        size=0;        head=new Node;        tail=new Node;        head->ptr=tail;        tail->ptr=head;       }       /** Push element x to the back of queue. */    void push(int x) {        if(empty()){            head->ptr=new Node(x,tail);            tail->ptr=head->ptr;        }        else{            tail->ptr->ptr=new Node(x,tail);            tail->ptr=tail->ptr->ptr;        }        ++size;    }       /** Removes the element from in front of queue and returns that element. */    int pop() {        int ret=head->ptr->data;        Node* tmp=head->ptr;        head->ptr=tmp->ptr;        delete tmp;        --size;        return ret;    }       /** Get the front element. */    int peek() {        return head->ptr->data;    }       /** Returns whether the queue is empty. */    bool empty() {        return size==0?true:false;    }   PRivate:    unsigned int size;    Node* head;    Node* tail;};/** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * bool param_4 = obj.empty(); */
修改成指針之后：
class MyQueue{public:    struct Node{        int data;        Node* ptr;        Node(int x=0,Node* p=NULL):data(x),ptr(p){}    };        MyQueue(){        size=0;        head=NULL;        tail=NULL;            }    int pop()    {        if(empty())            return false;        int ret=head->data;        Node* tmp=head->ptr;        delete head;        --size;        head=tmp;        return ret;           }    void push(int x)    {        if(empty())        {            head=new Node(x,nullptr);            tail=head;        }        else        {            tail->ptr=new Node(x,nullptr);            tail=tail->ptr;        }        ++size;    }    int peek()    {        return head->data;    }       bool empty()    {        return size==0?true:false;    }private:    Node* head;    Node* tail;    unsigned int size;    };