// 顺序栈
// Stack.h
#ifndef STACK_H_H_H
#define STACK_H_H_H
template<class T> class Stack
{
public:
Stack();
void push(T d);// 压栈
void pop(); // 出栈
bool is_empty() const
{ return -1 == top; }
bool is_full() const
{ return max_size == (top+1);}
void make_empty()
{ top = -1;}
T get_top(); // 得到栈顶元素
private:
T * con; // 栈容器
const static int max_size;
int top; // 栈顶数组索引
};
#endif
// Stack.cpp
#include "Stack.h"
#include <cassert>
template<class T> const int Stack<T>::max_size = 100;
template<class T> Stack<T>::Stack() : top(-1)
{
con = new T[max_size];
assert( con != 0);
}
template<class T> void Stack<T>::push(T d)
{
if( !is_full() )
{
con[++top] = d;
}
}
template<class T> void Stack<T>::pop()
{
if( !is_empty() )
top--;
}
template<class T> T Stack<T>::get_top()
{
if( !is_empty() )
return con[top];
else
{
return 0;
}
}
// main.cpp
#include <iostream>
#include "Stack.h"
#include "Stack.cpp"
using namespace std;
void main()
{
Stack<int> stack;
for(int i=0; i<20; i++)
{
stack.push(i);
}
cout << stack.get_top() << endl;
stack.pop();
stack.pop();
cout << stack.get_top() << endl;
stack.push(1001);
cout << stack.get_top() << endl;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
链式栈
// ListStack.h
#ifndef LISTSTACK_H_H_H
#define LISTSTACK_H_H_H
template<class T> class LStack;
template<class T> class LSNode
{
friend class LStack<T>;
private:
LSNode(T d, LSNode * oldtop)
: data(d), link(oldtop)
{}
T data;
LSNode * link;
};
template<class T> class LStack
{
public:
LStack() : top(0)
{}
~LStack();
void push(T d);
void pop();
bool is_empty()
{ return 0 == top; }
T get_data();
private:
LSNode<T> * top;
};
#endif
/////
// ListStack.cpp
#include "ListStack.h"
#include <cassert>
template<class T> void LStack<T>::push(T d)
{
top = new LSNode<T>(d, top);
}
template<class T> void LStack<T>::pop()
{
if(! is_empty() )
{
LSNode<T> * temp = top->link;
delete top;
top = temp;
}
}
template<class T> T LStack<T>::get_data()
{
assert( !is_empty() );
return top->data;
}
template<class T> LStack<T>::~LStack()
{
if( !is_empty() )
{
LSNode<T> * temp;
while( top != 0)
{
temp = top->link;
delete top;
top = temp;
}
}
}
//////////// main.cpp
#include <iostream>
#include <string>
#include "ListStack.h"
#include "ListStack.cpp"
using namespace std;
int main()
{
LStack<string> s_stack;
s_stack.push("ABC");
s_stack.push("DEF");
cout << s_stack.get_data() << endl;
s_stack.pop();
cout << s_stack.get_data() << endl;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
链表队列
#include <assert.h>
#define null 0
#include <iostream.h>
template <class Type> class Queue;
template <class Type> class QueueNode{
friend class Queue<Type>;
private:
Type data;
QueueNode<Type> * link;
QueueNode(Type d=0,QueueNode *l=null):data(d),link(l){}
}
template <class Type> class Queue{
public:
Queue():rear(null),front(null){}
~Queue();
void EnQueue(const Type & item);
Type DeQueue();
Type GetFront();
void MakeEmpty(){front=rear=null;}
int IsEmpty() const {return front==null;}
private:
QueueNode<Type> *front,*rear;
};
template <class Type> void Queue<Type>::~Queue(){
QueueNode<Type> * p=front;
while(front!=null){
p=front;
front=front->link;
delete p;
}
}
template <class Type> void Queue<Type>::EnQueue(const Type & item){
if(front==null) front=rear=new QueueNode<Type>(item,null);
else rear=rear->link=new QueueNode<Type>(item,null);
}
template <class Type> Type Queue<Type>::DeQueue(){
assert(!IsEmpty());
QueueNode<Type> * p=front;
Type retvalue=p->data;
front=front->link;
delete p;
return retvalue;
}
template <class Type> Type Queue<Type>::GetFront(){
assert(!IsEmpty());
return front->data;
}
void main(){
Queue<int> que;
for(int i=0;i<10;i++)que.EnQueue(i);
cout<<que.GetFront()<<endl;
while(!que.IsEmpty())cout<<que.DeQueue()<<endl;
for(i=0;i<10;i++)que.EnQueue(i);
que.MakeEmpty();
if(que.IsEmpty())cout<<"the que is empty.."<<endl;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
模板数组循环队列
// Queue.h
#ifndef SUN_QUEUE_H
#define SUN_QUEUE_H
namespace sun
{
template<class T> class Queue
{
public:
Queue();
~Queue()
{ delete [] con; }
void entry_queue(const T d); // 入队
T de_queue(); // 出队
T get_front() const;
bool is_empty() const
{ return front == rear; }
bool is_full() const
{ return (rear+1)%max_size == front;}
int get_length() const
{ return (rear - front + max_size)%max_size; }
private:
const static int max_size;
int front, rear;
T * con; // 队列容器
};
}
#endif
// Queue.cpp
#include "Queue.h"
#include <cassert>
namespace sun
{
template<class T> const int Queue<T>::max_size = 100;
template<class T> Queue<T>::Queue() : front(0),rear(0)
{
con = new T[max_size];
assert( con != NULL );
}
template<class T> void Queue<T>::entry_queue(T d)
{
assert( !is_full() );
//rear = (rear +1)%max_size;
con[rear] = d;
rear = (rear +1)%max_size;
}
template<class T> T Queue<T>::de_queue()
{
assert(! is_empty());
int temp = front;
front = ( front+1)%max_size;
return con[temp];
}
template<class T> T Queue<T>::get_front() const
{
assert( !is_empty() );
return con[front];
}
}
///////////
// main.cpp
// vc 2005 express
#include <iostream>
#include "Queue.h"
#include "Queue.cpp"
int main()
{
sun::Queue<char> q7;
for(int i=0; i<26;i++)
q7.entry_queue(char(65+i));
std::cout << q7.get_front() << std::endl;
q7.de_queue();
q7.de_queue();
std::cout << q7.get_front() << std::endl;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////