数据结构体栈和队列的实现

前言：

        关于c语言的学习已经差不多更新完毕，如果发现个别知识点，我还会继续更新，但目前已经准备往c 和数据结构的重心挪动，这篇文章就是向大家讲述数据结构中栈和队列的实现。 

          你来人间一趟，你要看看太阳！！！！

目录

前言：

一、数据结构体栈 

1.1栈的概念及结构：

1.2栈的实现：

 1.2.1栈的定义：

1.2.2栈的初始化：     

1.2.3栈的销毁：

 1.2.4判断栈是否为空：

1.2.5栈的压栈（push）：

1.2.6栈的出栈（Pop）：

 1.2.7栈顶的元素查看：    

1.2.7栈的元素个数：     

1.3栈实现的全部代码： 

1.3.1  .c

1.3.2   .h

1.3.3   test

二、数据结构队列：

2.1数列的概念和结构：

2.2队列的实现：

 2.2.1队列的定义： 

2.2.2队列的初始化：   

 2.2.3队列的销毁：   

 2.2.4队列判断是否为空：   

 2.2.5队列插入（push）：   

 2.2.6队列出队（Pop）：   

2.2.7队头元素：   

2.2.8队尾元素：   

2.2.9队的人员个数： 

2.3队列实现的全部代码： 

2.3.1  .c

2.3.2  .h

2.3.3  test

3、总结：

---

一、数据结构体栈 

1.1栈的概念及结构：

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

 ～～～～记住一个原则，先进的后出，后进的先出。～～～～

1.2栈的实现：

              栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。我们保证首先插入的后面出来就行。

 1.2.1栈的定义：

1.  
   typedef int STDataType; //重定义int
2.  
   typedef struct Stack{
3.  
   STDataType* a;
4.  
   STDataType top; //栈顶
5.  
   STDataType capicity;
6.  
    
7.  
   }ST;

1.2.2栈的初始化：     

1.  
   void StackInit(ST*ps)
2.  
   {
3.  
   assert(ps);
4.  
   ps->a=NULL; //先指向空指针
5.  
   ps->top=ps->capicity=0; 初始化都为零
6.  
   }

1.2.3栈的销毁：

1.  
   void StackDestroy(ST*ps)
2.  
   {
3.  
   assert(ps); //断言一下防止空指针
4.  
   free(ps); //进行释放因为我申请的是动态内存
5.  
   ps=NULL;
6.  
   ps->top=0;
7.  
   ps->capicity=0;
8.  
   }

 1.2.4判断栈是否为空：

1.  
   bool StackEmpty(ST*ps)
2.  
   {
3.  
   assert(ps);
4.  
   return ps->top==0; //如果top等于0则证明栈为空，返回true
5.  
   }

1.2.5栈的压栈（push）：

1.  
   void StackPush(ST*ps,STDataType x)
2.  
   {
3.  
   assert(ps); //断言一下
4.  
   if(ps->top==ps->capicity) //如果top（栈顶）=capacity则证明容量已经满了需要扩容一下
5.  
   {
6.  
   int newcapicity=ps->capicity==0?4:(ps->capicity)*2; //和顺序表扩容一样
7.  
   STDataType* ptr = (STDataType*)realloc(ps->a, newcapicity*sizeof(STDataType)); //进行动态扩容
8.  
   if(ptr==NULL) //防止扩容失败
9.  
   {
10.  
    perror("StackPush");
11.  
    exit(-1);
12.  
    }
13.  
    ps->a=ptr; //把扩容成功的地址传给a
14.  
    ps->capicity=newcapicity; //把扩容后的新newcapicity给capacity
15.  
    }
16.  
    ps->a[ps->top]=x; // 插入元素x
17.  
    ps->top; //top进行
18.  
    }

1.2.6栈的出栈（Pop）：

1.  
   void StackPop(ST*ps)
2.  
   {
3.  
   assert(ps);
4.  
   assert(!StackEmpty(ps)); //这里判断是否为空栈如果为空栈就不能在进行出栈了
5.  
   --ps->top; //只需要让top减一个就行了
6.  
   }

 1.2.7栈顶的元素查看：    

1.  
   STDataType StackTop(ST* ps)
2.  
   {
3.  
   assert(ps);
4.  
   assert(!StackEmpty(ps));
5.  
    
6.  
   return ps->a[ps->top - 1]; //因为进行push后top 了一下，所以栈顶需要top-1
7.  
   }

1.2.7栈的元素个数：     

1.  
   int StackSize(ST* ps)
2.  
   {
3.  
   assert(ps);
4.  
    
5.  
   return ps->top;
6.  
   }

