leetcode: Implement Queue using Stacks

使用satck实现queue

我使用的是 单向链表 实现的queue.

考察的是基本的数据结构的实现。

为了实现pop 和push 操作，需要设计两个指针（我代码中成了首位两个节点），一个只想第一个元素，另一个只想最后一个元素，以便快速实现pop和push操作。

结构体Node中的默认构造函数，也算是一个知识点吧。

同一段代码，中午提交没通过，晚上一点没改再次提交竟然通过了。。。。真是没脾气。

发现一个问题，pop操作时，如果queue为空，应该返回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;    };