栈和队列

栈和队列的定义和特点
栈 ———— 后进先出
队列 ———— 先进先出
栈和队列是两种常用的、重要的数据结构
栈和队列是限定插入和删除只能在表的“端点”进行的线性表

栈

栈定义和特点：
栈(stack)
是一个特殊的线性表，是限定仅在一端(通常是表尾进行插入和删除操作的线性表)
又称为后进先出(Last In First Out)的线性表，简称LIFO结构
存储结构：
用顺序栈or链栈存储均可，但以顺序栈更常见
栈的相关概念：
表尾(即an端)称为栈顶Top；表头(即a1端)称为栈底Base
插入元素到栈顶的操作，称为入栈
从栈顶删除最后一个元素的操作，称为出栈
“入” = 压入 = PUSH(x)
“出” = 弹出 = POP(y)

栈与一般线性表的区别：运算规则

栈的示意图：

栈的表示和操作的实现

基本操作：初始化、进栈、出栈、取栈顶元素
初始化、销毁栈、判断S是否为空栈、求栈的长度、取栈顶元素、栈置空、入栈、出栈

栈的顺序存储 ———— 顺序栈

top指针：为了操作方便，指示栈顶元素之上的下标地址
base指针：指示栈底元素在顺序栈中的位置
stacksize表示栈可使用的最大容量
空栈：base == top 是空栈的标志
栈满：top - base == stacksize

上溢：栈已经满了，又要压入元素
下溢：栈已经空了，还要弹出元素

顺序表的表示

//类型定义
#define MAXSIZE 100
typedef struct{
	SElemType *base; //栈底指针
	SElemType *top; //栈顶指针
	int stacksize; //栈可用最大容量
}SqStack;

顺序栈的初始化

//构造一个空栈
Status InitStack(SqStack &S){
	S.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType)); //分配存储空空间
	if(!S.base) exit (OVERFLOW); //存储分配失败
	S.top = S.base; //栈顶指针=栈底指针
	S.stacksize = MAXSIZE; 
	return OK;
}

顺序栈判断栈是否为空

Status 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 DestroyStack(SqStack &S){
	if(S.base){
		//delete是释放指针所指的空间，这个指针就变成了一个野指针，任意指向一个地址，并不是删除了这个指针
		//所以要早最后加上指针=NULL，避免其乱指
		delete S.base; 
		S.stacksize = 0;
		S.base = S.top = NULL;
	}
	return OK;
}

※顺序栈的入栈

Status Push(SqStack &S,SElemType e){
	if(S.top -S.base == S.stacksize){ //防止上溢
		return ERROR;
	}
	*S.top = e;
	S.top ++;
	//合并,先赋值后++:*Stop++ = e;
	return OK;
}

※顺序栈的出栈

Status Pop(SqStack &S,SElemType &e){
	if(S.top == S.base){ //防止下溢
		return ERROR;
	}
	-- S.top;
	e = *S.top;
	//e = * --S.top;
	return OK;
}

栈的链式存储 ———— 链栈

链栈的表示

typedef struct StackNode{
	SElemType data;
	struct StackNode *next;
}StackNode,*LinkStack;
LinkStack S;

链栈的初始化

void InitStack(LinkStack &S){
	构造一个空栈，栈顶指针置为空
	S = NULL;
	return OK;
}

判断链栈是否为空

Status StackEmpty(LinkStack S){
	if(S == NULL){
		return TRUE;
	}else{
		return FALSE;
	}
}

链栈的入栈

Status Push(LinkStack &S,SElemType e){
	p = new StackNode;//生成新结点p
	p -> data = e;
	p -> next = S;
	S = p; //修改栈顶指针
	return OK;
}

链栈的出栈

Status Pop(LinkStack &S,SElemType &e){
	if(S == NULL) return ERROR;
	e = S -> data;
	p = S;
	S = S -> next;
	delete p;
	return OK;
}

取栈顶元素

SElemType GetTop(LinkStack S){
	if(S != NULL){
		return S->data;
	}
}

栈与递归

递归的定义：
若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；
若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。
可递归求解的问题：
迷宫问题
Hanoi塔问题

