今天在看单元测试的时候无意中看到google gtest的例子有个实现Queue队列的数据结构它是用单链表实现的。索性今天就分享一下队列和栈这两种实现方法。
Queue
单链表实现
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 << "UnderFlow\nProgram Terminated\n"; 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 << "OverFlow\nProgram Terminated\n"; 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 << "UnderFlow\nProgram Terminated\n"; 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 Empty\n"; 131 else 132 cout << "Queue Is Not Empty\n"; 133 134 return 0; 135 }
Stack
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 };