随笔-13  评论-0  文章-2  trackbacks-0
栈的实现（顺序结构）Alpha 2.0
/**
 Stack(use array to implement)
 Version: 2.0
  Member function as follow:
  Size()
  Push(T)        // inset an elm
  Pop()        // delete the last elm
  Empty()         // if it is an empty list
  Print()
  Update Logfile:
            1. optimize  the member function.
            2. add the standard excetption
            3. ehance the logical struct
            4. be more simple to use
            5. can be enlarged automatly
            6. use dynamic allocatin
        Unresolved problem:
            there are still some problem in my stack class.
            it will be sovled in the next version.
  this time i also Use C++ template
**/
 1#include<iomanip>
 2#include<stdexcept>
 3#include<iostream>
 4using namespace std;
 5
 6template<typename T>
 7class Stack {
 8public:
 9    Stack():stack(new T [5]),size(5),sp(-1){}     // first allocate five room
10    bool Empty() const { return sp == -1; }      // judge empty ?
11    int Size() const { return sp + 1; }          // return the size
12    T& Top() const { return *(stack + sp); }     // return the top element
13    void Pop();                                  // delete the top element
14    void Push(const T& one);                     // Push an element
15    void Print() const;                          // Print the stack element
16private:
17    T* stack;
18    int size;
19    int sp;
20    bool extend(int s = 10);
21};
22
23template<typename T>void Stack<T>::Pop() {
24    if(Empty()) throw range_error("has empty"); // Empty-> exception
25    else{
26        stack[sp--];                       // delete an element
27    }
28}
29
30template<typename T>void Stack<T>::Push(const T& one) {
31    if(sp + 1 == size) {                       // it's full ,extend it
32        if(!extend(2 * size)) throw bad_alloc();
33    }
34    stack[++sp] = one;                         // fill the top
35}
36
37template<typename T>bool Stack<T>::extend(int s /*=10*/) {
38    T* temp = new T [s];
39    if(temp == NULL) return false;             // allocate fail
40    for(int i = 0; i < size; i++)              // copy all element from stack
41        *(temp + i) = *(stack + i);
42    delete [] stack;                           // release the stack
43    stack = temp;
44    delete [] temp;                            // release the temp
45    temp = NULL;
46    return true;                               // allocate successfully
47}
48
49template<typename T>void Stack<T>::Print() const {
50    for(int i = sp; i >= 0; i--) {
51        cout << setw(4) << *(stack + i);
52    }
53    cout << endl;
54}

Test function::
 1int main()
 2{
 3    using namespace std;
 4    Stack<int> stack;
 5    cout << "----------------Display the stack program-----------------------" << endl;
 6    cout << "\n Initial the stack,please input the number of element to push stack "<< endl;
 7    cout << "number = " ;
 8    int number;
 9    cin >> number;
10    cout << "Secondly input the number in the following\n" << endl;
11    int temp;
12    for( int i = 0; i < number; i++ )
13    {
14        cin >> temp;
15        stack.Push(temp);
16    }
17    cout << "You Input As Follow" << endl;
18    stack.Print();
19    cout << "Would you like to display the pop functionYes or No" << endl;
20    string answer;
21    cin >> answer;
22    if( answer == "yes" || answer == "YES" || answer == "Yes")
23    {
24        stack.Pop();
25        stack.Print();
26    }
27    cout <<"-----------------------------------------------------------------" << endl;
28    system("pause");
29    return 0;
30
31}
32

posted on 2009-04-27 16:33 亦夏 阅读(246) 评论(0)  编辑 收藏 引用 所属分类: DataStruct

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 亦夏