数据结构05

0x00 什么是队列

具有一定操作约束的线性表

插入在一端，删除在另一端

数据插入入队列（ADDQ）

数据删除出队列（DELETEQ）

先进先出 FIFO

队列的抽象数据结构描述

TIM截图20200202181716

0x01 队列的顺序存储结构实现

此种方式中为了尽量利用数组空间，会循环使用，当头部前面空了，尾部满了，会往前面插入。

typedef int Position;
struct QNode {
    ElementType *Data;     /* 存储元素的数组 */
    Position Front, Rear;  /* 队列的头、尾指针 */
    int MaxSize;           /* 队列最大容量 */
};
typedef struct QNode *Queue;
 
Queue CreateQueue( int MaxSize )
{
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    Q->Front = Q->Rear = 0;
    Q->MaxSize = MaxSize;
    return Q;
}
 
bool IsFull( Queue Q )
{
    return ((Q->Rear+1)%Q->MaxSize == Q->Front);
}
 
bool AddQ( Queue Q, ElementType X )
{
    if ( IsFull(Q) ) {
        printf("队列满");
        return false;
    }
    else {
        Q->Front=X;
        Q->Front=(Q->Front+1)%Q->MaxSize;
        return true;
    }
}
 
bool IsEmpty( Queue Q )
{
    return (Q->Front == Q->Rear);
}
 
ElementType DeleteQ( Queue Q )
{
    ElementType ret=NULL;
    if ( IsEmpty(Q) ) { 
        printf("队列空");
        return ERROR;
    }
    else  {
        ret=Q->Data[Q->Rear];
        Q->Rear=(Q->Rear+1)%MaxSize;
        return ret;
    }
}

0x02 队列的链式储存实现

typedef struct Node *PtrToNode;
struct Node { /* 队列中的结点 */
    ElementType Data;
    PtrToNode Next;
};
typedef PtrToNode Position;
 
struct QNode {
    Position Front, Rear;  /* 队列的头、尾指针 */
    int MaxSize;           /* 队列最大容量 */
    int length;
};
typedef struct QNode *Queue;
Queue createQueue(int MaxSize){
    Queue ret=(Queue)malloc(sizeof(struct Qnode));
    ret->MaxSize=MaxSize;
    ret->Front=NULL;
    ret->Rear=NULL;
    ret->length=0;
    return ret;
}
bool IsEmpty( Queue Q )
{
    return (Q->length==0);
}
bool IsFull(Queue Q){
    return (Q->length==Q->MaxSize);
}
int AddQ(Queue Q,ElementType value){
    if(IsFull(Q)){
        return -1;
    }else{
        Position p=(Position)malloc(sizeof(struct node));
        p->Data=value;
        p->Next=NULL;
        if(Q->Rear==NULL){//Front Rear both are NULL
            Q->Rear=p;
            Q->Front=p;
        }else{
            Q->Rear->Next=p;
            Q->Rear=Q->Rear->Next
        }
        Q->length++;
        return 0;
    }
}
ElementType DeleteQ( Queue Q )
{
    Position FrontCell; 
    ElementType FrontElem;
     
    if  ( IsEmpty(Q) ) {
        printf("队列空");
        return ERROR;
    }
    else {
        FrontCell = Q->Front;
        if ( Q->Front == Q->Rear ) /* 若队列只有一个元素 */
            Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */
        else                     
            Q->Front = Q->Front->Next;
        FrontElem = FrontCell->Data;
 
        free( FrontCell );  /* 释放被删除结点空间  */
        Q->length--;
        return  FrontElem;
    }
}

0x03 两个堆栈实现队列

注意 malloc和free的地址必须相同，不能一次malloc一大块，而只free一部分，必须free所有malloc的。

#include <stdio.h>
#include <stdlib.h>
#define Elementtype int
typedef struct Stack{
	Elementtype* data;
	int maxsize;
	int top;
}stack;
stack* createStack(int maxsize){
	stack* s=(stack*)malloc(sizeof(stack));
	s->data=(Elementtype*)malloc(sizeof(Elementtype)*maxsize);
	s->maxsize=maxsize;
	s->top=-1;
	return s;
}
int isEmpty(stack* s){
	int ret=0;
	if(s->top==-1) ret=1;	
	return ret;
}
int isFull(stack* s){
	int ret=0;
	if(s->top==s->maxsize-1) ret=1;
	return ret;
}
int push(stack* s,Elementtype x){
	int ret=0;
	if(isFull(s)){
		ret=1;
	}else{
		s->data[++(s->top)]=x;
	}
	return ret;
}
Elementtype pop(stack* s){
	Elementtype ret;
	if(isEmpty(s)){
	
	}else{
		ret=s->data[s->top--];
	}
	return ret;
}
int add(stack*a,stack*b,Elementtype x){
    if(isFull(a)) return -1;
	else{
        int ret;
        ret=push(a,x);
	    return ret;
    }
}
Elementtype del(stack*a,stack*b){
	Elementtype ret;
	if(isEmpty(b)){
		while(a->top!=-1){
			push(b,pop(a));
		}
		ret=pop(b);//这里有bug，如果栈s1 s2均为空，那么将没有返回值
	}else{
		ret=pop(b);	
	}
	return ret;
	
}
int main(void){
	Elementtype a;
	stack*s1=createStack(10);
	stack*s2=createStack(10);
	add(s1,s2,10);
	add(s1,s2,5);
	a=del(s1,s2);
	printf("%d ",a);
	return 0;
}