栈还是比较容易实现的，如果熟练掌握顺序表我相信大家还是很容易就能把栈写出来。

1.3栈实现的全部代码： 

1.3.1  .c

1.  
   #include "Stack.hpp"
2.  
   void StackInit(ST*ps)
3.  
   {
4.  
   assert(ps);
5.  
   ps->a=NULL;
6.  
   ps->top=ps->capicity=0;
7.  
   }
8.  
   void StackDestroy(ST*ps)
9.  
   {
10.  
    assert(ps);
11.  
    free(ps);
12.  
    ps=NULL;
13.  
    ps->top=0;
14.  
    ps->capicity=0;
15.  
    }
16.  
    void StackPush(ST*ps,STDataType x)
17.  
    {
18.  
    assert(ps);
19.  
     
20.  
     
21.  
    if(ps->top==ps->capicity)
22.  
    {
23.  
    int newcapicity=ps->capicity==0?4:(ps->capicity)*2;
24.  
    STDataType* ptr = (STDataType*)realloc(ps->a, newcapicity*sizeof(STDataType));
25.  
    if(ptr==NULL)
26.  
    {
27.  
    perror("StackPush");
28.  
    exit(-1);
29.  
    }
30.  
    ps->a=ptr;
31.  
    ps->capicity=newcapicity;
32.  
    }
33.  
    ps->a[ps->top]=x;
34.  
    ps->top;
35.  
    }
36.  
    bool StackEmpty(ST*ps)
37.  
    {
38.  
    assert(ps);
39.  
    return ps->top==0;
40.  
    }
41.  
    void StackPop(ST*ps)
42.  
    {
43.  
    assert(ps);
44.  
    assert(!StackEmpty(ps));
45.  
    --ps->top;
46.  
    }
47.  
    STDataType StackTop(ST* ps)
48.  
    {
49.  
    assert(ps);
50.  
    assert(!StackEmpty(ps));
51.  
     
52.  
    return ps->a[ps->top - 1];
53.  
    }
54.  
    int StackSize(ST* ps)
55.  
    {
56.  
    assert(ps);
57.  
     
58.  
    return ps->top;
59.  
    }

1.3.2   .h

1.  
   #ifndef Stack_hpp
2.  
   #define Stack_hpp
3.  
    
4.  
   #include <stdio.h>
5.  
   #include<assert.h>
6.  
   #include<stdbool.h>
7.  
   #include<stdlib.h>
8.  
   typedef int STDataType;
9.  
   typedef struct Stack{
10.  
    STDataType* a;
11.  
    STDataType top;
12.  
    STDataType capicity;
13.  
     
14.  
    }ST;
15.  
    void StackInit(ST*ps);
16.  
    void StackDestroy(ST*ps);
17.  
    void StackPush(ST*ps,STDataType x);
18.  
    void StackPop(ST*ps);
19.  
    bool StackEmpty(ST*ps);
20.  
    STDataType StackTop(ST* ps);
21.  
    int StackSize(ST* ps);
22.  
     
23.  
    #endif /* Stack_hpp */

1.3.3   test

测试我这里是随便测试了一下，大家可以自己进行不同的测试就行不必和我一样

1.  
   #include "Stack.hpp"
2.  
   void TestStack()
3.  
   {
4.  
   ST st;
5.  
   StackInit(&st);
6.  
   StackPush(&st, 1);
7.  
   StackPush(&st, 2);
8.  
   StackPush(&st, 3);
9.  
   printf("%d ", StackTop(&st));
10.  
    printf("%d ",StackSize(&st));
11.  
    StackPop(&st);
12.  
    //printf("%d ", StackTop(&st));
13.  
    StackPop(&st);
14.  
     
15.  
    StackPush(&st, 4);
16.  
    StackPush(&st, 5);
17.  
     
18.  
    while (!StackEmpty(&st))
19.  
    {
20.  
    printf("%d ", StackTop(&st));
21.  
    StackPop(&st);
22.  
    }
23.  
    printf("\n");
24.  
    }
25.  
     
26.  
    int main()
27.  
    {
28.  
    TestStack();
29.  
    return 0;
30.  
    }

二、数据结构队列：

2.1数列的概念和结构：

        队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。  队列和栈的区别就是先进的后出，就和排队买东西一样，先排队的先买，说白了就是先到先得。

2.2队列的实现：

        队列要用到头删，因为第一个进入的要第一个删除，这样用数组就不太合适，因为数组的头删是0(n),时间复杂度比较大，这里我们用链表就是比较合适的选择。

 2.2.1队列的定义： 

