【三支火把】---队列和栈的C程序实现

这几天总结了C语言的队列，栈的实现方法，在此总结一下：
一、栈
首先从栈开始，诚然，相信学习过数据结构的你，肯定应该知道栈是什么东西了，如果不知道也没事每一句话我就可以帮你总结--数据
只在栈顶进行插入和删除操作，数据进出栈符合先进后出或者后进先出的原则。来贴个图片，你就知道了。

                                                                      

　　再也没有比上述图片更能贴切的描述栈了，数据结构中的栈和程序运行压栈的栈还略有区别，在此先不说那么多，继续回归正题。栈的应用很多，你最可能会用到的一个就是10进制转换2进制数了，具体怎么应用，请亲爱的你动手试试哦！
接下来我就介绍栈的几种实现方法：
1.固定栈
　　固定栈是最简单的一种了，要点就2个，一是注意栈满，二是注意要符合先进后出的原则。在这两点的基础上，就可以自己动手写一个栈空间实现
程序，这里我就介绍那么多了，因为这个实在是太简单了，代码中我也都作了详细地说明。

# include "stdio.h" 
# include "stdlib.h"

# define MAX_STACK_SIZE 100 //定义栈空间的最大存储内存 
# define ERROR 1 //错误标志 
# define OK 0 

typedef struct sqstack{ //封装一个结构体，包括定义的栈存储数组，栈顶和栈底标志 
    int stack_array[MAX_STACK_SIZE];
    int top;
    int bottom;
}SqStack;

SqStack SqStack_Init(void) //初始化一个栈内存 
{
    static SqStack S;
    S.top = S.bottom = 0;
    return S;
}

int Push_Stack(SqStack *S) //压栈操作 
{
    int ele; 
    if(S->top == MAX_STACK_SIZE-1)
    {
        return ERROR;
    } 
    scanf("%d",&ele);
    S->stack_array[S->top] = ele;
    S->top+=1;
    return OK;
}

int Pop_Stack(SqStack *S) //出栈操作 
{
    if(S->top != 0)
    S->top--;    
    printf("%d ",S->stack_array[S->top]);
}

