체인 대기 열의 기본 조작

1. 대기 열의 개념 --- 한 끝 에 만 데 이 터 를 삽입 하고 다른 한 끝 에서 데 이 터 를 삭제 하 는 특수 선형 표 만 허용 합 니 다.
                            삽입 작업 을 하 는 한 끝 을 파티 끝 이 라 고 합 니 다 (대기 열 에 들 어 갑 니 다)
                            삭제 작업 을 진행 하 는 한 끝 을 파티 헤드 라 고 합 니 다 (대기 열 밖으로)
                            대기 열 은 선진 선 출 (FIFO) 의 특성 을 가지 고 있다.
2. 대열 의 성질 --- 대 미 삽입, 대 두 산 삭제
3. 대기 열 저장 구조
순서 대기 열 --- 팀 헤드 포인터 가 움 직 이지 않 고 대량의 요 소 를 옮 겨 야 합 니 다.
                      팀 헤드 포인터 이동, 가짜 넘 침 존재
가짜 넘 침: 순서 대기 열 은 여러 번 대기 열 에 들 어가 거나 대기 열 작업 을 한 후에 나타 나 는 저장 공간 이 있 지만 더 이상 대기 열 작업 을 할 수 없 는 넘 침 입 니 다. 순서 대기 열 최대 저장 공간 이 가득 차 있 고 대기 열 작업 을 요구 하 는 데 발생 하 는 넘 침 입 니 다.가짜 넘 침 을 해결 하 는 방법 은 순환 대기 열 입 니 다. 머리 와 끝 이 연결 되 는 순서 로 대기 열 을 저장 하 는 것 입 니 다.그러나 순환 대기 열 은 배열 이 넘 칠 수 있 는 문제 에 직면 하고 있 습 니 다. 그러면 순환 대기 열 은 대기 열 이 비어 있 고 꽉 찬 것 을 어떻게 판단 합 니까?

저장 소 를 하나 덜 사용 합 니 다

표지 판 설정

카운터 설정

 
//.h

​
​
#pragma once//          

#include
#include
#include
#include

typedef int DataType;
typedef struct Node
{
 DataType _data;//       
 struct Node* _pNext;//       
}Node,*pNode;
typedef struct Queue
{
 pNode _pHead;//       
 pNode _pTail;//       
}Queue;
void QueueInit(Queue* q);//      
pNode BuyNode(DataType data);//     
void QueuePush(Queue* q, DataType data);//   
void QueuePop(Queue* q);//   
DataType QueueFront(Queue* q);//     
DataType Queueback(Queue* q);//     
int QueueSize(Queue* q);//          
int QueueEmpty(Queue* q);//        

​

​

//Queue.c

​
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//      
void QueueInit(Queue* q)
{
 assert(q);
 q->_pHead = NULL;
 q->_pTail = NULL;
}
//     
pNode BuyNode(DataType data)
{
 pNode pNewNode = (pNode)malloc(sizeof(Node));
 if (NULL == pNewNode)
 {
  return NULL;
 }
 else
 {
  pNewNode->_data = data;
  pNewNode->_pNext = NULL;
 }
 return pNewNode;
}
//   （     ）
void QueuePush(Queue* q, DataType data)
{
 assert(q);
 pNode pNewNode = BuyNode(data);
 if (NULL == q->_pTail)//     ，           
 {
  q->_pHead = pNewNode;
  q->_pTail = pNewNode;
 }
 else
 {
  q->_pTail = q->_pTail->_pNext;
  q->_pTail = pNewNode;
 }
}
//void QueuePrint(Queue* q)//    
//{
// while (q->_pHead)
// {
//  printf("%d-->", q->_pHead->_data);
//  q->_pHead = q->_pHead->_pNext;
// }
// printf("NULL
");
//}
//   
void QueuePop(Queue* q)
{
 assert(q);
 if (NULL == q->_pHead)
 {
  return;
 }
 //    
 if (NULL == q->_pHead->_pNext)
 {
  q->_pHead = NULL;
  free(q->_pHead);
  return;
 }
 //    
 else
 {
  q->_pHead = q->_pHead->_pNext;
 }
 free(q->_pHead->_pNext);
 q->_pHead->_pNext = NULL;
}
//     
DataType QueueFront(Queue* q)
{
 assert(q);
 return q->_pHead->_data;
}
//     
DataType Queueback(Queue* q)
{
 assert(q);
 return q->_pTail->_data;
}
//          
int QueueSize(Queue* q)
{
 assert(q);
 int count = 0;
 while (q->_pHead)
 {
  count++;
  q->_pHead = q->_pHead->_pNext;
 }
 return count;
}
//        
int QueueEmpty(Queue* q)
{
 if (NULL == q)
 {
  return 0;
 }
 return 1;
}

​

//test.c

​
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void testQueuePush()
{
 Queue q;
 QueueInit(&q);
 QueuePush(&q, 1);
 QueuePush(&q, 2);
 QueuePush(&q, 3);
 QueuePush(&q, 4);
 QueuePush(&q, 5);
}
void testQueuePop()
{
 Queue q;
 QueueInit(&q);
 QueuePush(&q, 1);
 QueuePush(&q, 2);
 QueuePush(&q, 3);
 QueuePush(&q, 4);
 QueuePush(&q, 5);
 QueuePop(&q);
 QueuePop(&q);
}
void testQueue()
{
 Queue q;
 QueueInit(&q);
 QueuePush(&q, 1);
 QueuePush(&q, 2);
 QueuePush(&q, 3);
 QueuePush(&q, 4);
 QueuePush(&q, 5);
 printf("%d
", QueueFront(&q));//     
 printf("%d
", Queueback(&q));//     
 printf("%d
", QueueSize(&q));//          
 printf("%d
", QueueEmpty(&q));//        
}
int main()
{
 //testQueuePush();//   
 //testQueuePop();//   
 testQueue();

 system("pause");
 return 0;
}


​