模版链栈实现

Published at发布于:： 2013-10-04 | PV/UV: / | Reading阅读:： 3 min

栈只具备入栈和出栈的性质，实现起来较为简单，其本质还是链表，只不过限制了任意节点的访问权限，因此栈不具备迭代器的功能。代码中注释了一个迭代器，是测试代码时写的，迭代效果略有Bug，访问数据会多访问到一个，但不影响栈本身的功能，无视就好～ p.s. 可以考虑重载[]来实现栈中的数据访问。。当然这是后话了。。

//
//  Stack.h
//  链栈
//
//  Created by 欧 长坤 on 13-10-4.
//  Copyright (c) 2013年 欧 长坤. All rights reserved.
//

#ifndef ______Stack__
#define ______Stack__

#include <iostream>

template <class T> class Stack;
template <class T> class StackStackNode;
//template <class T> class StackIterator;
template <class T>
class StackNode {

    friend class Stack<T>;
    //friend class StackIterator<T>; // 用于测试迭代器而添加

private:
    T data;
    StackNode<T> *next;
};

template <class T>
class Stack {

    //friend class StackIterator<T>; // 用于测试迭代器而添加

private:

    StackNode<T> *Top;
    StackNode<T> *Bottom;
    size_t Size;

public:
    Stack();
    ~Stack();
    T top();
    void push(T value);
    bool pop();
    bool isEmpty();
    void clear();
    size_t size();
};

// 迭代器用于测试push是否成功而写

// 链栈迭代器
// 使用方法：
// int *x;
// StackIterator<int> inter;
// x = inter.initialize(XXX); // XXX是栈
// while (inter) {
//      cout << *x << ' ';
//      x = inter.next();
// }
/*
template <class T>
class StackIterator
{
private:

    StackNode<T> *location;

public:

    T* initialize(const Stack<T>&amp; stack)
    {
        location = stack.Top;
        if (location)
            return &amp;location->data;
        return 0;
    }
    T* next()
    {
        if (!location)
            return &amp;location->data;
        location = location->next;
        if (location) {
            return &amp;location->data;
        }
        return 0;
    }

};
*/

template <class T>
Stack<T>::Stack()
{
    Top = new StackNode<T>;
    if (NULL == Top) {
        throw "Out of Memory!";
    } else {
        Bottom = Top;
        Top->next = NULL;
    }
    Size = 0;
}

template <class T>
Stack<T>::~Stack()
{
    delete Top;
    Top = Bottom = NULL;
    Size = 0;
}

template <class T>
void Stack<T>::push(T value)
{
    StackNode<T> *newStackNode = new StackNode<T>;
    if (NULL == newStackNode) {
        throw "Out Of Memory!";
    }
    newStackNode->data = value;
    newStackNode->next = Top;
    Top = newStackNode;
    Size++;
}

template <class T>
bool Stack<T>::pop()
{
    if (isEmpty()) {
        return false;
    } else {
        StackNode<T> *p = Top;
        Top = p->next;
        delete p;
        return true;
    }
    Size--;
}

template <class T>
bool Stack<T>::isEmpty()
{
    if (Top == Bottom)
        return true;
    else
        return false;
}

template <class T>
void Stack<T>::clear()
{
    if (isEmpty())
        return;
    else {
        StackNode<T> *p = Top, *q;
        while (p != Bottom) {
            q = p->next;
            delete p;
            p = q;
        }
        Top = Bottom;
    }
    Size = 0;
}

template <class T>
T Stack<T>::top()
{
    return Top->data;
}

template <class T>
size_t Stack<T>::size()
{
    return Size;
}

#endif /* defined(______Stack__) */

推荐订阅源

Posts on Changkun's Blog

模版链栈实现