“栈、队列”的应用

栈的定义和基本操作实现

2.1.1 写代码：定义顺序存储的栈（数组实现），数据元素是 int 型

typedef struct{
	int data[maxsize];
	int top;
}SqStack;

2.1.2 写代码：基于上述定义，实现“出栈、入栈、判空、判满”四个基本操作

//出栈
void Pop(SqStack &S, int &e){
	if(S.top==-1) return;
	e=S.data[S.top--];
}
//进栈
void Push(SqStack &S, int e){
	if(S.top==maxsize-1) return;
	S.data[++S.top]=e;
}
//判空
bool StackEmpty(SqStack S){
	if(S.top==-1) return true;
	else return false;
}
//判满
bool StackFull(SqStack S){
	if(S.top==maxsize-1) return true;
	else return false;
}

2.1.3 写代码：定义链式存储的栈（单链表实现）

typedef struct LinkNode{
	Elemtype data;
	struct LinkNode *next;
}LinkNode, *LiStack;

2.1.4 写代码：基于上述定义，栈顶在链头，实现“出栈、入栈、判空、判满”四个基本操作*(不知道对不对)*

//出栈
void Pop(LiStack &S, Elemtype &e){
	LinkNode *Lhead, *p;
	Lhead=(LinkNode *)malloc(sizeof(LinkNode));
	p=(LinkNode *)malloc(sizeof(LinkNode));
	Lhead=LiStack;
	e=Lhead->data;
	p=Lhead;
	free(p);
	Lhead=Lhead->next;
}
//进栈
void Push(LiStack &S, Elemtype e){
	LinkNode *Lhead, *p;
	Lhead=(LinkNode *)malloc(sizeof(LinkNode));
	p=(LinkNode *)malloc(sizeof(LinkNode));
	p->data=e;
	p->next=Lhead;
	Lhead=p;
}
//判空
bool LiStackEmpty(LiStack S){
	if(LiStack==null) return true;
	else return false;
}
//判满
bool LiStackFull(LiStack S){
	//?
}

2.1.5 写代码：定义链式存储的栈（双向链表实现）

typedef struct LinkNode{
    Elemtype data;
    struct LinkNode *prior, *next, *top;
}LinkNode, *DLiStack;

2.1.6 写代码：基于上述定义，栈顶在链尾，实现“出栈、入栈、判空、判满”四个基本操作*(不知道对不对)*

//出栈
void Pop(DLiStack &S, Elemtype &e){
	LinkNode *p,*pre;
	pre=S; //不带头节点
	p=S->next;
	e=pre->data;
	free(pre);
	pre=p;
	p=p->next;
}
//进栈
void Push(DLiStack &S, Elemtype e){
	LinkNode *p, *s;
	s=(LinkNode *)malloc(sizeof(LinkNode));
	s->data=e;
	p=S;
	while(p!=null){
		p=p->next;
	}
	p-next=s;
	s->prior=p;
}
//判空
bool DLiStackEmpty(DListack S){
	if(S==null) return true;
	else return false;
}
//判满
bool DLiStackFull(DListack S){
	//?
}

队列的定义和基本操作实现

2.2.1 写代码：定义顺序存储的队列（数组实现），要求数组空间可以被循环利用

typedef struct{
	Elemtype data[MaxSize];
	int front, rear;
}SqQueue;

2.2.2 写代码：基于上述定义，实现“出队、入队、判空、判满”四个基本操作

typedef struct{
	Elemtype data[MaxSize];
	int front, rear;
}SqQueue;
//出队
void DeQueue(SqQueue &Q, Elemtype &e){
	if(Q.front==Q.rear) return;
	e=Q.data[Q.rear--];
}
//入队
void EnQueue(SqQueue &Q, ELemtype e){
	if((Q.rear+1)%MaxSize==Q.front) return;
	Q.data[++Q.rear]=e;
}
//判满
bool SqQueueFull(SqQueue Q){
	if((Q.rear+1)%MaxSize==Q.front) return true;
	else return false;
}
//判空
bool SqQueueEmpty(SqQueue Q){
	if(Q.front==Q.rear) return true;
	else return false;
}

2.2.3 写代码：定义链式存储的队列（单链表实现）

typedef struct LinkNode{
	Elemtype data;
	struct LinkNode *next;
};
typedef struct{
	LinkNode *front, *rear;
}LinkQueue;

2.2.4 写代码：基于上述定义，实现“出队、入队、判空、判满”四个基本操作

//出队
void DeQueue(LinkQueue &Q, Elemtype &e){
	if(Q.front==Q.rear) return;
	LinkNode *p=Q.front->next; //带头节点 
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p) Q.rear=Q.front;
	free(p);
} 
//入队
void EnQueue(LinkQueue &Q, ELemtype e){
	LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
	s->data=e; s->next==null;
	Q.rear->next=s;
	Q.rear=s;
} 
//判空
bool LinkQueueEmpty(LinkQueue Q){
	if(Q.front->next==null) return true;
	else return false;
} 

注：有些书上没有的大部分是自己写的，打问号的是不知道咋写，如果有问题请及时反馈指正，谢谢~