数据结构：栈与队列的 5 种实现（顺序栈、链栈、顺序队、优先级队列）

1、顺序栈的设计

#include <stdio.h>

#define N 100

struct stack{
    int top;
    int data[N];
};

struct stack st={-1,{0}};

int isempty(){
    if(st.top==-1){
        return -1;
    }else{
        return 0;
    }
}

void setempty(){
    st.top=-1;
}

int push(int data){
    if(st.top+1<N){
        st.top+=1;
        st.data[st.top]=data;
        return 0;
    }else{
        return -1;
    }
}

int pop(int *data){
    if(isempty()==-1){
        return -1;
    }else{
        *data=st.data[st.top];
        st.top-=1;
        return 0;
    }
}

void TenToTwo(int n){
    if(n){
        TenToTwo(n/2);
        printf("%d",n%2);
    }
}

int main(){
    int num=100,i,res;
    TenToTwo(100);
    printf("\n");
    while(num){
        i=num%2;
        push(i); //压栈
        num/=2;
    }
    while(isempty()!=-1){
        pop(&res); //出栈
        printf("%d",res);
    }
    return 0;
}

2、尾部添加式的链式栈的设计（先进先出）

#include <stdio.h>
#include <stdlib.h>

struct StackNode{
    int id;
    int data;
    struct StackNode *pNext; //下一节点的地址
};

typedef struct StackNode Stn; //简化数据类型

Stn *push(Stn *head,int id,int data){ //压栈，从尾部添加
    Stn *pnew=(Stn *)malloc(sizeof(Stn));
    Stn *p;
    pnew->id=id;
    pnew->data=data;
    pnew->pNext=NULL;
    if(head==NULL){
        head=pnew;
    }else{
        p=head;
        while(p->pNext){
            p=p->pNext;
        }
        p->pNext=pnew;
    }
    return head;
}

Stn *pop(Stn *head,Stn *temp){ //出栈，读取头节点
    Stn *p=NULL;
    if(head==NULL){
        printf("不允许传入空指针\n ");
        return NULL;
    }else{
        *temp=*head; //赋值结构体变量
        p=head;
        head=head->pNext;
        free(p);
        return head;
    }
}

void freeall(Stn *head){ //释放所有节点
    Stn *p=head;
    if(head==NULL){
        return;
    }else{
        while(head->pNext){
            head=head->pNext;
            free(p);
            p=head;
        }
        free(p);
    }
}

int main(){
    Stn *head=NULL; //链式栈的头节点
    Stn temp={0,0,NULL}; //创建一个结构体变量，用于保存 pop 出来的数据
    head=push(head,1,10); //压栈
    head=push(head,2,20);
    head=push(head,3,30);
    head=push(head,4,40);
    head=push(head,5,50);
    head=push(head,6,60);
    head=pop(head,&temp); //出栈
    printf("id=%d,data=%d,pNext=%x\n",temp.id,temp.data,temp.pNext);
    while(head){
        head=pop(head,&temp);
        printf("id=%d,data=%d,pNext=%x\n",temp.id,temp.data,temp.pNext);
    }
    return 0;
}

3、头部添加式的链式栈的设计（后进先出）

#include <stdio.h>
#include <stdlib.h>

struct StackNode{
    int id;
    int data;
    struct StackNode *pNext;
};

typedef struct StackNode Stn;

Stn *push(Stn *head,int id,int data){ //压栈，从头部添加
    Stn *pnew=(Stn *)malloc(sizeof(Stn));
    pnew->id=id;
    pnew->data=data;
    pnew->pNext=NULL;
    if(head!=NULL){
        pnew->pNext=head;
    }
    head=pnew;
    return head;
}

Stn *pop(Stn *head,Stn *temp){ //出栈，读取头节点
    Stn *p=NULL;
    if(head==NULL){
        printf("不允许传入空指针\n ");
        return NULL;
    }else{
        *temp=*head;
        p=head;
        head=head->pNext;
        free(p);
        return head;
    }
}

void freeall(Stn *head){ //释放所有节点
    Stn *p=head;
    if(head==NULL){
        return;
    }else{
        while(head->pNext){
            head=head->pNext;
            free(p);
            p=head;
        }
        free(p);
    }
}

int main(){
    Stn *head=NULL;
    Stn temp={0,0,NULL};
    head=push(head,1,10);
    head=push(head,2,20);
    head=push(head,3,30);
    head=push(head,4,40);
    head=push(head,5,50);
    head=push(head,6,60);
    head=pop(head,&temp);
    printf("id=%d,data=%d,pNext=%x\n",temp.id,temp.data,temp.pNext);
    while(head){
        head=pop(head,&temp);
        printf("id=%d,data=%d,pNext=%x\n",temp.id,temp.data,temp.pNext);
    }
    return 0;
}

