[C++]Stack with Template
17102 ワード
Stack with Template
Description:
Requirement:
In this assignment, you are required to finish the Stack with Template. Please modify class Stack’s declaration and definition so as to finish the validation from main.cpp
Attention: please use template you have learned in the class to finish this assignment and DON NOT add and modify any memeber function and member variable.
Warning: Do not use Stack in STL. Do not use array of Node to finish the definition of some function. Extra:
The Stack’s declaration with element type “int” is below:
class Stack { public: Stack() ;
private: struct Node { int element; Node* next; Node(int ele, Node *n = NULL) { element = ele; next = n; } }; Node *top_node; size_t node_num; };
Analysis: This question has some important knowledge point which needs be cared, like swap, reverse, construct procedure and so on. It is neccessary to be familiar with that codes.
answer:
Test:
Description:
Requirement:
In this assignment, you are required to finish the Stack with Template. Please modify class Stack’s declaration and definition so as to finish the validation from main.cpp
Attention: please use template you have learned in the class to finish this assignment and DON NOT add and modify any memeber function and member variable.
Warning:
The Stack’s declaration with element type “int” is below:
class Stack { public: Stack() ;
Stack(const Stack &stack);
~Stack();
bool empty();
size_t size() const;
int top() const;
void push(int element);
void pop();
void swap(Stack& stack);
void reverse(); /*reverse the elements' order in the stack*/
void clear();
private: struct Node { int element; Node* next; Node(int ele, Node *n = NULL) { element = ele; next = n; } }; Node *top_node; size_t node_num; };
Analysis: This question has some important knowledge point which needs be cared, like swap, reverse, construct procedure and so on. It is neccessary to be familiar with that codes.
answer:
#include<iostream>
#include<cstddef>
using namespace std;
template <typename ElementType>
class Stack {
public:
Stack() {
top_node = NULL;
node_num = 0;
}
Stack(const Stack<ElementType> &stack) {
if (this == &stack) return;
top_node = NULL;
node_num = 0;
if (stack.top_node == NULL) return;
Node *copy_temp = stack.top_node;
Node *top_temp = NULL;
while (copy_temp) {
if (top_temp == NULL) {
top_node = new Node(copy_temp->element);
top_temp = top_node;
} else {
top_node->next = new Node(copy_temp->element);
top_node = top_node->next;
}
copy_temp = copy_temp->next;
}
top_node = top_temp;
node_num = stack.node_num;
}
~Stack() {
clear();
}
bool empty() {
return (node_num == 0);
}
size_t size() const {
return node_num;
}
ElementType top() const {
return top_node->element;
}
void push(ElementType element) {
if (top_node == NULL) {
top_node = new Node(element);
} else {
Node*temp = new Node(element, top_node);
top_node = temp;
}
++node_num;
}
void pop() {
if (top_node == NULL) return;
Node *temp = top_node;
top_node = top_node->next;
delete temp;
--node_num;
}
void swap(Stack<ElementType>& stack) {
// swap the pointer is much easier!!!
Node* temp = top_node;
top_node = stack.top_node;
stack.top_node = temp;
size_t temp_num = node_num;
node_num = stack.node_num;
stack.node_num = temp_num;
}
void reverse() {
if (node_num <= 1) return;
Stack<ElementType> temp;
while (!empty()) {
temp.push(top());
pop();
}
swap(temp);
}
void clear() {
while (!empty()) pop();
}
private:
struct Node {
ElementType element;
Node* next;
Node(ElementType ele, Node *n = NULL) {
element = ele;
next = n;
}
};
Node *top_node;
size_t node_num;
};
Test:
#include <iostream>
#include "Stack.h"
#include <string>
#include <sstream>
#include <exception>
using namespace std;
class STLForbidden : public exception {
virtual const char *what() const throw() {
return "Please do not use std::sort or std::list or std::vector .....";
}
};
class Job {
public:
explicit Job(int pri = 0) {
id = number++;
priority = pri;
}
string toString() {
stringstream ss;
ss << "[" << id << ":" << priority << "]";
return ss.str();
}
private:
static int number;
int id;
int priority;
};
int Job::number = 0;
template<typename T>
void print(Stack<T> stack) {
while (!stack.empty()) {
cout << stack.top() << " ";
stack.pop();
}
cout << endl;
}
int main() {
// ignore it
#if defined(_GLIBCXX_ALGORITHM) || defined(_GLIBCXX_LIST) || \
defined(_GLIBCXX_VECTOR) || defined(_GLIBCXX_DEQUE) || \
defined(_GLIBCXX_STACK)
// throw AlgorithmnForbidden();
throw STLForbidden();
#endif
// testing -> integer..
Stack<int> stk;
int m, n;
cin >> m >> n;
for (int i = 0; i < m; i++) stk.push(i + 0.01);
for (int i = 0; i < n; i++) stk.pop();
Stack<int> stk0(stk);
if (!stk.empty()) cout << stk.top() << endl;
cout << "The size is: " << stk.size() << endl;
if (stk.empty()) cout << "The stack is empty!" << endl;
else cout << "The stack is NOT empty!" << endl;
// testing -> Stack(const &stack);
if (!stk0.empty()) cout << "The top of Stack is: " << stk0.top() << endl;
cout << "The size is: " << stk0.size() << endl;
print(stk0);
if (!stk0.empty()) cout << "The top of Stack is: " << stk0.top() << endl;
cout << "The size is: " << stk0.size() << endl;
// testing -> reverse()
stk0.reverse();
cout << "Result of reversing is: ";
print(stk0);
// testing -> double..
Stack<double> stk1;
cin >> m >> n;
for (int i = 0; i < m; i++) stk1.push(i + 0.01);
for (int i = 0; i < n; i++) stk1.pop();
if (!stk1.empty()) cout << stk1.top() << endl;
cout << "The size is: " << stk1.size() << endl;
stk1.clear();
cout << "The size is: " << stk1.size() << endl;
if (stk1.empty()) cout << "The stack is empty!" << endl;
else cout << "The stack is NOT empty!" << endl;
// testing -> user defined class..
cin >> m >> n;
Stack<Job> stk2;
for (int i = 0; i < m; i++) stk2.push(Job(i));
for (int i = 0; i < n; i++) stk2.pop();
if (!stk2.empty()) cout << stk2.top().toString() << endl;
cout << "The size is: " << stk2.size() << endl;
if (stk2.empty()) cout << "The stack is empty!" << endl;
else cout << "The stack is NOT empty!" << endl;
// testing -> swap function..
Stack<int> stk3, stk4;
for (int i = 0; i < m; i++) stk3.push(i);
for (int i = 0; i < m; i++) stk4.push(m - i);
cout << "Before swap...." << endl;
print(stk3);
print(stk4);
stk3.swap(stk4);
cout << "After swap...." << endl;
print(stk3);
print(stk4);
}