c++ template queue,stack ( c++用template实现队列、栈数据结构）

  1 // Copyright 2005, Google Inc.
  2 // All rights reserved.
  3 //
  4 // Redistribution and use in source and binary forms, with or without
  5 // modification, are permitted provided that the following conditions are
  6 // met:
  7 //
  8 //     * Redistributions of source code must retain the above copyright
  9 // notice, this list of conditions and the following disclaimer.
 10 //     * Redistributions in binary form must reproduce the above
 11 // copyright notice, this list of conditions and the following disclaimer
 12 // in the documentation and/or other materials provided with the
 13 // distribution.
 14 //     * Neither the name of Google Inc. nor the names of its
 15 // contributors may be used to endorse or promote products derived from
 16 // this software without specific prior written permission.
 17 //
 18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 29 
 30 // A sample program demonstrating using Google C++ testing framework.
 31 //
 32 // Author: wan@google.com (Zhanyong Wan)
 33 
 34 #ifndef GTEST_SAMPLES_SAMPLE3_INL_H_
 35 #define GTEST_SAMPLES_SAMPLE3_INL_H_
 36 
 37 #include <stddef.h>
 38 #include <iostream>
 39 #include "Exception.h"
 40 
 41 // Queue is a simple queue implemented as a singled-linked list.
 42 //
 43 // The element type must support copy constructor.
 44 template <typename E>  // E is the element type
 45 class Queue;
 46 
 47 // QueueNode is a node in a Queue, which consists of an element of
 48 // type E and a pointer to the next node.
 49 template <typename E>  // E is the element type
 50 class QueueNode {
 51   friend class Queue<E>;
 52 
 53  public:
 54   // Gets the element in this node.
 55   const E& element() const { return element_; }
 56 
 57   // Gets the next node in the queue.
 58   QueueNode* next() { return next_; }
 59   const QueueNode* next() const { return next_; }
 60 
 61  private:
 62   // Creates a node with a given element value.  The next pointer is
 63   // set to NULL.
 64   explicit QueueNode(const E& an_element) : element_(an_element), next_(NULL) {}
 65 
 66   // We disable the default assignment operator and copy c'tor.
 67   const QueueNode& operator = (const QueueNode&);
 68   QueueNode(const QueueNode&);
 69 
 70   E element_;
 71   QueueNode* next_;
 72 };
 73 
 74 template <typename E>  // E is the element type.
 75 class Queue {
 76  public:
 77   // Creates an empty queue.
 78   Queue() : head_(NULL), last_(NULL), size_(0) {}
 79 
 80   // D'tor.  Clears the queue.
 81   ~Queue() { Clear(); }
 82 
 83   // Clears the queue.
 84   void Clear() {
 85     if (size_ > 0) {
 86       // 1. Deletes every node.
 87       QueueNode<E>* node = head_;
 88       QueueNode<E>* next = node->next();
 89       for (; ;) {
 90         delete node;
 91         node = next;
 92         if (node == NULL) break;
 93         next = node->next();
 94       }
 95 
 96       // 2. Resets the member variables.
 97       head_ = last_ = NULL;
 98       size_ = 0;
 99     }
100   }
101 
102   // Gets the number of elements.
103   size_t Size() const { return size_; }
104 
105   // Gets the first element of the queue, or NULL if the queue is empty.
106   QueueNode<E>* Head() { return head_; }
107   const QueueNode<E>* Head() const { return head_; }
108 
109   // Gets the last element of the queue, or NULL if the queue is empty.
110   QueueNode<E>* Last() { return last_; }
111   const QueueNode<E>* Last() const { return last_; }
112 
113   // Adds an element to the end of the queue.  A copy of the element is
114   // created using the copy constructor, and then stored in the queue.
115   // Changes made to the element in the queue doesn't affect the source
116   // object, and vice versa.
117   void Enqueue(const E& element) {
118     QueueNode<E>* new_node = new QueueNode<E>(element);
119 
120     if (size_ == 0) {
121       head_ = last_ = new_node;
122       size_ = 1;
123     } else {
124       last_->next_ = new_node;
125       last_ = new_node;
126       size_++;
127     }
128   }
129 
130   // Removes the head of the queue and returns it.  Returns NULL if
131   // the queue is empty.
132   E* Dequeue() {
133     if (size_ == 0) {
134       return NULL;
135     }
136 
137     const QueueNode<E>* const old_head = head_;
138     head_ = head_->next_;
139     size_--;
140     if (size_ == 0) {
141       last_ = NULL;
142     }
143 
144     E* element = new E(old_head->element());
145     delete old_head;
146 
147     return element;
148   }
149 
150   // Applies a function/functor on each element of the queue, and
151   // returns the result in a new queue.  The original queue is not
152   // affected.
153   template <typename F>
154   Queue* Map(F function) const {
155     Queue* new_queue = new Queue();
156     for (const QueueNode<E>* node = head_; node != NULL; node = node->next_) {
157       new_queue->Enqueue(function(node->element()));
158     }
159 
160     return new_queue;
161   }
162 
163  private:
164   QueueNode<E>* head_;  // The first node of the queue.
165   QueueNode<E>* last_;  // The last node of the queue.
166   size_t size_;  // The number of elements in the queue.
167 
168   // We disallow copying a queue.
169   Queue(const Queue&);
170   const Queue& operator = (const Queue&);
171 };
172 
173 #endif  // GTEST_SAMPLES_SAMPLE3_INL_H_

  1 #include <iostream>
  2 #include <cstdlib>
  3 using namespace std;
  4 
  5 // define default capacity of the queue
  6 #define SIZE 10
  7 
  8 // Class for queue
  9 template <class X>
 10 class queue 
 11 {
 12     X *arr;            // array to store queue elements
 13     int capacity;    // maximum capacity of the queue
 14     int front;        // front points to front element in the queue (if any)
 15     int rear;        // rear points to last element in the queue
 16     int count;        // current size of the queue
 17 
 18 public:
 19     queue(int size = SIZE);        // constructor
 20 
 21     void dequeue();
 22     void enqueue(X x);
 23     X peek();
 24     int size();
 25     bool isEmpty();
 26     bool isFull();
 27 };
 28 
 29 // Constructor to initialize queue
 30 template <class X>
 31 queue<X>::queue(int size)
 32 {
 33     arr = new X[size];
 34     capacity = size;
 35     front = 0;
 36     rear = -1;
 37     count = 0;
 38 }
 39 
 40 // Utility function to remove front element from the queue
 41 template <class X>
 42 void queue<X>::dequeue()
 43 {
 44     // check for queue underflow
 45     if (isEmpty())
 46     {
 47         cout << "UnderFlownProgram Terminatedn";
 48         exit(EXIT_FAILURE);
 49     }
 50 
 51     cout << "Removing " << arr[front] << 'n';
 52 
 53     front = (front + 1) % capacity;
 54     count--;
 55 }
 56 
 57 // Utility function to add an item to the queue
 58 template <class X>
 59 void queue<X>::enqueue(X item)
 60 {
 61     // check for queue overflow
 62     if (isFull()) 
 63     {
 64         cout << "OverFlownProgram Terminatedn";
 65         exit(EXIT_FAILURE);
 66     }
 67 
 68     cout << "Inserting " << item << 'n';
 69 
 70     rear = (rear + 1) % capacity;
 71     arr[rear] = item;
 72     count++;
 73 }
 74 
 75 // Utility function to return front element in the queue
 76 template <class X>
 77 X queue<X>::peek()
 78 {
 79     if (isEmpty()) 
 80     {
 81         cout << "UnderFlownProgram Terminatedn";
 82         exit(EXIT_FAILURE);
 83     }
 84     return arr[front];
 85 }
 86 
 87 // Utility function to return the size of the queue
 88 template <class X>
 89 int queue<X>::size()
 90 {
 91     return count;
 92 }
 93 
 94 // Utility function to check if the queue is empty or not
 95 template <class X>
 96 bool queue<X>::isEmpty()
 97 {
 98     return (size() == 0);
 99 }
100 
101 // Utility function to check if the queue is full or not
102 template <class X>
103 bool queue<X>::isFull()
104 {
105     return (size() == capacity);
106 }
107 
108 // main function
109 int main()
110 {
111     // create a queue of capacity 4
112     queue<string> q(4);
113 
114     q.enqueue("a");
115     q.enqueue("b");
116     q.enqueue("c");
117     
118     cout << "Front element is: " << q.peek() << endl;
119     q.dequeue();
120     
121     q.enqueue("d");
122 
123     cout << "Queue size is " << q.size() << endl;
124 
125     q.dequeue();
126     q.dequeue();
127     q.dequeue();
128     
129     if (q.isEmpty())
130         cout << "Queue Is Emptyn";
131     else
132         cout << "Queue Is Not Emptyn";
133 
134     return 0;
135 }

 1 #ifndef _STACK_H_
 2 #define _STACK_H_
 3 
 4 #include <iostream>
 5 #include "Exception.h"
 6 
 7 template <class T>
 8 class Stack {
 9     public:
10         Stack():top(0) {
11             std::cout << "In Stack constructor" << std::endl;
12         }
13         ~Stack() {
14             std::cout << "In Stack destructor" << std::endl;
15             while ( !isEmpty() ) {
16                 pop();
17             }
18             isEmpty();
19         }
20 
21         void push (const T& object);
22         T pop();
23         const T& topElement();
24         bool isEmpty();
25 
26     private:
27         struct StackNode {              // linked list node
28             T data;                     // data at this node
29             StackNode *next;            // next node in list
30 
31             // StackNode constructor initializes both fields
32             StackNode(const T& newData, StackNode *nextNode)
33                 : data(newData), next(nextNode) {}
34         };
35 
36         // My Stack should not allow copy of entire stack
37         Stack(const Stack& lhs) {}
38 
39         // My Stack should not allow assignment of one stack to another
40         Stack& operator=(const Stack& rhs) {}
41         StackNode *top;                 // top of stack
42 
43 };
44 
45 template <class T>
46 void Stack<T>::push(const T& obj) {
47     std::cout << "In PUSH Operation" << std::endl;
48     top = new StackNode(obj, top);
49 }
50 
51 template <class T>
52 T Stack<T>::pop() {
53     std::cout << "In POP Operation" << std::endl;
54     if ( !isEmpty() ) {
55         StackNode *topNode = top;
56         top = top->next;
57         T data = topNode->data;
58         delete topNode;
59         return data;
60     }
61     throw StackException ("Empty Stack");
62     //return 0;
63 }
64 
65 template <class T>
66 const T& Stack<T>::topElement() {
67     std::cout << "In topElement Operation" << std::endl;
68     if ( !isEmpty() ) {
69         return top->data;
70     }
71 }
72 
73 template <class T>
74 bool Stack<T>::isEmpty() {
75     if (top == 0) {
76         return true;
77     }
78     else {
79         return false;
80     }
81 }
82 
83 #endif 

 1 #include "template.h"
 2 
 3 class Student {
 4     private:
 5         std::string name;
 6         std::string course;
 7         int age;
 8 
 9     public:
10         Student(std::string n, std::string c, int a) : name(n), course (c) {
11             //std::cout << "In STUDENT constructor" << std::endl;
12             age = a;
13         }
14 
15         ~Student() {
16             //std::cout << "In STUDENT destructor" << std::endl;
17         }
18 
19         std::string getName() {
20             return name;
21         }
22 
23         std::string getCourse() {
24             return course;
25         }
26 
27         int getAge() {
28             return age;
29         }
30 };
31 
32 int main () {
33     Stack <Student> studentStack;
34 
35     Student s1( "Student1" , "Course1", 21);
36     Student s2( "Student2" , "Course2", 22);
37 
38     studentStack.push ( s1 );
39     studentStack.push ( s2 );
40 
41     try {
42         Student s3 = studentStack.pop();
43         std::cout << "Student Details: " << s3.getName() << ", " << s3.getCourse() << ", " << s3.getAge() << std::endl;
44 
45         Student s4 = studentStack.pop();
46         std::cout << "Student Details: " << s4.getName() << ", " << s4.getCourse() << ", " << s4.getAge() << std::endl;
47 
48         Student s5 = studentStack.pop();
49         std::cout << "Student Details: " << s5.getName() << ", " << s5.getCourse() << ", " << s5.getAge() << std::endl;
50     } catch (StackException& se) {
51         se.what();
52     }
53 }

 1 #include <iostream>
 2 #include <string>
 3 
 4 class StackException {
 5     public:
 6         StackException(std::string s) : str(s) {}
 7         ~StackException() {}
 8         void what() {
 9             std::cout << str << std::endl;
10         }
11 
12     private:
13         std::string str;
14 };