数据结构 4 （栈和队列）
目录
一、栈
1、顺序栈
1）顺序栈的定义
2）顺序栈的操作
1.创建
2.判空
3.判满
4.入栈
5.出栈
6.输出栈内的值
7.销毁栈
2、链栈
1）链栈的定义
2）链栈的操作
1.创建
2.判空
3.入栈
4.出栈
二、队列
1、特点
2、顺序队列
3、循环顺序队列结构体的定义
4、循环顺序队列的操作
1）创建
2）判空
3）判满
4）入队
5）出队
6）返回队列中元素的个数
7）销毁
一、栈
特点：
先进后出（FILO）
栈和队列都是操作受限的线性表
1、顺序栈
逻辑结构：一对一，线性结构
存储结构：顺序结构
能操作的一端是栈顶，不能操作的一端为栈底，栈只有一端可以操作，遵循栈思想
data存连续的值（类似数组，但是只通过top访问）；
top存储记录栈顶的位置，初始值位-1；
1）顺序栈的定义
typedef struct
{int data[MAX]; //存储栈中的数据int top; //记录栈顶元素的位置(初始值为-1)
}stack,*stack_p;2）顺序栈的操作
1.创建
//1、创建顺序栈
stack_p create_stack()
{stack_p S = (stack_p)malloc(sizeof(stack));if(S==NULL){return NULL;}bzero(S,sizeof(stack)); //把申请的所有空间都初始为0S->top = -1; //-1是栈顶位置top的初始值return S;
}
2.判空
//2、判空
int empty_stack(stack_p S)
{if(S==NULL){return -1;}return S->top==-1;
}
3.判满
//3、判满
int full_stack(stack_p S)
{if(S==NULL){return -1;}return S->top==MAX-1;
}
4.入栈
//4、入栈
void push_stack(stack_p S,int value)
{if(S==NULL){return;}if(full_stack(S)){return;}//先加栈顶位置，再将元素压入栈//先加再压//S->data[++(S->top)] = value;S->top++;S->data[S->top] = value;
}5.出栈
//5、出栈
int pop_stack(stack_p S)
{if(S==NULL){return -1;}if(empty_stack(S)){return -2;}return S->data[S->top--];
}6.输出栈内的值
//输出栈中的元素
void show_stack(stack_p S)
{if(S==NULL) {return;}if(empty_stack(S)) {return;}for(int i=S->top;i>=0;i--){printf("%d\n",S->data[i]);}
}
7.销毁栈
//销毁栈
void destory(stack_p *S)
{if(S==NULL) {return;}free(*S); *S=NULL;
}
2、链栈
和链表一样结构一致，但是操作受限，没有头结点，也不存储记录链栈的长度，
只通过栈顶指针记录链栈中要出栈元素的地址
只通过链的一端操作，如果入栈在头部，那么出栈也在头部
1）链栈的定义
typedef struct node
{int data;struct node *next;
}node,*node_p;
2）链栈的操作
1.创建
//创建结点
node_p create_node(int value)
{ node_p new=(node_p)malloc(sizeof(node));if(new==NULL) {return NULL;}new->data=value;new->next=NULL;return new;
}
2.判空
//判空
int empty_stack(node_p S)
{return S==NULL;
}
3.入栈
//3、入栈
//入栈操作需要修改主函数中栈顶指针的指向
void push_stack(node_p *S,int value)
{//S是一个二级指针，保存主函数内栈顶指针的地址if(S==NULL){return;}//不用判断*S,因为如果*S==NULL说明栈中没有元素node_p new = create_node(value);new->next = *S; //新结点指向原来的栈顶元素*S = new; //让主函数中的栈顶指针S指向新的栈顶结点
}4.出栈
//4、出栈
int pop_stack(node_p *S)
{if(*S==NULL){return -1;}if(empty_stack(*S)){return -2;}int ret = (*S)->data;node_p del = *S; //先保存栈顶结点*S = (*S)->next; //让栈顶指针向后指一个结点free(del); //释放栈顶元素return ret;
}
二、队列
也是操作受限的线性结构
一端只允许插入，另一端只允许删除
1、特点
先进先出（FIFO）
允许插入的一端是队尾，允许删除的一端叫队头
队头永远要指向可以出队的元素，队尾永远只想可以入队的位置
2、顺序队列
普通的顺序队列，由于只能一个方向插入数据，会造成假溢现象
会使用循环队列代替普通的顺序队列
循环队列也会存在，判空和判满条件相同的问题
所以在实现循环队列是，往往会人为浪费一个空间，用来做队列的操作
3、循环顺序队列结构体的定义
typedef struct
{int data[MAX];int front;int rear;
}queue,*queue_p;4、循环顺序队列的操作
1）创建
//1、创建循环队列
queue_p create_que()
{queue_p Q = (queue_p)malloc(sizeof(queue));if(Q==NULL){return NULL;}bzero(Q,sizeof(queue));Q->front = Q->rear = 4;return Q;
}2）判空
//2、判空
int empty_que(queue_p Q)
{if(Q==NULL){return -1;}//如果队头和队尾在同一个位置说明队列为空return Q->front==Q->rear;
}3）判满
//3、判满
int full_que(queue_p Q)
{if(Q==NULL){return -1;}return (Q->rear+1)%MAX==Q->front;
}4）入队
//4、入队,队尾指针向后移动
void push_que(queue_p Q,int value)
{if(Q==NULL){return;}if(full_que(Q)){return;}Q->data[Q->rear] = value;Q->rear = (Q->rear+1)%MAX;
}5）出队
//5、出队,队头指针向后移动
int pop_que(queue_p Q)
{if(Q==NULL){return -1;}if(empty_que(Q)){return -2;}//先把要出队的元素保存起来int ret = Q->data[Q->front];//将队头位置向后移Q->front = (Q->front+1)%MAX;return ret;
}6）返回队列中元素的个数
//6、返回队列中元素的个数
int count_que(queue_p Q)
{if(Q==NULL){return -1;}return (Q->rear-Q->front+MAX)%MAX;
}7）销毁
//7、销毁队列
void destory(queue_p *Q)
{if(Q==NULL||*Q==NULL){return;}free(*Q);*Q=NULL;
}