03第三章、栈和队列

第三章、栈和队列

3.1.2 栈

算法库：

typedef struct
{
	ElemType data[MaxSize];  //存放在栈中的数据元素
	int top;				 //栈顶指针
}SqStack;

/*初始化*/
void InitStack(SqStack*& s) {
	s = (SqStack*)malloc(sizeof(SqStack));  //分配空间
	s->top = -1;
}
/*销毁*/
void DestroyStack(SqStack*& s) {
	free(s);
}
/*获取长度*/
int StackLength(SqStack* s) {
	return(s->top + 1);
}
/*判空*/
int StackEmpty(SqStack* s) {
	return (s->top == -1);
}
/*进栈*/
int Push(SqStack*& s, ElemType e) {
	if (s->top == MaxSize - 1)return 0;
	s->top++;
	s->data[s->top] = e;
	return 1;
}
/*出栈*/
int Pop(SqStack*& s, ElemType& e) {
	if (s->top == -1)return 0;
	e = s->data[s->top];
	s->top--;
	return 1;
}
/*取栈顶元素*/
int GetTop(SqStack*& s, ElemType& e) {
	if (s->top == -1)return 0;
	e = s->data[s->top];
	return 1;
}
/*展示*/
void DispStack(SqStack* s) {
	int i;
	for (i = s->top; i >= 0; i--) {
		printf("%c ", s->data[i]);
	}
	printf("\n");
}

例题 3.4 对称串

[例3.4]设计一个算法利用顺序栈判断一个字符串是否为对称串。所谓对称串指从左向右读和从右向左读的序列相同。
解：n个元素连续进栈，产生的连续出栈序列和输人序列正好相反，本算法就是利用这个特点设计的。对于字符串str，从头到尾将其所有元素连
续进栈，如果所有元素连续出栈产生的序列和从头到尾的字符依次相同，表示str是一个对称串，返回真；否则表示str不是对称串，返回假。
算法如下:

/*字符串是否对称*/
bool symmetry(ElemType str[]) {
	ElemType e;
	SqStack* st;
	InitStack(st);
	for (int i = 0; str[i]!='\0';i++) {
		Push(st,str[i]);
	}
	for (int i = 0; str[i] != '\0';i++) {
		Pop(st,e);//出栈，相当于逆序
		if (str[i] != e); {//顺序!=逆序
			DestroyStack(st);
			return false;
		}
	}
	DestroyStack(st);
	return true;
}

3.1.3 链栈

算法库：

typedef int ElemType;
constexpr auto MaxSize = 100;

typedef struct linknode {
	ElemType data;
	struct linknode* next;
}LinkStNode;

/*初始化*/
void InitStack(LinkStNode*& s) {
	s = (LinkStNode*)malloc(sizeof(LinkStNode));
	s->next = NULL;
}

void DestroyStack(LinkStNode*& s) {
	LinkStNode* p = s->next,*pre=s; //pre指向头节点，p指向首节点
	while (p != NULL) {
		free(pre);		//释放pre节点
		pre = p;		//pre、p同步后移
		p = pre->next;
	}
	free(pre);	//此时pre指向位置在，是放其空间
}

int StackLength(LinkStNode* s) {
	int i = 0;
	LinkStNode* p;
	p = s->next;
	while (p != NULL) {
		i++;
		p = p->next;
	}
	return i;
}

int StackEmpty(LinkStNode* s) {
	return s->next == NULL;
}

void Push(LinkStNode*& s, ElemType e) {
	LinkStNode* p;
	p = (LinkStNode*)malloc(sizeof(LinkStNode));
	p->data = e;
	p->next = s->next;		//插入p，作为首节点
	s->next = p;
}

int Pop(LinkStNode*& s, ElemType& e) {
	LinkStNode* p;
	if (s->next == NULL)return 0;
	p = s->next;
	e = p->data;
	s->next = p->next;
	free(p);
	return 1;
}

int GetTop(LinkStNode*& s, ElemType& e) {
	if (s->next == NULL)return 0;
	e = s->next->data;
	return 1;
}

void DispStack(LinkStNode* s) {
	LinkStNode* p = s->next;
	while (p != NULL) {
		printf("%c ", p->data);
		p = p->next;
	}
	printf("\n");
}

例题 3.5 括号匹配

[例3.5]设计一个算法判断输人的表达式中括号是否配对（假设只含有左、右圆括号）。
解：该算法在表达式括号配对时返回真，否则返回假。设置一个链栈st，扫描表达式exp，遇到左括号时进栈；遇到右括号时，若栈顶为左括号，则出栈，否则返回假。当表达式扫描完毕而且栈为空时返回真；否则返回假。
算法如下：

bool Match(char exp[],int n) {
	int i = 0; char e;
	bool match = true;
	LinkStNode* st;
	InitStack(st);
	while(i<n && match) {
		if (exp[i] == '(')Push(st, exp[i]);//左括号，入栈
		else if (exp[i] == ')')//右括号
		{
			if (GetTop(st, e) == true) {//得到栈顶元素
				if (e != '(')match = false;//如果栈顶不成匹配，false
				else Pop(st, e);//匹配成功就出栈
			}
			else match = false;
		}
		i++;
	}
	if (!StackEmpty(st))match = false;//如果还有（，表示括号不成对，失败！
	DestroyStack(st);
	return match;
}

3.2 队列

1、顺序队-算法库

typedef int ElemType;
constexpr auto MaxSize = 100;

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

void InitQueue(SqQueue *&q) {
	q = (SqQueue*)malloc(sizeof(SqQueue));
	q->front = q->rear = -1;
}

void DestroyQueue(SqQueue *&q) {
	free(q);
}

bool QueueEmpty(SqQueue *&q) {
	return q->front == q->rear;
}
/*入栈*/
bool enQueue(SqQueue *&q,ElemType e) {
	if (q->rear == MaxSize - 1)
		return false;
	q->rear++;
	q->data[q->rear] = e;
	return true;
}

/*出栈*/
bool deQueue(SqQueue*& q, ElemType e) {
	if (q->front == q->rear)return false;
	q->front++;
	e = q->data[q->front];
	return true;
}

2、环形队-算法库

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

void InitQueue(SqQueue *&q) {
	q = (SqQueue*)malloc(sizeof(SqQueue));
	q->front = q->rear = 0;
}

void DestroyQueue(SqQueue *&q) {
	free(q);
}

bool QueueEmpty(SqQueue *&q) {
	return q->front == q->rear;
}
/*入栈*/
bool enQueue(SqQueue *&q,ElemType e) {
	if ((q->rear+1)%MaxSize == q->front)
		return false;
	q->rear=(q->rear+1)%MaxSize;
	q->data[q->rear] = e;
	return true;
}

/*出栈*/
bool deQueue(SqQueue*& q, ElemType e) {
	if (q->front == q->rear)return false;
	q->front=(q->front+1)%MaxSize;
	e = q->data[q->front];
	return true;
}