栈
#include <iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;
#define MAXSIZE 100
//顺序栈的表示(声明)
typedef struct
{
int *base; //栈底指针(SElemType *base)
int *top; //栈顶指针(SElemType *top)
int stacksize;
} SqStack;
//顺序栈初始化
Status InitStack(SqStack &S)
{
S.base = new int[MAXSIZE];
if(!S.base)
{
return OVERFLOW;
}
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
//判断顺序栈是否为空栈
bool StackEMpty(SqStack &S)
{
if(S.top == S.base)
{
return true;
}
else
{
return false;
}
}
//求顺序栈的长度
int StackLength(SqStack &S)
{
return S.top - S.base;
}
//清空顺序栈
Status ClearStack(SqStack &S)
{
if(S.base)
{
S.top = S.base;
}
return OK;
}
//销毁顺序栈
Status DestoryStack(SqStack &S)
{
if(S.base)
{
delete S.base;
S.stacksize = 0;
S.base = S.top = NULL;
}
return OK;
}
//顺序栈进栈
Status Push(SqStack &S,int e)
{
if(S.top - S.base == S.stacksize) //判断是否栈满
{
return ERROR;
}
*S.top++ = e;
//等同于
//*S.top = e;
//S.top ++;
return OK;
}
//顺序栈出栈
Status Pop(SqStack &S,int &e)
{
if(S.top == S.base) //判断是否为空栈
{
return ERROR;
}
e = *-- S.top;
//等同于
// --s.top;
// e = *S.top;
return OK;
}
//取顺序栈顶元素
Status getTop(SqStack &S,int &e)
{
if(S.base == S.top)
{
return ERROR;
}
e = *(S.top-1);
//与e = *(S.top--)不同
return OK;
}
//链栈的表示(声明)
typedef struct StackNode
{
int data; //数据域(ElemType data)
struct StackNode *next;
} StackNode, *LinkStack;
//链栈的初始化
void InitStack(LinkStack S) //可用&S,也可S (老师建议S)
{
S = NULL;
}
//判断链栈是否为空
Status StackEmpty(LinkStack S)
{
if(S == NULL)
{
return true;
}
else
{
return false;
}
}
//链栈进栈
Status Push(LinkStack &S,int e)
{
LinkStack p = new StackNode; //生成新结点p
if(!p)
{
exit(OVERFLOW);
}
p->data = e;
p->next = S;
S = p;
return OK;
}
//取链栈栈顶元素
int GetTop(LinkStack S)
{
if(S == NULL)
{
exit(1);
}
else
{
return S->data;
}
}
int main()
{
LinkStack S;
return 0;
}
队列
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;
#define MAXSIZE 100 //最大队列长度
//循环队列的表示(声明)
typedef struct
{
int *base; //储存空间的基地址(QElemType *base)
int front; //头指针
int rear; //尾指针
}SqQueue;
//循环队列的初始化
Status initQueue(SqQueue &Q)
{
Q.base = new int[MAXSIZE];
if(!Q.base)
{
exit(OVERFLOW);
}
Q.front = Q.rear = 0;
return OK;
}
//求循环队列长度
int QueueLength(SqQueue Q)
{
return(Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}
//循环队列入队
Status EnQueue(SqQueue &Q,int e)
{
if((Q.rear + 1) % MAXSIZE == Q.front)
{
return ERROR;
}
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXSIZE;
return OK;
}
//循环队列出队
Status DeQueue(SqQueue &Q,int &e)
{
if(Q.front == Q.rear)
{
return ERROR;
}
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXSIZE;
}
//链队列的表示
typedef struct QNode
{
int data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
//链队列的初始化
Status InitQueue(LinkQueue &Q)
{
//Q.front = Q.rear (QueuePtr)malloc (sizeof(QNode));
Q.front = Q.rear = new QNode;
if(!Q.front)
{
exit(OVERFLOW);
}
Q.front-> next = NULL;
}
//销毁链队列
Status DestroyQueue(LinkQueue &Q)
{
while(Q.front)
{
Q.rear = Q.front->next;
delete Q.front;
Q.front = Q.rear;
}
return OK;
}
//判断链队列是否为空
Status QueueEmpty(LinkQueue Q)
{
return(Q.front == Q.rear);
}
int main()
{
}
1.设一个标志位用于区分队空与队满
2.//队空:front == rear
//队满:(rear+1)%M == front