大胖的部落格

Just a note
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  112 随笔 :: 0 文章 :: 3 评论 :: 0 Trackbacks
数据结构 ---- 堆栈
分别用链表和线性表实现的堆栈：
#include "stdafx.h"
#include <iostream>

using namespace std;

///////////////// Chain//////////////
template <class T> class LinkedStack;

template <class T>
class Node {
    friend LinkedStack<T>;
    T    data;
    Node<T>* link;
};

template <class T>
class LinkedStack {
public:
    LinkedStack(){top = NULL;}
    ~LinkedStack();
    bool IsEmpty() const {return NULL==top;}
    T Top() const;
    LinkedStack<T>& Add(const T& t);
    LinkedStack<T>& Delete(T& t);
private:
    Node<T>* top;
};

template<class T>
LinkedStack<T>::~LinkedStack()
{
    Node<T>* next = top;
    while(NULL != next) {
        top = next->link;
        delete next;
        next = top;
    }
}

template<class T>
T LinkedStack<T>::Top() const 
{
    if(NULL != top) {
        return top->data;
    }
}

template<class T>
LinkedStack<T>& LinkedStack<T>::Add(const T& t)
{
    Node<T>* p = new Node<T>;
    p->data = t;
    p->link = top;
    top = p;
    return *this;
}

template<class T>
LinkedStack<T>& LinkedStack<T>::Delete(T& t)
{
    if(NULL !=top ) {
        t = top->data;
        Node<T>* p = top;
        top = top->link;
        delete p;
    }
    return *this;
}

/////////// LinearList////////////////

template <class T>
class Stack {
public:
    Stack(int iSize = 10);
    ~Stack() {delete []stack;}
    bool IsEmpty() const {return -1 == top;}
    bool IsFull() const {return MaxSize-1 == top;}
    T Top() const;
    Stack<T>& Add(const T& t);
    Stack<T>& Delete(T& t);
private:
    T*    stack;
    int    top;        //index, the bottom is 0
    int MaxSize;
};

template <class T>
Stack<T>::Stack(int iSize)
{
    stack = new T[iSize];
    top = -1;
    MaxSize = iSize;
}

template<class T>
T Stack<T>::Top() const
{
    if(-1 != top) {
        return stack[top];
    }
}

template<class T>
Stack<T>& Stack<T>::Add(const T& t)
{
    if(MaxSize-1 != top) {
        ++top;
        stack[top] = t;
    }
    return *this;
}

template<class T>
Stack<T>& Stack<T>::Delete(T& t)
{
    if(0 != top) {
        t = stack[top];
        --top;
    }
    return *this;
}


int main ()
{
    /*int i = 0;
    LinkedStack<int> a;
    a.Add(1);
    cout<<a.Top()<<endl;
    a.Add(5);
    cout<<a.Top()<<endl;
    a.Delete(i);
    cout<<a.Top()<<endl;
    cout<<i<<endl;
    a.Delete(i);
    cout<<a.Top()<<endl;*/

    int i = 0;
    Stack<int> s;
    s.Add(1);
    cout<<s.Top()<<endl;
    s.Add(2);
    cout<<s.Top()<<endl;
    s.Delete(i);
    cout<<s.Top()<<endl;
    cout<<i<<endl;

    return 0;
}

posted on 2009-06-29 10:56 大胖 阅读(181) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

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