数据结构·栈、队列与数组

栈和队列的应用

栈在括号匹配中的应用

栈在表达式求值中的应用

• 操作数、运算符、界限符
• 中缀表达式、后缀表达式
• 计算过程

栈在递归中的应用

队列在层次遍历中的应用

队列在计算机系统中的应用

顺序存储的循环队列（c语言实现）

#define MaxSize 50
struct SqQueue {
	int data[MaxSize];
	int front,rear;
};

void InitQueue(struct SqQueue *Q) {
	Q->front=Q->rear=0;
}

int QueueEmpty(const struct SqQueue *Q) {
	if (Q->front==Q->rear)
		return 1;
	return 0;
}

int EnQueue(struct SqQueue *Q, int x) {
	if ((Q->rear+1)%MaxSize==Q->front)
		return 0;
	Q->data[Q->rear]=x;
	Q->rear=(Q->rear+1)%MaxSize;
	return 1;
}

int DeQueue(struct SqQueue *Q, int *x) {
	if (QueueEmpty(Q))
		return 0;
	*x=Q->data[Q->front];
	Q->front=(Q->front+1)%MaxSize;
	return 1;
}

int GetHead(const struct SqQueue *Q, int *x) {
	if (QueueEmpty(Q))
		return 0;
	*x=Q->data[Q->front];
	return 1;
}

链栈（c语言实现）

#include <stdlib.h>

#define MaxSize 100

struct LNode {
	int value;
	struct LNode *next;
};

struct LnStack {
	struct LNode *top;
	int height;
};

void InitStack(struct LnStack *S) {
	S->top = NULL;
	S->height = 0;
}

int StackEmpty(const struct LnStack *S) {
	if (S->height)
		return 0;
	else
		return 1;
}

int Push(struct LnStack *S, int x) {
	if (S->height==100)
		return 0;
	struct LNode *new_head = malloc(sizeof(struct LNode));
	new_head->value = x;
	new_head->next = S->top;
	S->top=new_head;
	S->height++;
	return 1;
}

int Pop(struct LnStack *S, int *x) {
	if (S->height==0)
		return 0;
	*x=S->top->value;
	struct LNode *old = S->top;
	S->top = S->top->next;
	free(old);
	S->height--;
	return 1;
}

int GetTop(const struct LnStack *S, int *x) {
	if (S->height==0)
		return 0;
	*x=S->top->value;
	return 1;
}

数组和特殊矩阵

数组的定义

• 数组元素
• 下标
• 维界：

数组的存储结构

特殊矩阵的压缩存储

• 对称矩阵