int main(void)
{
    int ele;
    int i = 0;
    SqStack MyStack = SqStack_Init();
    while(1)
    {
        system("cls");
        printf("***************静态栈空间模拟实现*******************\n") ; 
        printf("请输入元素！(元素进栈)");
        for(i=0;i<3;i++) //压三次栈 
        Push_Stack(&MyStack);
        printf("元素出栈\n");
        for(i=0;i<3;i++) //出三次栈
        Pop_Stack(&MyStack);
        system("pause")    ;
    }
return 0;
       

 

2.动态链栈
这是完全采用链表的形式实现一个栈空间，稍微有点麻烦，你可以选择该栈没有上限，只要你一直输就一直开辟栈空间，
并且进行数据存储，不过这显然是不符合实际的，所以我加了个stack_size变量，为该栈设置了上限，具体的代码如下：

# include"stdio.h"
# include "stdlib.h"

# define Stack_Size 5 

typedef struct stack{
    int ele;
    int stack_size;
    struct stack *next;
}Stack,* Pstack;    

//动态链栈的实现，每个节点可以存储一个栈点元素， 因此首先需要一个数据区，然后就是一个指针区，首先是一个链表，其次才是一个栈
//且应该定义一个top和bottom指针，来指向栈底，和栈顶，这样才能辅助来进行完成链栈的实现。 

Pstack Top;
Pstack Bottom; 

void Creat_StackNode(void)    //创建一个栈底。并且定义这个栈底不允许释放。 
{    
    Top = (Pstack)malloc(sizeof(Stack));
    Bottom = Top;
    scanf("%d",&Top->ele);   //写入栈底元素 
    Top->stack_size=0;        
    Top->next = NULL;
    printf("栈底建立成功\n"); 
}

void PushStack(void)
{
    Pstack pnew = (Pstack)malloc(sizeof(Stack));
    pnew->next = Top;   //新建一个节点，指针指向前一个节点，其实这就是在连接一个链表，然后再让Top指向新建的节点。 
    scanf("%d",&pnew->ele);
    pnew->stack_size=Top->stack_size + 1; 
    Top = pnew;    
}

void PopStack(void)
{
    Pstack ptemp = Top->next;      //这个其实跟链表的删除一样，因为你要释放掉这个节点，所以必须提前保存该节点的下一个指向，然后才能释放带该节点 
    printf("%d\n",Top->ele);      //将节点元素打印出来。 
    free(Top);                    //释放节点空间，也就是出栈， 
    Top = ptemp;                  //再将top指针指向新的栈顶 。 
}

int main(void)
{
    int sel;
    int i = 0;
    printf("创建链栈的头节点！"); 
    Creat_StackNode();   //这个是链栈的最底部空间，不允许释放。 
    while(1)
    {    
        printf("请选择是压栈还是出栈！(1.入   2.出)");
        scanf("%d",&sel);
        if(sel == 1)
        {
            if(Top->stack_size > Stack_Size-1)
                printf("栈内存已满了！") ; 
            else
                PushStack();   //将数据压入链栈         
        }     
        else if(sel == 2)
        {
            if(Top->stack_size == 0)
            {
                printf("%d\n",Top->ele);
                printf("已经到达栈底,禁止继续弹出数据!    ") ;          
            }
            else
                PopStack();        //将数据弹出栈                 
        } 
        else
        {
            printf("选择输入错误，请重新输入：");
            fflush(stdin) ;
        }
    }
    return 0;
}

 

二、队列
队列和栈是近似的，也是一种存储空间吧，不过它的存储与栈刚好相反，符合先进先出的原则。队列的首尾成为队首和队尾
元素在队尾实现入队，在队首实现出队，详情请看下图--形象的比喻：水从水管的一端进入，另一端出去。。

　　　　　　　　　  　　　

队列的实现有以下三种，
1.静态队列
　　类似上述静态栈的构建，不过这种的入队和出队都是向一个方向进行，在有限的空间内很容易造成空间的浪费因此用途并不广泛，再次我也就不举例了，太简单了。

2.静态循环队列
　　这就是 一个很好的队列实现方式了，使用循环的方式，能够节省空间，因此，使用较为广泛，实现起来也略微有点麻烦，首先来看下循环队列的结构示意图，或许你会更理解：

　　　　　　　　　　　　　　

 

具体的代码如下，供参考，代码中也有了十分详细的注释：

# include "stdio.h"
 
# define QUEUE_SIZE 5

typedef struct  queue{
    int queue_array[QUEUE_SIZE];
    int front;
    int rear;
}Queue,*Pqueue; 
//由于队列无论是入队还是出队都是只能像一个方向增长的操作，因此单向静态队列的用途不是很大， 同场有用的是静态循环队列和动态队列。
//该部分介绍一个静态循环队列。
//静态循环队列，是一个将队头和队尾链接在一起的队列，队列空间能够循环使用，因此空间利用率高，使用比较广泛
 
Pqueue Init_Queue(void)      //初始化一个队列 
{
    static Queue queue;
    queue.front  = 0;
    queue.rear = 0;
    return &queue;
}

/*接下来就是插入都列，和出队列了，这两个操作其实并不难，唯一的难点就在于临界状态的判断，有两个临界状态， 第一个就是队首不动，空间插入满，队尾追上了队首 
另外一个难点就是出队列队首追上了队尾，表示队尾已经空。因此确定了两个判断条件是  (rear+1)%size ==  front.表示队列满了，如果，(front)%size == front
则表示队列已经空了，并且这其中，默认rear所指向向的空间一直为空*/ 
void InputQueue(Pqueue MyQueue)
{
    if((MyQueue->rear+1)%QUEUE_SIZE == MyQueue->front)  //这一步骤的运算可以称得上是神来之笔 
    {
        printf("队列已满，不允许插入！\n"); 
        return;
    }
    else
    {
        scanf("%d",&MyQueue->queue_array[MyQueue->rear]);
        MyQueue->rear = (MyQueue->rear+1)%QUEUE_SIZE;
        printf("插入成功！\n"); 
    } 
}

void OutPutQueue(Pqueue MyQueue)
{
    if(MyQueue->front==MyQueue->rear)
    {
        printf("队列已空，请勿继续进行删除操作！\n"); 
        return;
    }
    else
    {
        printf("%d\n",MyQueue->queue_array[MyQueue->front]);
        MyQueue->front = (MyQueue->front+1)%QUEUE_SIZE;
        printf("删除成功！\n"); 
    }
}

int main(void)
{
    int i = 0;
    int sel;
    Pqueue MyQueue; MyQueue = Init_Queue();
    while(1)
    {
        system("cls"); 
        printf("请输入选择: 1.插入  2.删除!!!   ");
        scanf("%d",&sel);
        
        if(sel ==1)
        {
            InputQueue(MyQueue);
            sel = 0;
        }        
        else if(sel == 2)
        {
            OutPutQueue(MyQueue);
            sel = 0;            
        }
        system("pause");
    } 
    return 0;
} 

 

3.链式队列

　　队列的实现同样可以使用链的方式来构建完成，一旦牵扯到链，那么队列也就非常灵活了,不多啰嗦，直接看代码。

 

# include "stdio.h"
# include "stdlib.h"

typedef struct queue{ //封装一个队列节点的结构体
    int ele;
    struct queue *next;
}Dqueue,*Pqueue;

Pqueue Rear; //定义队首指针和队尾指针。
Pqueue Front;

void Init_Queue(void) //初始化队的开始，该部分空间不允许释放，否则会丢失队列的指针。
{ 
    Pqueue phead = (Pqueue)malloc(sizeof(Dqueue));
    phead->next = NULL;
    printf("请输入第一个队列元素："); 
    scanf("%d",&phead->ele);
    Rear = phead; //开始时队首指针和队尾指针都指向该节点。
    Front = phead;
    printf("构建成功！\n"); 
}

void Input_Queue(void) //入队操作。
{
    Pqueue pnew = (Pqueue)malloc(sizeof(Dqueue));
    if(pnew == NULL)
        printf("空间申请失败");
    else
    {    
        scanf("%d",&pnew->ele); 
        pnew->next = NULL; //入队操作时一个在头结点前插入的操作，对于新申请的堆空间必须要设置其指针域和数据域，缺一不可。
        Rear->next = pnew; /*该步十分关键，！！！为何这么说，它指定了新创建的前一个节点的指向是新建的节点，也就确定一条由下向上的的
        链式指向，因为这一步，Bottom指针才能一次向*问节点，进行出队操作。*/
        Rear = pnew;    //使队尾指针指向最末尾节点。
        printf("入队成功\n"); 
    }
}

void Output(void) //出队操作
{
    Pqueue ptemp;
    if(Front == Rear) //这就是队空标志，只允许弹出这个节点元素，不允许改变指针指向和释放改空间，否则队列指针将没有指向，还得重新构建
    { 
        printf("%d",Front->ele);
        printf("队列已经空，请禁止继续出队\n"); 
    }
    else
    {
        ptemp = Front->next; //同时这也是一个释放链式节点的操作，先让暂存指针保存，释放节点的指向， 
        printf("%d",Front->ele); //然后打印出释放节点的节点数值
        free(Front); //释放该节点
        Front = ptemp; //然后重新保存暂存指针，这样队首指针就向上移动一个节点。
        printf("出队成功\n"); 
    }
}

int main(void)
{
    int sel;
    Init_Queue(); 
    
    while(1)
    {
        printf("请选择入队还是出队！1.入队 2.出队: "); 
        scanf("%d",&sel);
        if(sel == 1)
        {
            Input_Queue();
            sel = 0;
        }
        else if(sel == 2)
        {
            Output();
            sel = 0;
        } 
    }
    return 0;
} 

 

 

 

　　至此，栈和队列已经总结完毕，其实说难也不难，只是刚学的你，可能会稍微有点绕，希望能帮到诸位！