//模版式的三种stack，都使用了迭代器iterator！！！都是嵌套类iterator操纵其他类
//外围类都有begin()和end()函数获取iterator对象
//////////////////////////////////////////////////////////数组固定大小式的stack
#ifndef ITERSTACKTEMPLATE_H
#define ITERSTACKTEMPLATE_H
#include "../require.h"
#include <iostream>
////////////////////////////////////////////////////////嵌套类iterator操纵外围类
template<class T, int ssize = 100>
class StackTemplate {
T stack[ssize];///////////////整个对象放进stack【】//////////////////////存放点
int top;
public:
StackTemplate() : top(0) {}
void push(const T& i) {
require(top < ssize, "Too many push()es");
stack[top++] = i;
}
T pop() {
require(top > 0, "Too many pop()s");
return stack[--top];
}
class iterator; // Declaration required
friend class iterator; // Make it a friend
class iterator { // Now define it
StackTemplate& s;
int index;
public:
///////////这里少了默认构造函数，不安全！
iterator(StackTemplate& st): s(st),index(0){}
iterator(StackTemplate& st, bool): s(st), index(s.top) {}
T operator*() const { return s.stack[index];}
T operator++() { // Prefix form
require(index < s.top,
"iterator moved out of range");
return s.stack[++index];
}
T operator++(int) { // Postfix form
require(index < s.top,
"iterator moved out of range");
return s.stack[index++];
}
// Jump an iterator forward
iterator& operator+=(int amount) {
require(index + amount < s.top,
" StackTemplate::iterator::operator+=() "
"tried to move out of bounds");
index += amount;
return *this;
}
// To see if you're at the end:
bool operator==(const iterator& rv) const {
return index == rv.index;
}
bool operator!=(const iterator& rv) const {
return index != rv.index;
}
friend std::ostream& operator<<(
std::ostream& os, const iterator& it) {
return os << *it;
}
};
iterator begin() { return iterator(*this); }/////////////////这两句相当重要
// Create the "end sentinel":
iterator end() { return iterator(*this, true);}/////////////这两句相当重要
};
#endif // ITERSTACKTEMPLATE_H ///:~
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////链表式的stack
#ifndef TSTACK2_H
#define TSTACK2_H
//////////////////////////////////这里外围类操纵嵌套类Link，同时嵌套类iterator又操纵嵌套类Link。
template<class T> class Stack {
struct Link {
T* data;
Link* next;
Link(T* dat, Link* nxt)
: data(dat), next(nxt) {}
}* head;////////////////////////////////////////////////////////////////////存放点
public:
Stack() : head(0) {}
~Stack();
void push(T* dat) {
head = new Link(dat, head);///////////////这句很牛叉
}
T* peek() const {
return head ? head->data : 0;
}
T* pop();
class iterator; // Declaration required
friend class iterator; // Make it a friend
class iterator { // Now define it
Stack::Link* p;
public:
iterator(const Stack<T>& tl) : p(tl.head) {}
iterator(const iterator& tl) : p(tl.p) {}
iterator() : p(0) {}
bool operator++() {
if(p->next)
p = p->next;
else p = 0; // Indicates end of list
return bool(p);
}
bool operator++(int) { return operator++(); }
T* current() const {
if(!p) return 0;
return p->data;
}
// Pointer dereference operator:
T* operator->() const {
require(p != 0,
"PStack::iterator::operator->returns 0");
return current();
}
T* operator*() const { return current(); }
// bool conversion for conditional test:
operator bool() const { return bool(p); }
// Comparison to test for end:
bool operator==(const iterator&) const {
return p == 0;
}
bool operator!=(const iterator&) const {
return p != 0;
}
};
iterator begin() const { return iterator(*this); }
iterator end() const { return iterator(); }
};
template<class T> Stack<T>::~Stack() {
while(head)
delete pop();
}
template<class T> T* Stack<T>::pop() {
if(head == 0) return 0;
T* result = head->data;
Link* oldHead = head;
head = head->next;
delete oldHead;
return result;
}
#endif // TSTACK2_H ///:~
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////可变大小容器式的stack‘
#ifndef TPSTASH2_H
#define TPSTASH2_H
#include "../require.h"
#include <cstdlib>
////////////////////////////////////////////////////////////嵌套类iterator操纵外围类
template<class T, int incr = 20>
class PStash {
int quantity;
int next;
T** storage;//////////////////////////////////////////////存放点
void inflate(int increase = incr);
public:
PStash() : quantity(0), storage(0), next(0) {}
~PStash();
int add(T* element);
T* operator[](int index) const;
T* remove(int index);
int count() const { return next; }
// Nested iterator class:
class iterator; // Declaration required
friend class iterator; // Make it a friend
class iterator { // Now define it
PStash& ps;
int index;
public:
iterator(PStash& pStash)
: ps(pStash), index(0) {}
// To create the end sentinel:
iterator(PStash& pStash, bool)
: ps(pStash), index(ps.next) {}
// Copy-constructor:
iterator(const iterator& rv)
: ps(rv.ps), index(rv.index) {}
iterator& operator=(const iterator& rv) {
ps = rv.ps;
index = rv.index;
return *this;
}
iterator& operator++() {
require(++index <= ps.next,
"PStash::iterator::operator++ "
"moves index out of bounds");
return *this;
}
iterator& operator++(int) {
return operator++();
}
iterator& operator--() {
require(--index >= 0,
"PStash::iterator::operator-- "
"moves index out of bounds");
return *this;
}
iterator& operator--(int) {
return operator--();
}
// Jump interator forward or backward:
iterator& operator+=(int amount) {
require(index + amount < ps.next &&
index + amount >= 0,
"PStash::iterator::operator+= "
"attempt to index out of bounds");
index += amount;
return *this;
}
iterator& operator-=(int amount) {
require(index - amount < ps.next &&
index - amount >= 0,
"PStash::iterator::operator-= "
"attempt to index out of bounds");
index -= amount;
return *this;
}
// Create a new iterator that's moved forward
iterator operator+(int amount) const {
iterator ret(*this);
ret += amount; // op+= does bounds check
return ret;
}
T* current() const {
return ps.storage[index];
}
T* operator*() const { return current(); }
T* operator->() const {
require(ps.storage[index] != 0,
"PStash::iterator::operator->returns 0");
return current();
}
// Remove the current element:
T* remove(){
return ps.remove(index);
}
// Comparison tests for end:
bool operator==(const iterator& rv) const {
return index == rv.index;
}
bool operator!=(const iterator& rv) const {
return index != rv.index;
}
};
iterator begin() { return iterator(*this); }
iterator end() { return iterator(*this, true);}
};
// Destruction of contained objects:
template<class T, int incr>
PStash<T, incr>::~PStash() {
for(int i = 0; i < next; i++) {
delete storage[i]; // Null pointers OK
storage[i] = 0; // Just to be safe
}
delete []storage;
}
template<class T, int incr>
int PStash<T, incr>::add(T* element) {
if(next >= quantity)
inflate();
storage[next++] = element;
return(next - 1); // Index number
}
template<class T, int incr> inline
T* PStash<T, incr>::operator[](int index) const {
require(index >= 0,
"PStash::operator[] index negative");
if(index >= next)
return 0; // To indicate the end
require(storage[index] != 0,
"PStash::operator[] returned null pointer");
return storage[index];
}
template<class T, int incr>
T* PStash<T, incr>::remove(int index) {
// operator[] performs validity checks:
T* v = operator[](index);
// "Remove" the pointer:
storage[index] = 0;
return v;
}
template<class T, int incr>
void PStash<T, incr>::inflate(int increase) {
const int tsz = sizeof(T*);
T** st = new T*[quantity + increase];
memset(st, 0, (quantity + increase) * tsz);
memcpy(st, storage, quantity * tsz);
quantity += increase;
delete []storage; // Old storage
storage = st; // Point to new memory
}
#endif // TPSTASH2_H ///:~