Implement Stack

题目：

Implement a stack. You can use any data structure inside a stack except stack itself to implement it.

接口：

接口太多，不一一黏贴，包括top(), push(), pop(), isEmpty().

分析：

允许使用自定义数据结构，因此使用Doubly Linked List来实现，从尾部加入，从尾部删除。需要注意以下几点：

(1) 自己定义stack的构造函数，最重要的是两个全局变量dummy和curr

(2) 目前在Pop()不出来的时候用return -1，但是应该用一个assert方法来报错。

解法：

class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node(int x) : val(x), prev(NULL), next(NULL) {}
};

class Stack {
public:
    Node* dummy;
    Node* curr;
    // Push a new item into the stack
    Stack() {
        dummy = new Node(0);
        curr = dummy;
    }
    void push(int x) {
        // Write your code here
        Node* temp = new Node(x);
        curr->next = temp;
        temp->prev = curr;
        curr = curr->next;
    }

    // Pop the top of the stack
    void pop() {
        // Write your code here
        Node* temp = curr;
        curr = curr->prev;
        curr->next = NULL;
        delete temp;
    }

    // Return the top of the stack
    int top() {
        // Write your code here
        if (curr == dummy) {
            return -1;
        } else {
            return curr->val;
        }
    }

    // Check the stack is empty or not.
    bool isEmpty() {
        // Write your code here
        if (curr == dummy) {
            return true;
        } else {
            return false;
        }
    }
};