4、顺序队列的设计

#include <stdio.h>
#define N 100

struct queue{
    char data[N]; //存放数据的字符数组
    int front; //允许删除的一端称为队头
    int rear; //允许插入的一端称为队尾
};

typedef struct queue QU; //简化 struct queue

void initQU(QU *sq){ //用 sq 表示顺序队列
    sq->front=sq->rear=0; //队列初始化
}

int isempty(QU *sq){
    if(sq->front==sq->rear){ //队头与队尾重合，表明队列已空
        return -1;
    }else{
        return 0;
    }
}

char gethead(QU *sq){ //获取队列第一个元素
    if(sq->front==sq->rear)
        return -1;
    return sq->data[sq->front];
}

int inQU(QU *sq,char ch){ //队列入队
    if(sq->rear+1<=N-2){
        sq->data[sq->rear]=ch;
        sq->rear++;
        return 0; //返回 0，表示插入队元素成功
    }else{
        return -1; //返回 -1，表示插入队元素失败
    }
}

char outQU(QU *sq){ //队列出队
    if(sq->front==sq->rear)
        return -1;
    sq->front++;
    return sq->data[sq->front-1];
}

void showQU(QU *sq){ //打印所有队列元素，不允许修改 front 和 rear 的值
    int i;
    if(sq->front==sq->rear){
        return;
    }
    for(i=sq->front;i<=sq->rear;i++){
        printf("%c ",sq->data[i]);
    }
    printf("\n");
}

int main(){
    char *pstr="ABCDEDGHIJKL";
    char *p=pstr;
    QU sq1={{0},0,0}; //创建队列结构体，并初始化
    while(*p){
        inQU(&sq1,*p);
        showQU(&sq1);
        p++;
    }
    while(isempty(&sq1)!=-1){
        printf("%c ",outQU(&sq1));
    }
    return 0;
}

5、链表队列的设计

#include <stdio.h>
#include <stdlib.h>
#define N 100

struct queue{
    int data; //代表数据
    int high; //代表优先级
    struct queue *pNext; //下一节点的地址
};

typedef struct queue QU; ///简化 struct queue

void sort(QU *head);

QU *InQU(QU *head,int data,int high){ //入队，从尾部入队
    QU *pt=NULL;
    QU *pnew=(QU *)malloc(sizeof(QU));
    pnew->data=data;
    pnew->high=high;
    pnew->pNext=NULL;
    if(head==NULL){
        head=pnew;
    }else{
        pt=head;
        while(pt->pNext!=NULL){
            pt=pt->pNext;
        }
        pt->pNext=pnew;
    }
    sort(head); //排序
    return head;
}

void showall(QU *head){ ///打印队列所有成员
    QU *p=head;
    while(p!=NULL){
        printf("data=%d,high=%d,head=%p,pNext=%p\n",p->data,p->high,head,p->pNext);
        p=p->pNext;
    }
}

QU *OutQU(QU *head,QU *temp){ //出队，从头节点出队
    if(head==NULL){
        return NULL;
    }else{
        temp->data=head->data;
        temp->high=head->high;
        head=head->pNext;
        return head;
    }
}

void sort(QU *head){ //优先级排序，（冒泡排序法）
    QU *p1,*p2,temp;
    if(head==NULL || head->pNext==NULL){
        return;
    }else{
        for(p1=head;p1!=NULL;p1=p1->pNext){
            for(p2=p1->pNext;p2!=NULL;p2=p2->pNext){
                if(p1->high < p2->high){
                    temp.data=p1->data;temp.high=p1->high;
                    p1->data=p2->data;p1->high=p2->high;
                    p2->data=temp.data;p2->high=temp.high;
                }
            }
        }
    }
}

int main(){
    QU *head=NULL;
    QU temp={0,0,NULL}; ///定义一个临时结构体变量，并初始化
    head=InQU(head,10,1); //入队一个元素，并接收返回的头节点地址
    head=InQU(head,60,5);
    head=InQU(head,90,2);
    head=InQU(head,70,3);
    head=InQU(head,30,0);
    showall(head);
    printf("\n");
    while(head){
        head=OutQU(head,&temp); //出队一个元素，并接收返回的头节点地址
        printf("出队的元素：data=%d,high=%d\n",temp.data,temp.high);
        showall(head);
    }
    return 0;
}