数据结构知识点-栈和队列_地址高端作为栈底是什么意思

栈

定义：只能在一端进行插入和删除运算的线性表
逻辑结构：与线性表相同，仍为一对一关系
存储结构：用顺序栈或链栈存储均可，但顺序栈更常见
运算规则：只能在栈顶运算，遵循后进先出或先进后出的原则

队列

定义：只能在表一端插入，在另一端删除运算的线性表
逻辑结构：与线性表一直，仍为一对一的关系
存储结构：顺序队列或链队均可
运算规则：先进先出

栈和队列的区别

栈、队列是一种特殊的操作受限的线性表，区别仅在于运算规则不同

一般线性表
逻辑结构：一对一
存储结构：顺序表、链表
运算规则：随即、顺序存储

栈
逻辑结构：一对一
存储结构：顺序表、链表
运算规则：后进先出

队列
逻辑结构：一对一
存储结构：顺序表、链表
运算规则：先进先出

顺序栈
当base==top时表示空栈，top表示栈顶元素之上的下标地址，当栈满时1、报错。2、分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈。

# 顺序栈的表示
#define MAXSIZE 100
typdef struct
{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;
1
2
3
4
5
6
7
8

顺序栈的初始化

1、 构造一个空栈
2、分配空间并检查空间是否分配失败，若失败则返回错误
3、设置栈底和栈顶指针S.top =S.base
4、设置栈的大小

#栈初始化
Status InitStack(Sqstack &S)
{
	S.base = new SElemType[MAXSIZE];
	if(!S.base) #如果栈不为空
		return OVERFLOW;
	S.top = S.base;
	S.stackSize = MAXSIZE;
return OK;
}
1
2
3
4
5
6
7
8
9
10

#判断栈空
bool StackEmpty(SqStack S)
{
	if(S.top == S.base)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7
8

#求顺序栈的长度
int Stacklength(SqStack S)
{
	return S.top-S.base;
}
1
2
3
4
5

#清空顺序栈
Status ClearStack(SqStack S)
{
	if(S.base) #如果为空
	S,top = S.base; #当栈顶指向栈低的时候为空
return OK;
}
1
2
3
4
5
6
7

#销毁顺序栈
Status DestroyStack(SqStack &S)
{
	if(S.base)
	{
		delete S.base;
		S.stackSize=0;
		S.base =S.top =NULL;
	}
}
1
2
3
4
5
6
7
8
9
10

顺序栈进栈
1、判断是否满栈，若满则出错
2、元素e压入栈顶
3、栈顶指针+1

#入栈
Status Push(SqStack &S，SElemType e)
{
	if(S.top -S.base == S.stacksize)#栈满
		return error;
	*S.top++ =e;#先入栈，然后栈顶元素+1
//*S.top =e;S.top++	
return OK;
}
1
2
3
4
5
6
7
8
9

#出栈
Status Pop(SqStack &S,SElemType &e)
{
	if(S.top == S.base)
		return ERROR;
	e= *--S.top;
	//--s.top;e=*S.top;
	return OK;
}
1
2
3
4
5
6
7
8
9

取栈顶元素

#取栈顶元素
Status GetTop(SqStack S,SElemType &e)
{
	if(S.top == S.base)
		return ERROR;#栈空
	e = *(S.top -1);

	return OK;
}
1
2
3
4
5
6
7
8
9

在一个具有n个单元的顺序栈中，假设以地址高端作为栈低，以top作为栈顶指针，当进行进栈处理时top–

双栈共享一个栈空间
优点：互相调剂，灵活性强，减少益处的机会。

将编号0和1的两个栈存放于一个数组空间v[m]中，栈低分别位于数组的两端，当第0号栈的栈顶top[0]=-1时为空，当1号栈的栈顶指针top[1]等于m时该栈为空，两个栈均从两端向中间增长，当top1-top0=1时栈满。
共享栈栈空：top[i] == bot[i],top[o]=bot[0]，当栈顶等于栈底时为空
共享栈栈满：top[1]-top[0]=1

数据结构定义

typedef struct
{
	int top[2],base[2];#定义栈顶和栈低
	SElemType *V;#定义栈数组
	int m;#栈最大可容纳元素个数
}DblStack;
1
2
3
4
5
6

链栈的表示
链栈是运算受限的单链表，只能在表头进行操作，故没有必要附加头结点，栈顶指针就是链表的头指针

typedef struct StackNode
{
	SElemType data;
	struct StackNode *next;
}StackNode,*LinkStack;//StackNode表示运算的结点，linkStack表示链栈
LinkStack S;
1
2
3
4
5
6

#链栈初始化
void InitStack(LinkStack &s)
{
	S =NULL; #S指向空
}
1
2
3
4
5

#判断链栈是否为空
status Stackempty(LinkStack S)
{
	if(S==NULL)
		return true;
	else
		return False;
}
1
2
3
4
5
6
7
8

#链表入栈
Status Push(LinkStack &s,SElemType e)
{
	p=new stackNode; #生成新结点
	if(!p)
		return overflow; #溢出
	p->data = e;
	p->next = s;# s是旧的链表表头
	s = p;#把新插入的结点设为表头
return ok;
}

1、新生城结点
2、指定新结点数据
3、新结点指向旧链表
4、设置新结点为表头结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#链表出栈
status Pop(LinkStack &S,SElemType &e)
{
	if(S==NUll)
		return ERROR;
	e = s->data;
	P = s;
	s = s->next;
	detete p;
return OK;
}
1、取表头结点
2、将旧的表头给新的结点
3、将旧的表头指向旧结点的下一个结点
4、删除旧的结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#取链栈顶元素
SElemType GetTop(LinkStack S)
{
	if(S == NULL)
		exit(1);
	else
		return S->data;
}
1
2
3
4
5
6
7
8

栈与递归
递归的定义，若一个对象部分包含它自己，或用它自己给自己定义，则称这个对象是递归的；
若一个过程直接或间接的调用自己，则称这个或称是递归的。

用分治法求解递归问题
分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同的子问题来求解。
必备的三个条件：
1、能将一个问题转变为一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象。
2、可以通过上述转为为简单问题。
3、必须有一个明确的递归出口，或称为递归边界。

队列

# 队列数据结构
Typedef struct
{
	QElemType *base;
	int front;
	int rear;
}SqQueue;
1
2
3
4
5
6
7

队空：rearfront;
队满：rearfront；
入队：base[rear++]=x;
出队：x=base[front++];

队列存在的问题
设置队列大小为M

front = 0；rear=M时再入队，真溢出。
front！=0，rear=M时再入队，假溢出。

假溢出的原因，因为队列是遵循先进后出的原则，当尾指针到达末尾时就不能在插入元素，再插入元素会导致尾指针越届，但是在队列中还有剩余的可用空间，队列没有真正的满，可用循环队列或者链式队列解决问题。

循环队列
循环队列可以解决普通队列假溢出的问题。
入队：base[rear]=x；rear = (rear+1)%M；
出队：x=base[front]；front=(front+1)%M;
队空：frontrear；
队满：(rear+1)%Mfront
求队长：(rear-front+MAXQSIZE)%MAXQSIZ #(队尾-队头+MAXSIZE)%MAXSIZE

当使用普通的方式区分队空和队满时候，判断条件都是front==rear。
解决方案
1、设置一个标志区分队空、队满。
2、少用一个空间元素：

#循环队列结构
Typedef struct
{
	QElemType *base;#动态分配指针
	int front;#队头
	int rear;#队尾
}SqQueue;
1
2
3
4
5
6
7

#循环队列初始化
Status InitQueue(SqQueue &Q)
{
	Q.base = new QElemType[mAXQSIZE];
	if(!Q.base) #队列不是空的
		exit(OVERFLOW);
	Q.front=Q.rear=0;
return OK;
}
1
2
3
4
5
6
7
8
9

#求循环队列长度
int QueueLength(SqQueue Q)
{
	return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
1
2
3
4
5

#对列入队
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;
	return OK;
}
1
2
3
4
5
6
7
8
9

#循环队列出队
Status DeQueue(LinkQueue &Q,QElemType &e)
{
	if(Q.front==Q.rear)#队空
		return ERROR;
	e=Q,base[Q.front];
	Q.front = (Q.front+1)%MAXQSIZE;
return 0;
}
1
2
3
4
5
6
7
8
9

链队列

Typedef struct QNode
{
	QElemType data;#数据域
	struct Qnode *next;#指针域
}QNode,*QueuePtr;

Typedef struct
{
	QueuePtr front;#队头指针
	QueuePtr rear;#队尾指针
}LinkQueue;
1
2
3
4
5
6
7
8
9
10
11

#队列初始化
Status InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
	if(!Q.front)
		exit(OVERFLOW);
	Q.front->next=NULL;
return OK;
}
1
2
3
4
5
6
7
8
9

#销毁队列
Status DesstroyQueue(LinkQueue &Q)
{
	while(Q.front)
	{
		Q.rear=Q.front->next;
		free(Q.front);
		Q.front = Q.rear;
	}
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11

案例分析

数制转换
1、初始化一个空栈
2、当十进制数N非零时，循环执行以下操作：
把N与8求余得到八进制数压入栈S；
N更新为N与8的商；
3、当栈S非空时，循环执行以下操作：
弹出栈顶元素e，输出e。

#对于任意一个非负十进制，打印输出与其相等的八进制数
void conversion(int N)
{
	InitStack(s);#初始化栈
	while(N)#当N不为0时
	{
		Push(S,N%8);#把N与8求余得到的八进制压入栈S
		N=N/8;#N更新为N与8的商
	}
	while(!StackEmpty(S))
	{
		Pop(S,e);
		cout<<e;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

括号匹配
1、初始化一个空栈S
2、设置一标记变量flag，用来标记匹配结果以控制循环及返回结果，1表示匹配成功，0表示匹配错误，初始值为1
3、扫描表达式，依次读入字符ch，如果表达式没有扫描完成或flag非零，则执行以下操作：
（1）若ch是左括号‘[’‘(’，则将其压入栈
（2）若ch是右括号‘）’，则根据当前栈顶元素分析；若栈非空且栈顶元素是‘（’则出栈匹配成功，否则匹配错误flag=0；
（3）若ch是右括号‘]’，则根据当前栈顶元素分析；若栈非空且栈顶元素是‘[’则出栈匹配成功，否则匹配错误flag=0；
4、退出循环后，如果栈空且flag值为1，则匹配成功，返回true，否则返回false。

算术表达式求值
设置两个栈OPND（操作数运算），OPTR（运算符）
1、初始化两个栈，将表达式起始符‘#’压入OPTR栈
2、扫描表达式，读入第一个字符ch，如果表达式没有扫描完成，或OPTR的栈顶元素不为‘#’，则执行以下操作：
（1）若ch不是运算符，则压入OPND栈，读入下一字符ch；
（2）若ch是运算符，则根据OPTR的栈顶元素和ch的优先级比较
若栈顶元素优先级小于ch，则ch压入OPTR栈，读入下一字符ch
若栈顶元素优先级大于ch，则弹出OPTR栈顶元素，从OPND弹出两个数，进行相应运算，结果压入OPND栈
若栈顶元素优先级等于ch，则OPTR的栈顶元素是‘(’且ch是‘)’,弹出OPTR栈顶的‘(’，相当于匹配括号，然后读入下一个字符ch
3、OPND栈顶元素即为表达式求值结果，返回此元素。

OperandType EvaluateExpression()
{
	IniStack(OPTR);Push(OPTR,'#');
	InitStack(OPND);ch=getchar();
	while(ch != '#' || GetTop(OPTR) != '#')
	{
		if(!In(ch))
		{
			Push(OPND,ch);
			ch = getchar();
		}
		else
		{
			switch(Precede(GetTop(OPTR),ch))
			{
				case '<':Push(OPTR,ch);ch = Getchar();break;
				case '>':Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPnd,Opreate(a,theta,b));break;
				case '=':Pop(OPTR,x);ch=getchar();break
			}
		}
	}
	return GetTop(OPND);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

迷宫求解
需要解决的问题：
1、表示迷宫的数据结构
2、试探方向
3、栈的设计
4、防止重复到达，避免死循环
1、表示迷宫的数据结构
用maze[m][n]表示，0<=i<m，0<=j<n
maze[i][j] = 0 #表示路通
maze[i][j]=1#表示不通
改进
maze[m+2][n+2]
maze[i][j]=1，i=0或m+1,j=0或n+1
入口坐标为（1，1），出口坐标为（m，n）

#迷宫定义
#define m 8
#define n 8
int maze[m+2][n+2];
#试探方向
typedef struct
{
	int x,y;
}PosType;
#栈的设计
typedef struct
{
	int ord;
	PostType seat;
	int di;
}SElemType;
#防止重复到达某点
#走不同的路加标记
MarkPrint()操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

伴舞问题
1、设置两个队列分别存放男士和女士
2、假设男士和女士的记录存放在一个数组中作为数入，然后依次扫描该队列数组的各个元素，并根据性别来决定是男士入队还是女士入队
3、当队列构造完成后，依次将两队列的队头元素出队匹配舞伴，直到某队列变空为止
4、此时，若某队仍然等待匹配者，则输出此队列中排在队头的等待者，此人是下一轮舞曲开始时第一个可获得舞伴的人

#舞伴问题
typedef struct
{
	char name[20];
	char sex;
}Person;
#define MAXQSIZE 100
typedef struct
{
	Person *base;
	int front;
	int rear;
}SqQueue;
SqQueue Mdancers,Fdancers;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#舞伴问题
SqQueue *Mdan(Squeue *MQ)#初始化度列
{
	MQ = (SqQueue *)malloc(sizeof(Squeue));
	if(!MQ->base)#如果MQ不是1
		exit(0)
	MQ->front = MQ->rear = -1;
return MQ
}
InQueue(SqQueue *MQ,Persion p)
{
	if(MQ->rear+1)%20 == MQ->front)
	{
		printf("满")
	}
	else
	{
		MQ->rear++;
		MQ->base[MQ->rear] = p;
	}
}
int IsEmpty(Squeue *MQ)
{
	if(MQ->front == MQ->rear)
		return OK
	else
		return ERROR;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <stdio.h>
int main()
{
	int num;
	person p[20];
	SqQueue *mq;
	SqQueue *fq;
	mq = mdancers(mq);
	fq = mdancers(fq);
}
1
2
3
4
5
6
7
8
9
10

优先级队列–堆
每次从队列中取出的是具有最高优先权的元素。
任务优先权及执行顺序的关系

大根堆

共享栈

typedef struct
{
	int top[2];
	int bot[2];
	SElemType *V;
	int m;
}DbStack;

#初始化栈
Status Init_Stack(DblStack &s,int m)
{
	s.V = (*Dbstack)malloc(sizeof(DblStack));
	s.bot[0] = -1;
	s.bot[1] = m;
	s.top[0] = -1;
	s.top[1] = m;
return OK;
}

#判断空
int IsEmpty(DblStack s,int i )
{
	return s.top[i] == s.bot[i];
}
#判断是否满
int IsFull(DblStack s)
{
	if(s.top[0] + 1==s.top[1])
		return 1;
	else
		return 0;
}
#入栈
void DblPush(DblStack &s,SElemType x,int i)
{
	if(IsFull(s))
		exit(1);
	if(i==0)
		s.V[++s.top[0]] = x;#初始值top[0]=-1;
	else 
	  s.V[--s.top[1]] = x;#初始值top[1]=m;
}
#出栈
int DblPop(DblStack &s,int i,SElemType &x)
{
	if(IsEmpty(S,i))
		return 0;
	if(i==0)
		x = s.V[top[0]];
		s.top[0]--;
	else
	  x = s.V[top[0]];
		s.top[1]++;
 return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

已知单链表的表头指针，链表中存储的都是整形数据，递归的实现以下算法
1、求链表中最大整数
2、求链表的结点个数
3、求所有整数的平均值

int GetMax(LinkList p)
{
	if(!p->next)
		return p->data;
	else
	{
		int max = GetMax(p->next);
		return p->data >= max :p->data:max; #如果当前结点的数据大于最大值，则最大值取当前结点，否则最大值还是最大值。
	}
}
1
2
3
4
5
6
7
8
9
10
11