栈
#include<iostream.h>
#include<malloc.h>
#include<conio.h>
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status ;
typedef int ElemType;
struct STACK
{
ElemType *base;
ElemType *top;
int stacksize;
};
typedef struct STACK SqStack;
//typedef struct STACK *pSqstack;
//函数声明
Status InitStack(SqStack &S);
void DestroyStack(SqStack &S);
void ClearStack(SqStack &S);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S,ElemType &e);
Status Push(SqStack &S,ElemType e);
Status Pop(SqStack &S,ElemType &e);
//初始化
Status InitStack(SqStack &S)
{
S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
//销毁栈
void DestroyStack(SqStack &S)
{
free(S.base);
}
//清空栈
void ClearStack(SqStack &S)
{
S.top=S.base;
}
//判栈空
Status StackEmpty(SqStack S)
{
if(S.top==S.base) return TRUE;
else
return FALSE;
}
//求栈中元素个数
int StackLength(SqStack S)
{
int i;
ElemType *p;
i=0;
p=S.top;
while(p!=S.base)
{p--;
i++;
}
return i;
}
//获取栈顶元素值
Status GetTop(SqStack S,ElemType &e)
{
if(S.top==S.base) return ERROR;
e=*(S.top-1);
return OK;
}
//入栈
Status Push(SqStack &S,ElemType e)
{
if(S.top - S.base>=S.stacksize)
{
S.base=(ElemType *) realloc(S.base,
(S.stacksize + STACKINCREMENT) * sizeof(ElemType));
if(!S.base) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize += STACKINCREMENT;
}
*(S.top++)=e;
return OK;
}
//出栈
Status Pop(SqStack &S,ElemType &e)
{
if(S.top==S.base) return ERROR;
e=*--S.top;
return OK;
}
//逆序打印栈中元素
void PrintElem(SqStack S)
{
ElemType e;
if(S.top==S.base) cout<<"该栈为空栈.";
else
while(S.top!=S.base)
{
Pop(S,e);cout<<e<<ends;
}
cout<<endl;
}
//进制转换函数
void conversion()
{
SqStack S;
ElemType e;
char b[17]="0123456789ABCDEF";
int n,r;
InitStack(S);
cout<<"Input a number to convert to :\n";
cin>>n;
cout<<"请输入要转换的进制:";
cin>>r;
if(n<0)
{
cout<<"\nThe number must be over 0.";
return;
}
if(!n) Push(S,0);
while(n){
Push(S,n%r);
n=n/r;
}
cout<<"the result is: ";
while(!StackEmpty(S)){
Pop(S,e);
cout<<b[e];
}
cout<<endl;
}
void main()
{
ElemType e;
SqStack Sa;
cout<<"\n\n-------------------SqStack Demo is running...----------------\n\n";
cout<<"First is Push function.\n";
InitStack(Sa);
cout<<" Now Stack is Empty.\n";
cout<<"请输入第一个要入栈的元素值:";
cin>>e;
Push(Sa,e);
cout<<"\n Now Stack has one element.\n";
PrintElem(Sa);
cout<<"请输入第二个要入栈的元素值:";
cin>>e;
Push(Sa,e);
cout<<"\n Now Stack has another element.\n";
PrintElem(Sa);
int n;
cout<<"请输入还要入栈的元素个数:";
cin>>n;
for(int i=1;i<=n;i++)
{
cout<<"\n请输入第"<<i+2<<"个元素:";
cin>>e;
Push(Sa,e);
}
cout<<"\n Now Pop Stack,the top elem put into variable e.\n";
Pop(Sa,e);
cout<<e<<endl;
cout<<" Let's see the left of Stack's elem:\n";
PrintElem(Sa);
cout<<"现在栈中元素个数为:"<<StackLength(Sa);
cout<<endl;
getch();
cout<<"进制转换演示:\n";
conversion();
}
------------------------------
-------------------------------
队列
#include <iostream.h>
#include <malloc.h>
typedef int QElemType;
typedef int Status;
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define MaxQsize 100 /*最大队列长度*/
typedef struct {
QElemType *base; /*初始化的动态分配存储空间*/
int front; /*头指针,若队列不空,指向队列头元素*/
int rear; /*尾指针,若队列不空,指向队列尾元素的下一个位置*/
}SqQueue;
Status InitQueue(SqQueue &Q){
/*构造一个空队列Q*/
Q.base=(QElemType *)malloc(MaxQsize*sizeof(QElemType));
if(!Q.base) return ERROR;/*存储分配失败*/
Q.front=Q.rear=0;
return OK;
}
Status QueueEmpty(SqQueue Q){
/*若队列Q为空队列,则返回TRUE,否则返回FALSE*/
if(Q.front==Q.rear) return TRUE;
else return FALSE;
}
int QueueLength(SqQueue Q){
/*返回Q的元素个数,即为队列的长度*/
return(Q.rear-Q.front+MaxQsize)% MaxQsize;
}
Status GetHead(SqQueue Q,QElemType &e){
/*若队列不为空,则用e返回Q的队头元素,并返回OK;否则返回ERROR*/
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front];
return OK;
}
Status EnQueue(SqQueue &Q,QElemType e){
/*插入元素e为Q的新的队尾元素*/
if((Q.rear+1)%MaxQsize==Q.front) return ERROR;/*队列满*/
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MaxQsize;
return OK;
}
Status DeQueue(SqQueue &Q,QElemType &e){
/*若队列不空,则删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR*/
if(Q.rear==Q.front) return ERROR;/*队列空*/
e=Q.base[Q.front];
Q.front=(Q.front+1)%MaxQsize;
return OK;
}
void main(){
SqQueue Q;
int select;
QElemType e;
if (InitQueue(Q)==ERROR)
cout<<"分配失败,即将退出程序!\n";
else/*否则显示队列操作的菜单,并选择相应的基本操作*/
do {
cout<<"1:判断队列是否为空\n";
cout<<"2:测试队列的长度\n" ;
cout<<"3:取队头元素值\n";
cout<<"4:向队列中插入一新元素\n";
cout<<"5:删除队列中一元素\n";
cout<<"0:结束\n";
cout<<"\n请输入您的选择:";
cin>>select;
cout<<endl;
switch (select) {
case 1:
if (QueueEmpty(Q)==TRUE) cout<<"队列为空\n";
else cout<<"队列不为空\n";break;
case 2:
cout<<"队列长度为:"<<QueueLength(Q)<<endl;break;
case 3:
if(GetHead(Q,e)==ERROR) cout<<"队列为空\n";
else cout<<"队首元素为:"<<e<<endl;break;
case 4:
cout<<"请输入要插入的元素值:";
cin>>e;
if(EnQueue(Q,e)==ERROR) cout<<"\n队列满\n";
else cout<<"\n元素成功插入\n";break;
case 5:
if(DeQueue(Q,e)==ERROR) cout<<"队列空,无数据可删\n";
else cout<<"删除元素为:"<<e;break;
case 0:
cout<<"操作结束\n";break;
default:
cout<<"输入选择出错!\n";
}/*switch*/
cout<<endl<<endl;
}while (select);
}/*main_end*/
参考资料:http://zhidao.baidu.com/question/41056708.html