/*
*栈先加后减 S->[++top],S->[top--]
*/
简单理解就是:先出栈的在最右侧
符号最高时出栈
/*
*队列:FIFO,先进先出,头删尾进(正常的队列规则)
*一般队列->引出front,rear:n>m(m是入队列的元素个数),n是队列的容量,插入操作0(1)[末尾插入]
*删除某个元素,按线性表的逻辑(前驱后继关系),大量的数据移动(n/2)(O(n)),引入队头,队尾指针,不用移动
*接着有“假溢出的问题”(公交车有座问题),满空条件碰撞,引入循环队列
*设置flag|| 牺牲掉一个队列元素来实现,rear指向最后一个元素下标+1,front指向头元素的下标
*判满(rear+1)%QSIZE #正常的话就+1,但是会假溢出,所以就对QSIZE取模,有点空间复用
*所以就rear=(rear+1+QSIZE)%QSIZE //空间复用的实现,解决假溢出
*判满 ,(rear+1)%QSIZE==front,解决条件碰撞的问题
*循环队列->判空,判满
*假溢出指的是下标溢出,真溢出指的是空间溢出(QSIZE<要插入的元素个数),数据的覆盖
*队列长度=|rear-front|=(rear-front+QSIZE)%QSIZE
*链队->空间问题不需要考虑
*/
//循环队列的顺序存储结构:队列的基本操作
#include"stdio.h"
#define MAXSIZE 10
typedef int Elemtype;
typedef struct
{
Elemtype r[MAXSIZE];
int front;//队头指针
int rear;//指空(尾元素的下一个),front,rear递增式移动
}SqQueue;
void InitSqQueue(SqQueue *Q);//初始化空队列
void GetLength(SqQueue *Q,int length);//获取长度
void InsertElem(SqQueue *Q,int e);//涉及rear的变化Q->rear=(Q->rear+1+QSIZE)%QSIZE;
void DeleteElem(SqQueue *Q,int *e);//Q->front=(Q->front+1+QSIZE)%QSIZE;
//队列的链式存储结构,尾进头出,链队列,链队的特征是front指向头结点,rear指向尾节点
//空时均指向头结点
typedef int Elemtype;
typedef struct QNode
{
Elemtype data;
struct QNode * next;//链队元素的介绍
}QNode ,*QnodePtr;
typedef struct
{
QnodePtr front,rear;//链队的属性
}QLinkList;
//队列的链式存储结构,尾进头出,链队列,链队的特征是front指向头结点,rear指向尾节点
//空时均指向头结点
#include"stdio.h"
#include"malloc.h"
#define MAXSIZE 10
typedef int Elemtype;
typedef struct QNode
{
Elemtype data;
struct QNode * next;//链队元素的介绍
}QNode ,*QnodePtr;
typedef struct
{
QnodePtr front,rear;//链队的属性
}QLinkList;
int main();
void QueuePrint(QLinkList *Q);
void QueueInit(QLinkList *Q,Elemtype *a);
void InQueue(QLinkList *Q,Elemtype e);//队尾入队
int main()
{
QLinkList Q;
Elemtype a[MAXSIZE]={1,2,3,4,5,6,7,8,9,0};
QueueInit(&Q,a);
QueuePrint(&Q);
printf("\n");
InQueue(&Q,3);
QueuePrint(&Q);
}
void QueueInit(QLinkList *Q,Elemtype *a)
{
//设置头结点,这里没有传递二级指针的原因是修改的是Q的front,一级指针即可
Q->front=(QNode*)malloc(sizeof(QNode));
Q->front->next=NULL;
Q->rear=Q->front;
//各节点初始化
QnodePtr p;
int i;
p=Q->front;
for(i=1;i<=MAXSIZE;i++)
{
p->next=(QNode*)malloc(sizeof(QNode));
p=p->next;
p->data=a[i-1];
Q->rear=p;
}
//printf("%d ",p->data);
//QueuePrint(Q);
p->next=NULL;
//QueuePrint(Q);
}
void InQueue(QLinkList *Q,Elemtype e)//队尾插入元素
{
Q->rear->next=(QNode *)malloc(sizeof(QNode));//添加尾节点
Q->rear=Q->rear->next;//尾指针更新
Q->rear->data=e;//尾数据更新
Q->rear->next=NULL;//尾节点的指针域更新
//这里易需要自己验证
}
void QueuePrint(QLinkList *Q)
{
int j;
QNode *p;
//已起始和终结节点为分割距离
p=Q->front->next;
while(p)
{
printf("%d " ,p->data);
p=p->next;
}
}