Circular deque (C++資料結構)

題目:

1. Task: Implement a circular deque class template. A deque class can be pushed or popped from either ends, so instead of push and pop, you should implement these member functions: push_front, pop_front, push_rear, and pop_rear.

2. In the main function, read in a series of operations from a text file inputDQ.txt. Each line in the file contains one operation. The data part is always an integer. Example:

push_front 1

push_rear 5

push_rear -10

pop_front

push_front 17

3. After all the operations (ignore operations that cannot be done, such as a pop operation when the deque is empty), write all the elements as integers separated by spaces into a text file named outputDQ.txt.

請問該怎麼寫?

3 Answers

Rating
  • 7 years ago
    Favorite Answer

    #include <iostream>

    using namespace std;

    template <class TT> class deQ;

    template <class TT>

    class DD {

    private:

    TT dd;

    DD *prev, *nxt;

    public:

    DD(TT d):dd(d),prev(NULL),nxt(NULL){};

    ~DD(){};

    friend class deQ<TT>;

    };

    template <class TT>

    class deQ {

    private:

    int cnt;

    DD<TT> *head, *tail;

    public:

    deQ():cnt(0),head(NULL),tail(NULL){};

    ~deQ(){for(tail=head; tail && cnt; tail=tail->nxt, delete head, head=tail, --cnt);}

    int push_front(TT d) {

    DD<TT> *t = new DD<TT>(d);

    t->nxt = head;

    if (head) head->prev = t;

    head = t;

    if (!tail) tail = t;

    return ++cnt;

    };

    int push_rear(TT d) {

    DD<TT> *t = new DD<TT>(d);

    t->prev = tail;

    if (tail) tail->nxt = t;

    tail = t;

    if (!head) head = t;

    return ++cnt;

    };

    TT pop_front(){

    if (!cnt || !head) throw 0;

    DD<TT> *t = head;

    TT d = t->dd;

    head = head->nxt;

    if (head) head->prev = NULL; else tail = NULL;

    delete t;

    --cnt;

    return d;

    };

    TT pop_rear(){

    if (!cnt || !tail) throw 0;

    DD<TT> *t = tail;

    TT d = t->dd;

    tail = tail->prev;

    if (tail) tail->nxt = NULL; else head = NULL;

    delete t;

    --cnt;

    return d;

    };

    int count() {return cnt;};

    int dqPrint(){

    for(DD<TT> *t=head; t; t=t->nxt) cout << t->dd << " ";

    return cnt;

    }

    };

    int main(

    int gc,

    char **gv

    ){

    deQ<int> dqI;

    int ary[] = {1,5,-10,17};

    for(int i=sizeof(ary)/sizeof(ary[0])-1; i>=0; --i)

    cout << "push_rear the " << dqI.push_rear(ary[i]) << "th element=" << ary[i] << endl;

    cout << "size of q=" << dqI.count() << endl;

    dqI.dqPrint(); cout << endl;

    for(; dqI.count() > 0;) cout << "pop_rear=" << dqI.pop_rear() << endl;

    return 0;

    }

  • Anonymous
    7 years ago

    推薦你一個不錯的網站!!

    http://tt.gboy1069.com/

    我身邊也是有很多異性戀朋友,我也會介紹她們欣賞!!

    看日本的帥哥男優如何打扮、如何有型!

    甚至去看一些GV片(男同志影片)增加自己的性愛技巧。

    支持一下喔

  • 7 years ago

    你可以先學著寫非circular的deque,

    應該不難.

Still have questions? Get your answers by asking now.