棧的鏈表實現

1)list.h

/*
 * list_2.cpp
 *
 *  Created on: 2013年8月2日
 *      Author: 黃東東
 *      為了能有章澤天這樣的女朋友而不斷努力。。。。。。
 */ 
 
#include <iostream>  
 
using namespace std; 
 
typedef int T; 
 
class List { 
    struct Node { 
 
        T data; 
        Node* next; 
        Node(const T& d = T()) : 
                data(d), next(0) { 
 
        } 
 
    }; 
 
    Node* head; 
    int len; 
 
public: 
    List() : 
            head(NULL), len(0) { 
 
    } 
 
    ~List() { 
        clear(); 
    } 
 
    void insert(const T& d, int pos) { 
 
        Node*& pn = getptr(pos); 
        Node* p = new Node(d); 
        p->next = pn; 
        pn = p; 
        ++len; 
    } 
 
    void push_front(const T& d) { 
        insert(d, 0); 
    } 
 
    List& push_back(const T& d) { 
        insert(d, size()); 
 
        return *this; 
    } 
 
    void clear() { 
        Node* p; 
        while (head != NULL) { 
            p = head->next; 
            delete head; 
            head = p; 
        } 
    } 
 
    void erase(int pos) { 
        if (pos < 0 || pos >= size()) { 
            return; 
        } 
 
        Node*& pn = getptr(pos); 
        Node* p = pn; 
        pn = pn->next; 
        delete p; 
        --len; 
    } 
 
    void remove(const T& d) { 
        int pos; 
        while ((pos = find(d)) != -1) { 
            erase(pos); 
        } 
    } 
 
    void set( int pos,const T& d) { 
        if (pos < 0 || pos >= size()) { 
            return; 
        } 
 
        getptr(pos)->data = d; 
    } 
 
    Node*& getptr(int pos) { 
 
        if (pos < 0 || pos > size()) { 
            pos = 0; 
        } 
 
        if (pos == 0) { 
            return head; 
        } 
 
        Node* p = head; 
 
        for (int i = 1; i < pos; ++i) { 
            p = p->next; 
        } 
 
        return (*p).next; 
 
    } 
 
     int find(const T& d) { 
        Node* p = head; 
        int pos = 0; 
        while (p) { 
            if (p->data == d) { 
                return pos; 
            } 
 
            p = p->next; 
            pos++; 
        } 
 
        return -1; 
    } 
 
    const int& front() { 
        if (empty()) { 
            throw "空"; 
        } 
        return head->data; 
    } 
 
    int back() { 
        if (empty()) { 
            throw "空"; 
        } 
 
        Node* p = head; 
 
        while (p->next != NULL) { 
            p = p->next; 
        } 
 
        return (*p).data; 
    } 
 
    bool empty() { 
        return head == NULL; 
    } 
 
    int size() { 
        return len; 
    } 
 
    void travel() { 
        Node* p = head; 
 
        while (p != NULL) { 
 
            cout << p->data << ' '; 
            p = p->next; 
        } 
 
        cout<<endl; 
    } 
}; 
 
//int main(){  
//  List l;  
//  l.push_front(5);//5  
//  l.push_front(8);//8 5  
//  l.push_front(20);//20 8 5  
//  l.insert(9, 2);//20 8 9 5  
//  l.insert(6, 100);//6 20 8 9 5  
//  l.insert(7, -10);//7 6 20 8 9 5  
//  l.insert(1, 2);//7 6 1 20 8 9 5  
//  
//  //7 6 1 20 8 9 5 10 15  
//  l.push_back(10).push_back(15).travel();  
//  
//  
//  l.erase(0);//6 1 20 8 9 5 10 15  
//  l.erase(l.size() - 1);//6 1 20 8 9 5 10  
//  l.erase(2);//6 1 8 9 5 10  
//  l.travel();  
//  
//  l.push_back(6);//6 1 8 9 5 10 6  
//  l.insert(6,3);//6 1 8 6 9 5 10 6  
//  l.travel();  
//  
//  l.remove(6);//1 8 9 5 10  
//  l.travel();  
//  
//  l.set(0,666);//666 8 9 5 10  
//  l.set(4,789);//666 8 9 5 789  
//  l.set(l.find(9),123);//666 8 123 5 789  
//  l.set(1,777);//666 777 123 5 789  
//  l.travel();  
//  
//  cout<<l.front()<<"...."<<l.back()<<','<<l.size()<<endl;  
//  
//  while(!l.empty()){  
//      l.erase(0);  
//  }  
//  
//  cout<<"size: "<<l.size()<<endl;  
//} 

/*
 * list_2.cpp
 *
 *  Created on: 2013年8月2日
 *      Author: 黃東東
 *      為了能有章澤天這樣的女朋友而不斷努力。。。。。。
 */

#include <iostream>

using namespace std;

typedef int T;

class List {
 struct Node {

  T data;
  Node* next;
  Node(const T& d = T()) :
    data(d), next(0) {

  }

 };

 Node* head;
 int len;

public:
 List() :
   head(NULL), len(0) {

 }

 ~List() {
  clear();
 }

 void insert(const T& d, int pos) {

  Node*& pn = getptr(pos);
  Node* p = new Node(d);
  p->next = pn;
  pn = p;
  ++len;
 }