1.  
   typedef int QDataType;
2.  
   typedef struct QueueNode
3.  
   {
4.  
   struct QueueNode*next;
5.  
   QDataType data;
6.  
   }QNode;
7.  
   typedef struct Queue
8.  
   {
9.  
   QNode* head; //队列要有一个头
10.  
    QNode* rear; //队列要有一个尾
11.  
    int size;
12.  
    }Queue;

2.2.2队列的初始化：   

1.  
   void QueueInit(Queue*pq)
2.  
   {
3.  
   assert(pq); //断言防止传入空指针
4.  
   pq->head=NULL;
5.  
   pq->rear=NULL;
6.  
   pq->size=0;
7.  
   }

 2.2.3队列的销毁：   

1.  
   void QueueDestroy(Queue*pq)
2.  
   {
3.  
   assert(pq);
4.  
   QNode *cur=pq->head; //定一个节点进行遍历一个个销毁
5.  
   while(cur)
6.  
   {
7.  
   QNode *del=cur;
8.  
   free(cur);
9.  
   cur=del->next;
10.  
    }
11.  
    pq->head=NULL;
12.  
    pq->rear=NULL;
13.  
    }

 2.2.4队列判断是否为空：   

1.  
   bool QueueEmpty(Queue* pq)
2.  
   {
3.  
   assert(pq);
4.  
   return pq->head == NULL && pq->rear == NULL;
5.  
   }

 2.2.5队列插入（push）：   

1.  
   void QueuePush(Queue* pq, QDataType x)
2.  
   {
3.  
   assert(pq);
4.  
   QNode*newnode=(QNode*)malloc(sizeof(QNode)); //插入前先创建一个节点
5.  
   if(newnode==NULL) //这是判断是否申请成功
6.  
   {
7.  
   perror("newnode");
8.  
   exit(-1);
9.  
   }
10.  
    else
11.  
    {
12.  
    newnode->data=x;
13.  
    newnode->next=NULL;
14.  
    }
15.  
    if(pq->rear==NULL) //两种情况这是尾节点位空的时候
16.  
    {
17.  
    pq->rear=pq->head=newnode;
18.  
    }
19.  
    else //这是尾节点不为空的时候
20.  
    {
21.  
    pq->rear->next=newnode;
22.  
    pq->rear=newnode;
23.  
    }
24.  
    pq->size ;
25.  
    }

 2.2.6队列出队（Pop）：   

1.  
   void QueuePop(Queue* pq)
2.  
   {
3.  
   assert(pq);
4.  
   assert(!QueueEmpty(pq)); //判断队列是否为空
5.  
   if(pq->head->next==NULL) //如果只有一个头节点情况
6.  
   {
7.  
   free(pq->head);
8.  
   pq->head=pq->rear=NULL;
9.  
   }
10.  
    else //不止只有头节点的情况
11.  
    {
12.  
    QNode* del;
13.  
    del=pq->head;
14.  
    pq->head=pq->head->next;
15.  
    free(del);
16.  
    del=NULL;
17.  
    }
18.  
    pq->size--;
19.  
    }

2.2.7队头元素：   

1.  
   QDataType QueueFront(Queue* pq)
2.  
   {
3.  
   assert(pq);
4.  
   assert(!QueueEmpty(pq));
5.  
    
6.  
   return pq->head->data;
7.  
   }

2.2.8队尾元素：   

1.  
   QDataType QueueBack(Queue* pq)
2.  
   {
3.  
   assert(pq);
4.  
   assert(!QueueEmpty(pq));
5.  
   return pq->rear->data;
6.  
   }

2.2.9队的人员个数： 

1.  
   int QueueSize(Queue* pq)
2.  
   {
3.  
   assert(pq);
4.  
   return pq->size;
5.  
   }

2.3队列实现的全部代码： 

2.3.1  .c

1.  
   #include"Queue.h"
2.  
   void QueueInit(Queue*pq)
3.  
   {
4.  
   assert(pq);
5.  
   pq->head=NULL;
6.  
   pq->rear=NULL;
7.  
   pq->size=0;
8.  
   }
9.  
   void QueueDestroy(Queue*pq)
10.  
    {
11.  
    assert(pq);
12.  
     
13.  
    QNode *cur=pq->head;
14.  
    while(cur)
15.  
    {
16.  
    QNode *del=cur;
17.  
    free(cur);
18.  
    cur=del->next;
19.  
    }
20.  
    pq->head=NULL;
21.  
    pq->rear=NULL;
22.  
    }
23.  
    void QueuePush(Queue* pq, QDataType x)
