C++を使用して、テンプレートを使用して、チェーンスタックを実現します。

#ifndef Stack_h
#define Stack_h
 
template <class T>
class Stack {
public:
  Stack(){}; //     
  void Push(const T x); //      
  bool Pop(); //       
  virtual bool getTop(T &x) const = 0; //       ， x  
  virtual bool isEmpty() const = 0; //      
  // virtual bool isFull() const = 0; //      ,             
  virtual int getSize() const = 0; //         
};
 
 
#endif /* Stack_h */

#ifndef LinkedStack_h
#define LinkedStack_h
#include <iostream>
#include "Stack.h"
using namespace std;
 
template <class T>
struct LinkNode {
  T data;
  LinkNode<T> *link;
};
 
//      
template <class T>
class LinkedStack;
 
//       
template <class T>
ostream& operator<<(ostream& out, LinkedStack<T>& s);
template <class T>
class LinkedStack: public Stack<T> {
public:
  LinkedStack(); //     
  ~LinkedStack();//     
  void Push(const T x); //   
  bool Pop(); //   
  bool getTop(T &x) const; //       
  bool isEmpty()const; //        
  int getSize()const; //        
  void makeEmpty(); //       
  friend ostream& operator << <T>(ostream& out, LinkedStack<T>& s); //       
private:
  LinkNode<T> *top; //     ，     
};
template <class T>
LinkedStack<T>::LinkedStack() {
  //     ，   
  top = new LinkNode<T>(); //      ：     
  top->link = NULL;
}
template <class T>
LinkedStack<T>::~LinkedStack() {
  //     ,      
  makeEmpty();
}
template <class T>
void LinkedStack<T>::Push(const T x) {
  //   ：    x         ，   
  LinkNode<T> *newNode = new LinkNode<T>(); //     x    
  if(newNode == NULL) {
    cerr << "        ！" << endl;
    exit(1);
  }
  newNode->data = x;
  newNode->link = top->link; //            ：               
  top->link = newNode; //       
}
template <class T>
bool LinkedStack<T>::Pop() {
  //   ：      
  if(isEmpty())
    return false; //   ，   
  LinkNode<T> *p = top->link; //       
  top->link = p->link; //             
  delete p;
  p = NULL;
  return true;
}
 
template <class T>
bool LinkedStack<T>::getTop(T &x) const {
  //       
  if(isEmpty())
    return false;
  x = top->link->data; //    ，        。  top    ，       ：top->link
  return true;
}
 
template <class T>
bool LinkedStack<T>::isEmpty()const {
  //        
  if(top->link == NULL) //    
    return true;
  return false;
}
 
template <class T>
int LinkedStack<T>::getSize()const {
  //        
  int len = 0;
  
  LinkNode<T> *current = top->link;
  while(current != NULL) {
    len++;
    current = current->link;
  }
  return len;
}
 
template <class T>
void LinkedStack<T>::makeEmpty() {
  //       
  LinkNode<T> *current = top->link;
  while(current != NULL) {
    top->link = current->link; //                    ，    
    delete current; //   
    current = NULL; //     
    current = top->link; //            
  }
}
 
template <class T>
ostream& operator<<(ostream& out, LinkedStack<T>& s) {
  //       
  LinkNode<T> *current = s.top->link;
  while(current != NULL) {
    out << current->data << " ";
    current = current->link;
  }
  return out;
}
#endif /* LinkedStack_h */

#include "LinkedStack.h"
using namespace std;
 
int main(int argc, const char * argv[]) {
  int n, x, choice, len; // val   ，choose       
  bool finished = false;
  LinkedStack<int> L; //   
  
  while(!finished) {
    cout << "1:  ：" << endl;
    cout << "2:  " << endl;
    cout << "3:  ：" << endl;
    cout << "4:      ：" << endl;
    cout << "5:     ：" << endl;
    cout << "6:       ：" << endl;
    cout << "7:      ：" << endl;
    cout << "8:        ：" << endl;
    cout << "9:  " << endl;
    cout << "       [1-9]：" << endl;
    cin >> choice;
    switch(choice) {
      case 1:
        cout << "           :";
        cin >> n;
        cout << "        (     )：" << endl;
        for(int i=0; i < n; i++) {
          cin >> x;
          L.Push(x);
        }
        break;
      case 2:
        cout << "        :";
        cin >> x;
        L.Push(x);
        break;
      case 3:
        if(L.Pop())
          cout << "    !" << endl;
        else
          cout << "   !" << endl;
        break;
      case 4:
        if(L.getTop(x))
          cout << "       ：" << x << endl;
        else
          cout << "   !" << endl;
        break;
      case 5:
        if(L.isEmpty())
          cout << "   ！" << endl;
        else
          cout << "    !" << endl;
        break;
      case 6:
        len = L.getSize();
        cout << "        ：" << len << endl;
        break;
      case 7:
        L.makeEmpty(); //    
        break;
      case 8:
        if(L.isEmpty())
          cout << "   ！" << endl;
        else
          cout << L << endl;
        break;
      case 9:
        finished = true;
        break;
      default:
        cout << "    ，     !" << endl;
    } // switch
  } // while
  return 0;
}