堆栈和队列

一、栈

1.定义

​ 栈是一种满足后进先出的数据结构；例：死胡同

1. 允许进行插入、删除操作的一端称为栈顶 top
2. 表的另一端称为栈底
3. 当栈中没有数据元素时，称为空栈
4. 栈的插入操作通常称为进栈或入栈
5. 栈的删除操作通常称为退栈或出栈

void InitStack(SqStack *&s);
void DestroyStack(SqStack *&s);
bool StackEmpty(SqStack *s);
bool Push(SqStack *&s,ElemType e);
bool Pop(SqStack *&s,ElemType &e);
bool GetTop(SqStack *s,ElemType &e);

2.类型

①顺序栈
②链栈

2.1顺序栈

顺序栈四要素：
①栈空条件：top=-1
②栈满条件：top=MaxSize - 1
③进栈操作：top++；将e放在栈顶
④退栈操作：从top取出；top--

//顺序栈基本运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct 
{	
	ElemType data[MaxSize];
	int top;//栈指针
} SqStack;//顺序栈类型
void InitStack(SqStack *&s)
{
	s=(SqStack *)malloc(sizeof(SqStack));
	s->top=-1;//top为下标，始终指向栈顶元素；在以数组构成的栈中，初始值为-1,自加一次则指向下标为0的元素
} 
void DestroyStack(SqStack *&s)
{
	free(s);
}
bool StackEmpty(SqStack *s)
{
	return(s->top==-1);
}
bool Push(SqStack *&s,ElemType e)
{
	if (s->top==MaxSize-1)//栈满的情况，即栈上溢出
		return false;
	s->top++;
	s->data[s->top]=e;
	return true;
}
bool Pop(SqStack *&s,ElemType &e)
{
	if (s->top==-1)//栈为空的情况，即栈下溢出
		return false;
	e=s->data[s->top];
	s->top--;
	return true;
} 
bool GetTop(SqStack *s,ElemType &e)
{
	if (s->top==-1)//栈为空的情况，即栈下溢出
		return false;
	e=s->data[s->top];
	return true;
}

2.2 链栈

//链栈基本运算算法
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
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;
	while (p!=NULL)
	{	
		free(s);
		s=p;
		p=p->next;
	}
	free(s);	//s指向尾结点,释放其空间
}
bool StackEmpty(LinkStNode *s)
{
	return(s->next==NULL);
}
void Push(LinkStNode *&s,ElemType e)
{	LinkStNode *p;
	p=(LinkStNode *)malloc(sizeof(LinkStNode));
	p->data=e;				//新建元素e对应的结点p
	p->next=s->next;		//插入p结点作为开始结点
	s->next=p;
}
bool Pop(LinkStNode *&s,ElemType &e)
{	LinkStNode *p;
	if (s->next==NULL)		//栈空的情况
		return false;
	p=s->next;				//p指向开始结点
	e=p->data;
	s->next=p->next;		//删除p结点
	free(p);				//释放p结点
	return true;
}
bool GetTop(LinkStNode *s,ElemType &e)
{	if (s->next==NULL)		//栈空的情况
		return false;
	e=s->next->data;
	return true;
}

3.表达式

算数表达式=中缀表达式【考虑运算符优先性】
二叉树画法：【根据优先级顺序，找运算符；整体上（）> 乘除 > 加减 ，局部上从左到右）
①找到符号两边的两个数
②先写符号，再写数
③根据中序，依次合并，画出二叉树

转后缀表达式：
1.遇到操作数：直接输出
2.栈为空时，遇到运算符，直接入栈
3.遇到左括号：将其入栈
4.遇到右括号：执行出栈操作，直到弹出栈的是左括号，括号不输出。
5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
6.最终将栈中的元素依次出栈，输出。

简便方法：
①根据优先级顺序中缀符号两边，两两结合，用括号括起来。
②前缀则把符号挪到括号左侧，后缀则挪到右侧。
③最后括号都去掉

前缀与后缀【不用考虑运算符优先性】
后缀表达式---->二叉树以后序输出
二叉树画法：①找到符号的前两个数
②先写符号，再写数
③根据后序，依次合并，画出二叉树
前缀表达式---->二叉树以前序输出

4.出入栈序列

入栈序列为1,2,3,4,5,6，则不可能的序列
栈顶有高位元素后，+出栈的首先得是高位元素；

5.进制转化

高进制->低进制，除法
余数依次进栈，依次输出即可

6.括号匹配

二、队列

1.顺序队列基本代码

(1) 入队时队尾指针前进1：(rear+1)%QueueSize

(2) 出队时队头指针前进1：(front+1)%QueueSize

(3) 队列长度：(rear-front+QueueSize)%QueueSize

​ 现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设队头不存放数据)

​ 答案：(rear-front+N)%N

(4) 队空和队满的条件

​ 为了区分队空还是堆满的情况，有多种处理方式：

方式1： 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，即约定以"队头指针在队尾指针的下一位置作为队满的标志"。

​ 队满条件为：(rear+1)%QueueSize==front

​ 队空条件为：front==rear

​ 队列长度为：(rear-front+QueueSize)%QueueSize

方式2： 增设表示队列元素个数的数据成员size，此时，队空和队满时都有front==rear。

​ 队满条件为：size==QueueSize

​ 队空条件为：size==0

方式3： 增设tag数据成员以区分队满还是队空

​ tag表示0的情况下，若因删除导致front==rear，则队空；

​ tag等于1的情况，若因插入导致front==rear则队满

2.类型

①顺序队列（非环形）
②顺序队列（环形）
③链队

2.1 顺序队列（非环形）

//顺序队列（非环形队列）基本运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
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++;							//队尾增1
	q->data[q->rear]=e;					//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.2 顺序队列（环形）

//顺序队列（环形队列）基本运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
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;
}

2.3 链队

同样包括单链表的队列，循环链表队列

//链队运算算法
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct DataNode
{	
	ElemType data;
	struct DataNode *next;
} DataNode;				//链队数据结点类型
typedef struct
{	
	DataNode *front;
	DataNode *rear;
} LinkQuNode;			//链队类型
void InitQueue(LinkQuNode *&q)
{	
	q=(LinkQuNode *)malloc(sizeof(LinkQuNode));
	q->front=q->rear=NULL;
}
void DestroyQueue(LinkQuNode *&q)
{
	DataNode *p=q->front,*r;//p指向队头数据结点
	if (p!=NULL)			//释放数据结点占用空间
	{	r=p->next;
		while (r!=NULL)
		{	free(p);
			p=r;r=p->next;
		}
	}
	free(p);
	free(q);				//释放链队结点占用空间
}
bool QueueEmpty(LinkQuNode *q)
{
	return(q->rear==NULL);
}
void enQueue(LinkQuNode *&q,ElemType e)
{	DataNode *p;
	p=(DataNode *)malloc(sizeof(DataNode));
	p->data=e;
	p->next=NULL;
	if (q->rear==NULL)		//若链队为空,则新结点是队首结点又是队尾结点
		q->front=q->rear=p;
	else
	{	q->rear->next=p;	//将p结点链到队尾,并将rear指向它
		q->rear=p;
	}
}
bool deQueue(LinkQuNode *&q,ElemType &e)
{	DataNode *t;
	if (q->rear==NULL)		//队列为空
		return false;
	t=q->front;				//t指向第一个数据结点
	if (q->front==q->rear)  //队列中只有一个结点时
		q->front=q->rear=NULL;
	else					//队列中有多个结点时
		q->front=q->front->next;
	e=t->data;
	free(t);
	return true;
}

三、思考题

3.1两个栈实现一个队列