[cpp]
#ifndef stack_
#define stack_
#include "stdafx.h"
//#include <iostream>
//using namespace std;
//exception
class OutOfBounds{
public:
OutOfBounds(){}
};
//change array's size
template<class T>
void Changesize1D(T * &arr,const int& size,const int& ToSize){
T* tmp = new T[size];
tmp = arr;
arr = new T[ToSize];
for(int i=0; i< size; ++i){
arr[i] = tmp[i];
}
delete[] tmp;
}
template <class T>
class Stack{
//friend ostream& operator<<(ostream&, const Stack<T>&);
public:
Stack();
~Stack(){delete []stack;};
T Top() const;
void Pop();
void Push(const T& x);
int Size() const;
bool Empty();
private:
int top;
int Maxtop;
T* stack;
};
template <class T>
Stack<T>::Stack() {
stack = new T[1];
top = -1;
Maxtop = 0;
}
template <class T>
T Stack<T>::Top() const{
if(top == -1){
throw OutOfBounds();
}else{
return stack[top];
}
}
template <class T>
void Stack<T>::Pop(){
--top;
//change array capacity when the list size drops to
//one-fourth of the array capacity
if((top + 1 <= (Maxtop + 1)/4) && Maxtop >0){
Maxtop = (Maxtop - 1)/2;
Changesize1D(stack,top + 1, Maxtop + 1);
}
}
template <class T>
void Stack<T>::Push(const T& x){
//if there is not enough space to accommodate the new element,
//double the array capacity
if(top == Maxtop){
Maxtop = Maxtop * 2 + 1;
Changesize1D(stack,top + 1,Maxtop + 1);
}
stack[++top] = x;
}
template <class T>
int Stack<T>::Size() const{
return top + 1;
};
template <class T>
bool Stack<T>::Empty(){
return top == -1;
}
/*
template <class T>
ostream& operator<<(ostream& out, const Stack<T>& s){
out << "The stack has " << s.Size() << " element(s)" << endl;
return out;
}*/
#endif
Test it
[cpp]
// Stack.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "Stack1.h"
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
Stack<int> t;
try
{
t.Top();
}
catch (OutOfBounds e)
{
cout << "no element" << endl;
}
t.Push(1);
cout << "after push 1, the top:" << t.Top() << endl;
cout << "after push 1, is empty?:" <<t.Empty() << endl;
t.Pop();
cout << "after pop, is empty? " <<t.Empty() << endl;
for(int i=0; i<10; ++i){
t.Push(i);
}
while(!t.Empty()){
cout << t.Top() << endl;
t.Pop();
}
return 0;
}
