大话数据结构 | 栈与队列

/*
 *栈先加后减 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;
}
}