stack implementation

下面是一个template版本利用 array 和 single linked list实现的stack， 包含以下功能:

1. push, pop, top, size, isEmpty

2. 线程安全

从下面的实现可以看出来， push, pop top 这些操作都是O(1)的time complexity

/*implementation of stack*/

/*M1: use single linked list to implement*/

// treat head as top of the stack

// push element before head

// pop element on head

template <typename K>

class StackEntry{

private:

    K value;

    StackEntry* next;

public:

    StackEntry(K value) {

        this->value = value;

        this->next = NULL;

    }

    void setValue(K value){

        this->value = value;

    }

    void setNext(StackEntry* next) {

        this->next = next;

    }

    K getValue() const{

        return value;

    }

    StackEntry* getNext() const{

        return next;

    }

};

//用 linkedlist 实现的数据结构，不用考虑Capacity问题吧

template <typename K>

class Stack{

private:

    StackEntry<K> * head;

    mutex mtx;

    int size;

public:

    Stack() {

        head = NULL;

        size = 0;

    }

   ~Stack() {

        StackEntry<K>* tmp = head;

        while (head) {

            tmp = head;

            head = head->getNext();

            delete tmp;

        }

    }

    void push(K value){

        mtx.lock();

        //insert element before head

        StackEntry<K>* newEntry = new StackEntry<K>(value);

        if (head == NULL) {

            head = newEntry;

        } else {

            newEntry->setNext(head);

            head = newEntry;

        }

        size++;

        mtx.unlock();

    }

    K top(){

        mtx.lock();

        //get the head of the liklist

        if (head == NULL) {

            throw invalid_argument("The stack is empty!");

        } else {

            return head->getValue();

        }

        mtx.unlock();

    }

    void pop(){

        mtx.lock();

        //pop head from the linklist

        if (head == NULL) {

            throw invalid_argument("The stack is empty!");

        } else {

            StackEntry<K>* tmp = head;

            head = head->getNext();

            delete tmp;

        }

        size--;

        mtx.unlock();

    }

    int getSize() {

        mtx.lock();

        return size;

        mtx.unlock();

    }

    bool isEmpty(){

        mtx.lock();

        return size == 0;

        mtx.unlock();

    }

};

/*end of implementation of stack*/

/*implementation of queue*/

/*end of implementation of queue*/

//file system

//class:  FILE, Directory,

int main(int argc, const char * argv[]) {

    // insert code here...

    std::cout << "Hello, World!\n";

    int a[7] = {1,2,4,6,7,8,9};

    vector<int> input(a, a+7);

 // vector<int> rst = getUnion()

    

    Stack<int> s;

    s.push(2);

    cout << "TOP IS"<<s.top();

    s.push(3);

    cout << s.top();

    s.pop();

    cout << s.top();

    s.push(4);

    cout << s.top();

    s.pop();

    cout << s.top();

    s.pop();

    cout << s.top();

    return 0;

}

/*implementation of stack*/

/*M2: use array to implement*/

// treat head as the end of the array

// push element at the end of the array

template <typename K>

class StackEntry{

private:

    K value;

public:

    StackEntry(K value) {

        this->value = value;

    }

    void setValue(K value){

        this->value = value;

    }

    K getValue() const{

        return value;

    }

};

const int Capacity = 128;

template <typename K>

class Stack{

private:

    int head;

    StackEntry<K>* list;

    int size;

public:

    Stack() {

        head  = 0;

        size = 0;

        list = new int[Capacity];

    }
 ~Stack() {
        if (head != 0) {
            for (int i = 0; i < size; i++) {
                StackEntry<K>* tmp = list[i];
                head--;
                delete tmp;
            }
        }
        delete [] list;

    }

    void push(K value) {

        if (size == Capacity) {

            throw invalid_argument("Out of capacity");

        } else {

            list[head++] = new StackEntry<K>(value);

        }

        size++;

    }

    void pop() {

        if (head == 0) {

            throw invalid_argument("the stack is empty");

        } else {

            StackEntry<K>* tmp = list[head];

            head--;

            delete tmp;

        }

        size--;

    }

    K top() {

        return list[head]->getValue();

    }

    int getSize() {

        return size;

    }

    bool isEmpty(){

        return size == 0;

    }

};