递归问题 —— 用分治法求解
分治法：对于一个较为复杂的问题，能够分解成几个相对简单且解法相同或者类似的子问题来求解。

队列

队列的定义和特点：
队列
一种先进先出的线性表(Frist In First Out —— FIFO)
在表的一端插入(表尾)，在另一端删除(表头)
存储结构：
顺序队or链队存储均可，以循环顺序队列更常见

队列的示意图：

队列的表示和操作的实现

队列的顺序存储 ———— 顺序队(循环顺序队列)

顺序队的类型定义
用一维数组base[MAXQSIZE]动态分配存储空间

# define MAXQSIZE 100
Typedef struct{
	QElemType *base;
	int front;
	int rear;
}SqQueue;

解决假上溢的方法 —— 引入循环队列

base[0]接在base[MAXQSIZE - 1]之后，若rear + 1 == M,则令 rear = 0；
实现方法：利用模运算(mod,C语言中：%)

插入元素：
Q.base[Q.rear] = x; //将要插入的元素放在尾指针所指的位置
Q.rear = (Q.rear + 1) % MAXQSIZE;
删除元素：
x = Q.base[s.front]
Q.front = (Q.front + 1) % MAXQSIZE

解决判断队空还是队满的问题：

1. 另外设一个标志以区别队空、队满
2. 另设一个变量，记录元素个数
3. 少用一个元素空间
       队空：front = rear
       队满：**(rear + 1) % MAXQSIZE == front**

队列的初始化

Status InitQueue (SqQueue &Q){
	//分配数组空间
	Q.base = (QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
	if(!Q.base) exit(OVERFLOW);
	//头指针 尾指针置为0
	Q.front = Q.rear = 0;
	return OK;
}

求队列的长度
(Q.rear - Q.front + MAXQSIZE)%MAXQSIZE

int QueueLength(SqQueue Q){
	return (Q.rear - Q.front + MAXQSIZE)%MAXQSIZE;
}

循环队列入队

Status EnQueue(SqQueue &Q, QElemType e){
	if((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR;//队满
	Q.base[Q.rear] = e; //只能从队尾插入，放在尾指针指的地方
	Q.rear = (Q.rear + 1) % MAXQSIZE; //队尾指针 +1
}

循环队列出队

Status DeQueue(SqQueue &Q,QElemType &e){
	if(Q.front == Q.rear) return ERROR; //队空
	e = Q.base[Q.front]; //保存队头元素，只能从队头出队
	Q.front = (Q.front + 1) % MAXQSIZE; //对头指针 + 1
	return OK;
}

取队头元素

SElemType GetHead(SqQueue Q){
	if(Q.front != Q.rear){
		return Q.base[Q.front];
	}
}

队列的链式存储 ———— 链队

链队列的类型定义

#define MAXQSIZE 100 //最大队列长度
//结点类型
typedef struct Qnode{
	QElemType 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));
	if(!Q.front) exit (OVERFLOW);
	Q.front -> next = NULL;
	return OK;
}

销毁链队列

Status DestroyQueue(LinkQueue &Q){
	while(Q.front){
		p = Q.front -> next;
		free(Q.front);
		Q.front = p;
		/**
		Q.rear = Q.front -> next;
		free(Q.front);
		Q.front = Q.rear ;
		*/
	}
	return OK;
}

将元素e入队

Status EnQueue(LinkQueue &Q,QElemType e){
	p = (QueuePtr)malloc(sizeof(QNode));
	if(!p) exit(OVERFLOW);
	p -> data = e;
	p -> next = NULL;
	Q.rear -> next = p;
	Q.rear = p;
	return OK;
}

链队列出队

Status DeQueue(LinkQueue &Q,QElemType &e){
	if(Q.front == Q.rear) return ERROR;
	p = Q.front -> next;
	e = p -> data;
	Q.front -> = p -> next;
	if(Q,rear == p) Q.rear = Q.front; //刚好出队的是尾部
	delete p;
	return OK;
}

求链队列的队头元素

Status GetHead(LinkQueue Q,QElemType &e){
	if(Q.front == Q.rear) return ERROR;
	e = Q.front -> next -> data;
	return OK;
}

Donate