24.  
    {
25.  
    assert(pq);
26.  
    QNode*newnode=(QNode*)malloc(sizeof(QNode));
27.  
    if(newnode==NULL)
28.  
    {
29.  
    perror("newnode");
30.  
    exit(-1);
31.  
    }
32.  
    else
33.  
    {
34.  
    newnode->data=x;
35.  
    newnode->next=NULL;
36.  
    }
37.  
    if(pq->rear==NULL)
38.  
    {
39.  
    pq->rear=pq->head=newnode;
40.  
    }
41.  
    else
42.  
    {
43.  
    pq->rear->next=newnode;
44.  
    pq->rear=newnode;
45.  
    }
46.  
    pq->size ;
47.  
    }
48.  
    void QueuePop(Queue* pq)
49.  
    {
50.  
    assert(pq);
51.  
    assert(!QueueEmpty(pq));
52.  
    if(pq->head->next==NULL)
53.  
    {
54.  
    free(pq->head);
55.  
    pq->head=pq->rear=NULL;
56.  
    }
57.  
    else{
58.  
    QNode* del;
59.  
    del=pq->head;
60.  
    pq->head=pq->head->next;
61.  
    free(del);
62.  
    del=NULL;
63.  
    }
64.  
    pq->size--;
65.  
    }
66.  
    bool QueueEmpty(Queue* pq)
67.  
    {
68.  
    assert(pq);
69.  
    return pq->head == NULL && pq->rear == NULL;
70.  
    }
71.  
    QDataType QueueFront(Queue* pq)
72.  
    {
73.  
    assert(pq);
74.  
    assert(!QueueEmpty(pq));
75.  
     
76.  
    return pq->head->data;
77.  
    }
78.  
     
79.  
    QDataType QueueBack(Queue* pq)
80.  
    {
81.  
    assert(pq);
82.  
    assert(!QueueEmpty(pq));
83.  
    return pq->rear->data;
84.  
    }
85.  
    int QueueSize(Queue* pq)
86.  
    {
87.  
    assert(pq);
88.  
    return pq->size;
89.  
    }

2.3.2  .h

1.  
    
2.  
   #ifndef Queue_h
3.  
   #define Queue_h
4.  
    
5.  
   #include <stdio.h>
6.  
   #include<stdlib.h>
7.  
   #include<stdbool.h>
8.  
   #include<assert.h>
9.  
   typedef int QDataType;
10.  
    typedef struct QueueNode
11.  
    {
12.  
    struct QueueNode*next;
13.  
    QDataType data;
14.  
    }QNode;
15.  
    typedef struct Queue
16.  
    {
17.  
    QNode* head;
18.  
    QNode* rear;
19.  
    int size;
20.  
    }Queue;
21.  
    void QueueInit(Queue*pq);
22.  
    void QueueDestroy(Queue*pq);
23.  
    void QueuePush(Queue* pq, QDataType x);
24.  
    void QueuePop(Queue* pq);
25.  
    bool QueueEmpty(Queue* pq);
26.  
    QDataType QueueFront(Queue* pq);
27.  
    QDataType QueueBack(Queue* pq);
28.  
    int QueueSize(Queue* pq);
29.  
     
30.  
     
31.  
     
32.  
    #endif /* Queue_h */

2.3.3  test

1.  
   #include"Queue.h"
2.  
   void test()
3.  
   {
4.  
   Queue q;
5.  
   QueuePush(&q,1);
6.  
   QueuePush(&q,2);
7.  
   QueuePush(&q,3);
8.  
   QueuePush(&q,4);
9.  
   QueuePush(&q,5);
10.  
    printf("%d \n",QueueSize(&q));
11.  
    printf("%d ",QueueFront(&q));
12.  
    QueuePop(&q);
13.  
    printf("%d ",QueueFront(&q));
14.  
    QueuePop(&q);
15.  
    printf("%d ",QueueFront(&q));
16.  
    printf("%d ",QueueBack(&q));
17.  
     
18.  
    QueueDestroy(&q);
19.  
     
20.  
    }
21.  
    int main()
22.  
    {
23.  
    test();
24.  
    return 0;
25.  
    }

3、总结：

        关于栈和队列是数据结构中比较重要的一点，这篇博客我把栈和队列的实现全部写出来了，同时最后有他全部的代码，但我的建议是大家可以尝试一下自己去完成栈和队列的代码实现，在实现过程中也就是我们的学习过程！！！！！！！

 最后小马码文不易，如果觉得有帮助就多多支持哈！！！^ _ ^

这篇好文章是转载于：学新通技术网