大话数据结构 栈和队列

《大话数据结构》 阅读整理

栈和队列

栈的定义

定义

栈是限定仅在表尾进行插入和删除操作的线性表

性质

允许插入和删除的一端称为栈顶 另一端称为栈底

不含任何数据元素的栈称为空栈

后进先出 LIFO结构

栈的插入操作叫做进栈 压栈 入栈

栈的删除操作叫做 出栈 弹栈

栈的顺序存储结构

顺序栈的定义

定义一个top变量用来存放栈顶元素的位置

typedef struct {
	//存放的数据
	SElemType data[MAXSIZE];
	//栈顶指针
	int top;
}SqStack;

顺序栈的入栈

从栈顶添加元素 头指针上移

//压栈
Status Push(SqStack *s, SElemType e) {

	//栈满 因为栈顶指针等于了最大空间
	if (s->top == MAXSIZE - 1) {
		//返回错误状态码
		return ERROR;
	}

	//栈顶指针后移
	s->top++;

	//将元素插入到栈顶
	s->data[s->top] = e;
	//返回正确状态码
	return OK;

}

顺序栈的出栈

从栈顶元素移除元素 头指针下移

//出栈
Status Pop(SqStack* s, SElemType e) {

	//栈空
	if (s->top == -1) {
		//返回错误状态码
		return ERROR;
	}

	//将删除的元素赋值给e
	e = s->data[s->top];

	//栈顶指针下移
	s->top--;

	//返回正确状态码
	return OK;

}

两栈共享空间

出发点

让一个栈的栈底为数组的始端 下标为0出 另一个栈为数组的末端 下标的数组长度为n-1 增加元素 两端向中间延伸

• 栈满

栈二为空 栈一 top1 == n-1 栈一满

栈一为空 栈二 top2 == 0 栈二满

两栈见面 top1 + 1 = top2

共享栈的定义

//空间栈结构
typedef struct {
	//栈数据
	SElemType data[MAXSIZE];
	//栈一的栈顶指针
	int top1;
	//栈二的栈顶指针
	int top2;
}SqDoubleStack;

共享栈的入栈

//s链表 e操作元素 stackNumber 哪个栈 压栈
Status Push(SqDoubleStack* s, SElemType e, int stackNumber) {

	//栈满
	if (s->top1 + 1 == s->top2) {
		//返回错误状态码
		return ERROR;
	}

	//第一个栈插入
	if (stackNumber == 1) {

		//先将栈顶指针上移后存入数据元素
		s->data[++s->top1] = e;
	}
	//第二个栈插入
	else if (stackNumber == 2) {
		//先将栈顶指针下移后存入数据元素
		s->data[--s->top2] = e;
	}

	//返回正确状态码
	return OK;
}

共享栈的出栈

//出栈
Status Pop(SqDoubleStack* s, SElemType e, int stackNumber) {

	//第一个栈
	if (stackNumber == 1) {
		//栈空
		if (s->top1 == -1) {
			return ERROR;
		}

		//现将栈顶元素赋值给e后下移
		e = s->data[s->top1--];
	}
	//第二个栈
	else if (stackNumber == 2) {
		//栈空
		if (s->top2 == MAXSIZE) {
			return ERROR;
		}
		//现将栈顶元素赋值给e后下移
		e = s->data[s->top2++];
	}

	return OK;
}

栈的链式存储结构

定义

栈顶放在单链表的头部

通常情况下不存在栈满情况 除非内存已经没有可使用的空间了

top == null 说明空栈

//定义一个单链表结构体
typedef struct StackNode{

	//链表数据域
	SElemType data;
	//链表指针域
	struct StackNode* next;

}StackNode,*LinkStackPtr;


//定义一个栈顶指针指向单链表头结点
typedef struct {

	//栈顶指针
	LinkStackPtr top;

	//栈元素数
	int count;

}LinkStack;

链栈的入栈

开辟一块内存空间给一个新结点 将数据赋值给新节点以及头指针指向新结点

//压栈 进栈
Status Push(LinkStack* S, SElemType e) {

	//开辟一块内存空间赋值给s结点
	LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));

	//将插入的数据存入s的数据域
	s->data = e;

	//s的指针域指向栈的栈顶指针
	s->next = S->top;

	//将栈顶指针移动将s结点设置为栈顶指针
	S->top = s;
	//栈内元素++
	S->count++;

	//返回正确状态码
	return OK;

}

链栈的出栈

将头指针指向下一结点

//弹栈 出栈
Status Pop(LinkStack* S, SElemType* e) {

	//定义结点p
	LinkStackPtr p;

	//判断栈是否为空
	if (StackEmpty(*S)) {
		return ERROR;
	}

	//将栈顶元素赋值给e
	*e = S->top->data;

	//将栈顶指针指向的结点存放到p结点中
	p = S->top;

	//将栈顶指针 指向栈顶指针的下一个结点
	S->top = S->top->next;

	//释放之前栈顶指针向的结点
	free(p);

	//栈内元素 - 1
	S->count--;

	//返回正确状态码
	return OK;
}

注意

