链式堆栈.cpp

高效的链式堆栈算法

// 链式堆栈

#include <fstream>
#include <iostream>
#include <string>

using namespace std;

class Stack
{
    // the structure of each node
    struct Link
    {
        void* data;
        Link* next;
        Link(void* dat, Link* nxt);
    }* head;
public:
    Stack();
    void push(void* dat);
    void* peek();
    void* pop();
};

inline Stack::Link::Link(void* dat, Link* nxt)
{
    data = dat;
    next = nxt;
}

inline Stack::Stack()
{
    head = 0;
}

// push new data into the stack
void Stack::push(void* dat)
{
    head = new Link(dat, head);
}

// just return the top data
inline void* Stack::peek()
{
    if(head == 0)
        return 0;
    return head->data;
}

// pop the top data
void* Stack::pop()
{
    // stack is empty
    if(head == 0)
        return 0;
    void* result = head->data;
    Link* oldHead = head;
    head = head->next;
    delete oldHead;
    return result;
}

int main(int argc, char* argv[])
{
    ifstream in(argv[1]);
    Stack textlines;
    string line;
    
    while(getline(in, line))
        textlines.push(new string(line));
        
    string *s;
    while((s = (string*)textlines.pop()) != 0)
    {
        cout << *s << endl;
        delete s;
    }
}