LinkedListStack

  链式栈：就是一种操作受限的单向链表，每次入栈一个元素，向链表中添加一个节点，出栈一个元素，释放一个节点。因为栈具有“后进先出”的特点，如果每次在链表的尾部进行插入和删除，就要遍历整个链表来找到尾节点。而在头部进行插入和删除时，只需根据头指针即可找到链表的首元素结点。而无需遍历链表。所以链式栈的出，入栈通过对链表进行头删和头插来实现。

LinkedList

代码清单

LinkedListStack.h

#ifndef C___LINKEDLISTSTACK_H
#define C___LINKEDLISTSTACK_H
#include "LinkedList.h"
template<typename T>
class Stack {
public:
    virtual int getSize()const = 0;
    virtual bool isEmpty()const = 0;
    virtual void push(T& e) = 0;
    virtual T pop() = 0;
    virtual T peek()const = 0;
};

template<typename T>
class LinkedListStack : public Stack<T> {
public:
    LinkedListStack();
    int getSize()const;
    bool isEmpty()const;
    void push(T&e);
    T pop();
    T peek()const;
    void print()const;
private:
    LinkedList<T>*list;
};

template<typename T>
int LinkedListStack<T>::getSize() const {
    return list->getSize();
}

template<typename T>
bool LinkedListStack<T>::isEmpty() const {
    return list->isEmpty();
}

template<typename T>
void LinkedListStack<T>::push(T& e) {
    list->addFirst(e);
}

template<typename T>
T LinkedListStack<T>::pop() {
    return list->removeFirst();
}

template<typename T>
T LinkedListStack<T>::peek()const {
    return list->getFirst();
}

template<typename T>
void LinkedListStack<T>::print() const {
    std::cout << "Stack: size = " << list->getSize() << std::endl;
    std::cout << "bottom ";
    list->print();
    std::cout << " top" << std::endl;
}

template<typename T>
LinkedListStack<T>::LinkedListStack() {
    list = new LinkedList<T>();
}

#endif //C___LINKEDLISTSTACK_H

main.cpp

int LinkedListStack()
{
   LinkedListStack<int>*ls = new LinkedListStack<int>();
   for(int i = 0;i<10;++i)
   {
       ls->push(i);
       ls->print();
   }
   cout<<"isEmpty()"<<ls->isEmpty()<<endl;
   cout<<"getSize()"<<ls->getSize()<<endl;
   cout<<"peek"<<ls->peek()<<endl;
   cout<<"pop"<<ls->pop()<<endl;
   ls->print();
   return 0;
}