如果栈的使用过程中元素变化不可预料最好使用链栈 反之顺序栈

递归

递归定义

把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数

每个递归定义必须至少有一个条件 满足时递归不再进行 不再引用自身而是返回值退出

经典的菲波那切数列

# include <stdio.h>

int fbi(int i) {

	if (i < 2) {
		return i == 0 ? 0 : 1;
	}

	return fbi(i - 1) + fbi(i - 2);

}

int main() {

	int i;

	printf("递归现实菲波那切数列\n");

	for (i = 0; i < 40; i++) {
		printf("%d", fbi(i));
	}


	return 0;
}

栈的应用（四则运算表达式求值）

后缀（逆波兰）表示法

原式(中缀表达式)：9+(3 - 1) * 3 + 10 / 2

后缀表达式：9 3 1 - 3 * + 10 2 / +

所有的符号都在要运算数字的后面

后缀表达式计算结果

从左到右遍历表达式的每个数字和符号 遇到是数字就进栈 遇到符号就将处于站定两个数字出栈 进行计算 运算结果进栈 一直到最终获得结果

中缀表达式转后缀表达式

从左到右遍历中缀表达式的每个数字和符号 若是数字就输出 即成为后缀表达式的一部分 若是符号 则判断其与栈顶符号的优先级 是右括号或优先级不高于栈顶符号(乘除优先加减) 则栈顶元素依次出栈并输出 并将当前符号进栈 一直到最终输出后缀表达式为止

队列的定义

只允许在一端进行插入操作 而在另一端进行删除操作的线性表

性质

先进先出的线性表 FIFO

允许插入的一端称为队尾 允许删除的一端称为队头

循环队列

队列顺序存储的不足

就是当出队是后面的都要动 时间复杂度为O(n)

当前面有空位置时后面却已经满了 无法入队
这种现象称作 假溢出

循环队列的定义

头尾相接的顺序存储结构称为循环队列

循环队列的判断条件

设置一个标志量flag 当front == rear 且flag = 0时为空队列
当front == rear 且 flag = 1时为队列满

当队列为空 条件是front == rear 队列满时 保留一个元素空间
队列满的条件是 (rear + 1) % QueueSize == front

• 队列长度通用公式

(rear - front + QueueSize) % QueueSize

循环队列顺序结构定义

typedef struct {
	QElemType data[MAXSIZE];//队列数据
	int front;//头指针
	int rear;//尾指针
}SqQueue;

循环队列初始化

//队列初始化
Status InitQueue(SqQueue* Q) {

	//头指针指向0位置
	Q->front = 0;

	//尾指针指向0位置
	Q->rear = 0;

	return OK;
}

循环队列长度

//返回队列的长度
int QueueLength(SqQueue *Q) {
	
	//队列长度算法
	return (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
}

循环队列入队

//入队
Status EnQueue(SqQueue *Q,QElemType e){

	//队列满
	if ((Q->rear + 1) % MAXSIZE == Q->front) {
		return ERROR;
	}

	//入队数据赋值
	Q->data[Q->rear] = e;

	//尾指针后移一位
	Q->rear = (Q->rear + 1) % MAXSIZE;

	//返回正确代码
	return OK;
}

循环队列出队

//出队
Status DeQueue(SqQueue* Q, QElemType *e) {

	//栈为空
	if (Q->front == Q->rear) {
		return ERROR;
	}
	//将出队队列赋值给e
	*e = Q->data[Q->front];

	//头指针前移
	Q->front = (Q->front + 1) % MAXSIZE;

	//返回正确状态吗
	return OK;
}

链式队列

链式队列定义

//定义结点结构
typedef struct QNode{
	QElemType data;//数据域
	struct QNode *next;//指针域
}QNode,*QueuePtr;


//定义队列头尾指针
typedef struct {
	QueuePtr front, rear;//头尾指针
}LinkQueue;

链式队列入队

//入队
Status EnQueue(LinkQueue* Q, QElemType e) {
	
	//开辟内存空间
	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));

	//分配内存空间失败
	if (!s) {
		exit(_CRT_GUARDOVERFLOW);
	}

	//s结点的数据
	s->data = e;

	//s的下一结点为空
	s->next = NULL;

	//头指针指向s结点
	Q->rear->next = s;

	//将s结点设置为头指针
	Q->rear = s;
}

链式队列出队

//出队
Status DeQueue(LinkQueue* Q, QElemType* e) {

	//声明结点p
	QueuePtr p;

	//队列为空
	if (Q->front == Q->rear) {
		return ERROR;
	}

	//将要删除的结点赋值给结点p
	p = Q->front->next;

	//将删除的数据赋值给e
	*e = p->data;

	//将头结点指向出队结点的下一结点
	Q->front->next = p->next;

	//如果出队的是最后一个元素
	if (Q->rear == p) {
		//将头指针指向尾指针
		Q->rear = Q->front;
	}

	//释放结点p 出队成功
	free(p);

	//返回正确状态码
	return OK;
}

你知道的越多 你不知道的越多 嘿 我是小博 带你一起看我目之所及的世界……