第三章 栈与队列

栈与队列 栈 栈的顺序实现

#define MaxSize 10
typedef struct {
	ElemType data[MaxSize];
	int top;
} SqStack;

int InitStack(SqStack &S) {
	S.top = -1;
	return true;
}

int Push(SqStack &S, ElemType e) {
	if (S.top + 1 == MaxSize)
		return -1;
	S.data[++ top] = e;
	return 1;
}

int Pop(SqStack &S, ElemType &e) {
	if (S.top == -1)
		return -1;
	e = S.data[top --];
	return 1;
}

栈的链表实现

typedef struct {
	ElemType data;
	struct SNode *next;
} SNode, *LinkedStack;

int InitStack(LinkedStack S) {
	S = NULL; //推荐使用不带头节点的链表
}

int Push(LinkedStack S, ElemType e) {
	SNode *p = (SNode *) malloc(sizeof SNode);
	if (!p)
		return -1;
	p->data = e;
	p->next = S;
	S = p;
}
int Pop(LinkedStack &S, ElemType &e) {
	SNode *p = S;
	S = S->next;
	e = p->data;
	free(p);
}

队列 队列的顺序实现 定义top为当前要插入的位置

typedef struct {
	ElemType data[MaxSize];
	int top, rear;
} SqQueue;

int InitQueue(SqQueue &Q) {
	Q.top = Q.rear = 0;
}

int Empty(SqQueue &Q) {
	return Q.top == Q.rear;
}

int Full(SqQueue &Q) {
	//牺牲队头前面的那个位置
	return (Q.rear + 1) % MaxSize == Q.top;
}
int EnQueue(SqQueue &Q, ElemType e) {
	if (Full(Q))
		return -1;
	Q.data[Q.rear] = e;
	Q.rear = (Q.rear ++) % MaxSize;
	return 1;
}
int DeQueue(SqQueue &Q, ElemType &e) {
	if (Empty(Q))
		return -1;
	e = Q.data[Q.top];
	Q.top = (Q.top ++) % MaxSize;
	return 1;
}

定义size变量

typedef struct {
	ElemType data[MaxSize];
	int top, rear;
	int size;
} SqQueue;

int InitQueue(SqQueue &Q) {
	Q.top = Q.rear = Q.size = 0;
}

int Empty(SqQueue &Q) {
	return !Q.size;
}

int Full(SqQueue &Q) {
	return Q.size == MaxSize;
}

int EnQueue(SqQueue &Q, ElemType e) {
	if (Full(Q))
		return -1;
	Q.data[Q.rear] = e;
	Q.rear = (Q.rear ++) % MaxSize;
	Q.size ++;
	return 1;
}

int DeQueue(SqQueue &Q, ElemType &e) {
	if (Empty(Q))
		return -1;
	e = Q.data[Q.top];
	Q.top = (Q.top ++) % MaxSize;
	Q.size --;
	return 1;
}

定义tag变量

typedef struct {
	ElemType data[MaxSize];
	int top, rear;
	int tag;
} SqQueue;

int InitQueue(SqQueue &Q) {
	Q.top = Q.rear = Q.tag = 0;
}

int Empty(SqQueue &Q) {
	return Q.top == Q.rear && !Q.tag;
}

int Full(SqQueue &Q) {
	return Q.top == Q.rear && Q.tag;
}

int EnQueue(SqQueue &Q, ElemType e) {
	if (Full(Q))
		return -1;
	Q.data[Q.rear] = e;
	Q.rear = (Q.rear ++) % MaxSize;
	Q.tag = 1;
	return 1;
}

int DeQueue(SqQueue &Q, ElemType &e) {
	if (Empty(Q))
		return -1;
	e = Q.data[Q.top];
	Q.top = (Q.top ++) % MaxSize;
	Q.tag = 0;
	return 1;
}

定义top为当前栈顶

typedef struct {
	ElemType data[MaxSize];
	int top, rear;
} SqQueue;

int InitQueue(SqQueue &Q) {
	Q.top = 0, Q.rear = (-1 + MaxSize) % MaxSize;
}

int Empty(SqQueue &Q) {
	if (mode == 牺牲一个元素)
		return (Q.rear + 1) % MaxSize == Q.top;
	else if (mode == 定义size变量)
		return Q.size == 0;
	else 
		return (Q.rear + 1) % MaxSize == Q.top && !Q.tag;
}

int Full(SqQueue &Q) {
	if (mode == 牺牲一个元素)
		return (Q.rear + 2) % MaxSize == Q.top;
	else if (mode == 定义size变量)
		return Q.size == MaxSize;
	else 
		return (Q.rear + 1) % MaxSize == Q.top && Q.tag;
}

int EnQueue(SqQueue &Q, ElemType e) {
	if (Full(Q))
		return -1;
	Q.rear = (++ Q.rear) % MaxSize;
	Q.data[Q.rear] = e;
	if (mode == 定义size变量)
		Q.size ++;
	else if (mode == 定义tag变量)
		Q.tag = 1;
	return 1;
}

int DeQueue(SqQueue &Q, ElemType &e) {
	if (Empty(Q))
		return -1;
	e = Q.data[Q.top];
	Q.top = (Q.top ++) % MaxSize;
	if (mode == 定义size变量)
		size --;
	else if (mode == 定义tag变量)
		Q.tag = 0;
}

暑期编程PK赛 得CSDN机械键盘等精美礼品！