9.24 数据结构-栈、队列总结
一、栈
1.1 概念
1、操作受限的线性表,只能在一端插入删除。
2、先进后出或者后进先出的线性表。
1.2 顺序栈
1.2.1 顺序栈的概念
1、借助数组来存储的栈
1.2.2 顺序栈的组成
1、用来存储栈的数组
2、记录下标的top
1.2.3 顺序栈结构体类型
typedef struct
{
int data[MAX];//存储栈元素的数组
int top;//记录栈顶元素的下标
}stack,*Pstack;
1.2.4 顺序栈的相关操作(功能函数)
1> 创建栈
Pstack create()
{
Pstack p = malloc(sizeof(stack));
if(NULL==p)
{
printf("创建栈失败\n");
return NULL;
}
p->top = -1;
return p;//返回栈地址
}
2> 入栈
1、判断栈满
2、入栈先加后压
int push(Pstack Z,int e)
{
if(Z->top==MAX-1)//判断栈满
{
printf("栈满无法入栈\n");
return -1;
}
//入栈先加后压
Z->top++;
Z->data[Z->top] = e;
printf("入栈成功\n");
return 0;
}
3> 遍历栈
3.1从栈底到栈顶遍历
int output1(Pstack Z)
{
if(Z->top==-1)
{
printf("栈空,无法输出\n");
return -1;
}
int i;
for(i =0;i<=Z->top;i++)
{
printf("%d\t",Z->data[i]);
}
printf("\n");
return 0;
}
3.2从栈顶到栈底遍历
int output2(Pstack Z)
{
if(Z->top==-1)
{
printf("栈空,无法输出\n");
return -1;
}
int i;
for(i =Z->top;i>=0;i--)
{
printf("%d\t",Z->data[i]);
}
return 0;
}
4> 出栈
1、判断栈空
2、先弹后减
int pop(Pstack Z)
{
if(Z->top==-1)//判断栈空
{
printf("栈空无法出栈\n");
return -1;
}
//出栈先弹后减
printf("%d\t",Z->data[Z->top]);
Z->top--;
return 0;
}
5> 获取栈顶元素
int huoqu(Pstack Z)
{
if(Z->top==-1)
{
printf("获取失败\n");
return -1;
}
return Z->data[Z->top];
}
6>求栈的大小
int sizestack(Pstack Z)
{
return Z->top+1;
}
7>销毁栈
int destroy_stack(Pstack Z)
{
free(Z);
Z=NULL;
printf("销毁成功\n");
return 0;
}
1.3链式栈
1>创建链式栈
typedef struct node//正常节点结构体
{
int data;
struct node *next;
}xxx,*Pxxx;
typedef struct//栈顶指针的结构体
{
int len;
Pxxx top;
}stack,*Pstack;
Pstack create()//创建栈顶指针节点
{
Pstack p = malloc(sizeof(stack));
if(p==NULL)
{
printf("申请节点失败\n");
return NULL;
}
p->len=0;
p->top=NULL;
return p;
}
2>入栈
int push(Pstack S,int e)//入栈
{
if(S==NULL)
{
printf("入栈失败\n");
return -1;
}
Pxxx p = malloc(sizeof(xxx));
p->data = e;
p->next = S->top;
S->top = p;
S->len++;
printf("入栈成功\n");
return 0;
}
3> 出栈
int pop(Pstack S)//出栈
{
if(S->top==NULL||S==NULL)
{
printf("栈空出栈失败\n");
return -1;
}
Pxxx Q = S->top;
printf("出栈元素是:%d\n",Q->data);
S->top = Q->next;
free(Q);
Q = NULL;
S->len--;
return 0;
}
4>遍历
int ouput_stack(Pstack S)//输出
{
if(S==NULL||S->top==NULL)
{
printf("栈不存在或者空\n");
return -1;
}
Pxxx t = S->top;
while(t!=NULL)
{
printf("%d\t",t->data);
t = t->next;
}
return 0;
}
二、队列
2.1 概念
1、操作受限的线性表,只能队尾入队,队头出队。
2、先进先出,后进后出的线性表。
2.2 顺序队列
2.2.1 概念
1、借助数组来存储的队列。
2.2.2 组成
1、存储队列元素的数组
2、队头下标
3、队尾下标
2.2.3 假溢满现象:
2.3 循环顺序队列
出队,入队,队长推导:
2.3.1 引入目的
循环队列可以解决顺序队列的假溢出现象。
2.3.2 队列结构体类型
#define MAX 5
typedef struct//循环队列结构体
{
int data[MAX];
int rear;
int front;
}queue,*Pqueue;
2.3.3 相关操作(功能函数)
1> 创建循环队列
Pqueue create()//创建循环队列
{
Pqueue p = malloc(sizeof(queue));
if(NULL==p)
{
printf("创建循环队列失败\n");
return NULL;
}
p->rear = 0;
p->front = 0;
return p;
}
2>入队
int enqueue(Pqueue D,int e)
{
if((D->rear+1)%MAX==D->front)
{
printf("队满无法入队\n");
return -1;
}
D->data[D->rear] =e;//入队
D->rear = (D->rear+1)%MAX;//队尾下标+1
printf("入队成功\n");
return 0;
}
3>遍历
int output(PQueue D){
//输出队头到队尾信息//可以分情况讨论也可以直接(D->rear-D->front+MAX)%MAX队列元素长度做判断条件
int i;
if(D->rear>D->front){
for(i=D->front;i<D->rear;i++){
printf("%d\t",D->data[i]);
}
}else{
//front-->MAX-1
for(i=D->front;i<=MAX-1;i++){
printf("%d\t",D->data[i]);
}
//0->rear
for(i=0;i<D->rear;i++){//因为D->rear指向队列空白下标,所以是<不是<=
printf("%d\t",D->data[i]);
}
}
}
4>出队
int outqueue(Pqueue D)
{
if(D->rear==D->front)
{
printf("队列为空无法出队\n");
return -1;
}
printf("出队元素:%d\n",D->data[D->front]);//出队
D->front = (D->front+1)%MAX;//队头下标+1
return 0;
}
5> 求队列长度
6>释放队列
int destroy(Pqueue D)
{
if(D==NULL)
{
printf("销毁失败\n");
return -1;
}
free(D);
D = NULL;
return 0;
}
2.4链式队列
2.4.1 链式队列结构体类型
typedef struct node
{
int data;
struct node *next;
}xxx,*Pxxx;
typedef struct
{
int len;
Pxxx rear;
Pxxx front;
}queue,*Pqueue;
2.4.2 链式队列的相关操作(功能函数)
1>创建
Pqueue create()//创建队列头结点
{
Pqueue p = malloc(sizeof(queue));
if(p==NULL)
{
printf("申请头结点失败\n");
return NULL;
}
p->len=0;
p->rear = NULL;
p->front = NULL;
return p;
}
2>入队
1、没有节点时
p->next = NULL;
D->rear=p
D->front = p;
2、有节点时
p->next = NULL;
D->rear->next = p;
D->rear = p;
int enqueue(Pqueue D,int e)
{
if(D==NULL)
{
printf("入队失败\n");
return -1;
}
Pxxx p = malloc(sizeof(xxx));
p->data = e;
if(D->rear==NULL)//没有节点
{
D->front = p;
D->rear = p;
p->next = NULL;
}
else//有节点
{
D->rear->next = p;
D->rear = p;
p->next =NULL;
}
D->len++;
return 0;
3>出队
当有多个节点时:
当有1个节点时
int outqueue(Pqueue D)
{
if(D==NULL||D->rear==NULL)
{
printf("队列为空\n");
return -1;
}
Pxxx Q;
if(D->rear!=D->front)//不只一个节点
{
Q = D->front;//保留要出队的节点
printf("出队元素:%d\n",Q->data);
D->front = Q->next;
}
else//只有一个节点
{
Q = D->front;//保留要出队的节点
printf("出队元素:%d\n",Q->data);
D->front = D->rear= NULL;
}
free(Q);
Q = NULL;
D->len--;
return 0;
}
4> 遍历
int output(Pqueue D)
{
if(D==NULL||D->rear==NULL)
{
printf("没有节点输出失败\n");
return -1;
}
int i;
Pxxx t = D->front;
for(i = 0;i<D->len;i++)
{
printf("%d\t",t->data);
t = t->next;
}
return 0;
}
5> 销毁队列
int destroy(Pqueue D)
{
Pxxx t;
while(D->front!=NULL)
{
t = D->front;
D->front = D->front->next;
free(t);
}
free(D);
D=NULL;
printf("销毁成功\n");
}