 void push_front(const T& d) {
  insert(d, 0);
 }

 List& push_back(const T& d) {
  insert(d, size());

  return *this;
 }

 void clear() {
  Node* p;
  while (head != NULL) {
   p = head->next;
   delete head;
   head = p;
  }
 }

 void erase(int pos) {
  if (pos < 0 || pos >= size()) {
   return;
  }

  Node*& pn = getptr(pos);
  Node* p = pn;
  pn = pn->next;
  delete p;
  --len;
 }

 void remove(const T& d) {
  int pos;
  while ((pos = find(d)) != -1) {
   erase(pos);
  }
 }

 void set( int pos,const T& d) {
  if (pos < 0 || pos >= size()) {
   return;
  }

  getptr(pos)->data = d;
 }

 Node*& getptr(int pos) {

  if (pos < 0 || pos > size()) {
   pos = 0;
  }

  if (pos == 0) {
   return head;
  }

  Node* p = head;

  for (int i = 1; i < pos; ++i) {
   p = p->next;
  }

  return (*p).next;

 }

     int find(const T& d) {
  Node* p = head;
  int pos = 0;
  while (p) {
   if (p->data == d) {
    return pos;
   }

   p = p->next;
   pos++;
  }

  return -1;
 }

 const int& front() {
  if (empty()) {
   throw "空";
  }
  return head->data;
 }

 int back() {
  if (empty()) {
   throw "空";
  }

  Node* p = head;

  while (p->next != NULL) {
   p = p->next;
  }

  return (*p).data;
 }

 bool empty() {
  return head == NULL;
 }

 int size() {
  return len;
 }

 void travel() {
  Node* p = head;

  while (p != NULL) {

   cout << p->data << ' ';
   p = p->next;
  }

  cout<<endl;
 }
};

//int main(){
// List l;
// l.push_front(5);//5
// l.push_front(8);//8 5
// l.push_front(20);//20 8 5
// l.insert(9, 2);//20 8 9 5
// l.insert(6, 100);//6 20 8 9 5
// l.insert(7, -10);//7 6 20 8 9 5
// l.insert(1, 2);//7 6 1 20 8 9 5
//
// //7 6 1 20 8 9 5 10 15
// l.push_back(10).push_back(15).travel();
//
//
// l.erase(0);//6 1 20 8 9 5 10 15
// l.erase(l.size() - 1);//6 1 20 8 9 5 10
// l.erase(2);//6 1 8 9 5 10
// l.travel();
//
// l.push_back(6);//6 1 8 9 5 10 6
// l.insert(6,3);//6 1 8 6 9 5 10 6
// l.travel();
//
// l.remove(6);//1 8 9 5 10
// l.travel();
//
// l.set(0,666);//666 8 9 5 10
// l.set(4,789);//666 8 9 5 789
// l.set(l.find(9),123);//666 8 123 5 789
// l.set(1,777);//666 777 123 5 789
// l.travel();
//
// cout<<l.front()<<"...."<<l.back()<<','<<l.size()<<endl;
//
// while(!l.empty()){
//  l.erase(0);
// }
//
// cout<<"size: "<<l.size()<<endl;
//}

 

2)stack.cpp

 * stack_1.cpp
 *
 *  Created on: 2013年8月2日
 *    為了能有章澤天這樣的女朋友而不斷努力。。。。。。
 *    加油。。。fighting。。。。。
 */ 
 
#include <iostream>  
#include "list_2.h"  
 
using namespace std; 
 
class Stack{ 
    List l; 
public: 
    void push(const T& d){ 
        l.push_front(d); 
    } 
 
    T pop(){ 
 
        T t = l.front(); 
        l.erase(0); 
        return t; 
    } 
 
    const T& top(){ 
 
        return l.front(); 
    } 
 
    bool empty(){ 
 
        return l.empty(); 
    } 
 
    bool full(){ 
 
        return false; 
    } 
 
    void clear(){ 
 
        l.clear(); 
    } 
 
    int size(){ 
 
        return l.size(); 
    } 
}; 
int main(){ 
 
    Stack s; 
    s.push(2); 
    s.push(4); 
    s.push(6); 
    s.push(8); 
    s.push(10); 
 
    while(!s.empty()){ 
        cout<< s.pop()<<endl; 
    } 
} 

/*
 * stack_1.cpp
 *
 *  Created on: 2013年8月2日
 *    為了能有章澤天這樣的女朋友而不斷努力。。。。。。
 *    加油。。。fighting。。。。。
 */

#include <iostream>
#include "list_2.h"

using namespace std;

class Stack{
 List l;
public:
 void push(const T& d){
  l.push_front(d);
 }

 T pop(){

  T t = l.front();
  l.erase(0);
  return t;
 }

 const T& top(){

  return l.front();
 }

 bool empty(){

  return l.empty();
 }

 bool full(){

  return false;
 }

 void clear(){

  l.clear();
 }

 int size(){

  return l.size();
 }
};
int main(){

 Stack s;
 s.push(2);
 s.push(4);
 s.push(6);
 s.push(8);
 s.push(10);

 while(!s.empty()){
  cout<< s.pop()<<endl;
 }
}