栈 stack

• 受限线性表
• 先进后出 FILO

题外话：

堆和栈是内存区域的问题，栈和队列是数据结构的问题，两者没有任何关系。

堆和栈的区别

• 申请空间的方式和回收不一样。

  • 堆区的空间要向系统申请，malloc和new，必须要自己主动释放才能够回收，否则会内存泄漏。
  • 栈只要定义就会自动分配空间，回收也不用管，系统会自动回收。

• 生命周期不同

  • 栈的生命周期就在定义的大括号里面。
  • 堆的生命周期从申请空间到释放的范围。
  • 所以一般情况下，如果需要返回一块空间的话，一般选择堆区而不会返回栈区，因为栈区会被回收掉。

• 分配效率不同

  • 栈区是连续的空间，可以连续遍历来得到，速度也快。
  • 堆区是利用的不连续的离散的空间，（底层实现类似于链表），所以如果要用的时候需要遍历啥的，效率相对较低。

• 生长方向不同

  • 堆区的空间申请时是从小到大生长的
  • 栈区的空间申请时是从大到小生长的

• 内存碎片问题

  • 堆区会产生内存碎片
  • 栈区不会产生

• 存储内容问题

  • 堆区放的内容基本是数据和地址（变量地址和空间地址），堆区没有变量的概念，只有被别的变量所指向
  • 栈区放的内容可以放变量和函数的入口地址

静态变量tips

• 只能定义一次，且在其作用域内保持其值，除非重新给它赋值

• 只在定义内的文件有效，全局变量才可以跨文件使用

跨文件使用tips：关键字extern

• 定义一个数组，我们知道可以用指针接着，但跨文件引用的时候千万不可以把原有的数组在跨文件的时候引用成指针，只能声明成数组。
• 在局部范围内可以使用全局变量，比如一个函数内定义一个局部变量i，然后外面有全局变量i，那么函数内的使用i的时候使用的是函数内的局部变量i，如果想要使用外面的全局变量i，那就需要用extern
• 三个使用：
  • extern C ：以C的标准来编译C++的代码
  • 局部范围内引用全局的变量
  • 跨文件引用

• 数组方式来实现栈 其弊端在于容量问题 （容量不够则需要用一个新的大容量栈来存 链式没有这个问题）

• 链式方式来实现栈 其实就相当于链表的头添加头删除 所以会倒序

  • C语言实现链式栈

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node{
            
        int nvalue;
        struct node *pNext;
    }ListStack;
    
    void Push(ListStack **pTop,int nvalue){
            
        //新元素申请空间
        ListStack *pTemp = NULL;
        pTemp = (ListStack*) malloc(sizeof(ListStack));
        pTemp->nvalue = nvalue;
        pTemp->pNext = NULL;
    
        //头增加
        pTemp->pNext = *pTop;
        *pTop = pTemp;
    }
    
    int Pop(ListStack **pTop){
            
        if (*pTop == NULL) {
            
            printf("stack is empty~\n");
            exit(1);    //结束所在进程
        }
    
        //标记
        ListStack *pDel = *pTop;
        int nNum = pDel->nvalue;
    
        //头弹出
        *pTop = (*pTop)->pNext;
        free(pDel);
        pDel = NULL;
        return nNum;
    }
    
    int main()
    {
            
        ListStack *pTop = NULL;
        Push(&pTop, 1);
        Push(&pTop, 2);
        Push(&pTop, 3);
        Push(&pTop, 4);
    
        printf("%d\n",Pop(&pTop));
        printf("%d\n",Pop(&pTop));
        printf("%d\n",Pop(&pTop));
        printf("%d\n",Pop(&pTop));
    
        return 0;
    }
    

• 栈的八大基本函数

  • Init
  • Push
  • Pop
  • Clear
  • Destroy
  • GetCount
  • GetTop
  • IsEmpty

  //	实现栈的八大基本函数（C语言）
  
  #include <stdio.h>
  #include <stdlib.h>
  
  typedef struct node{
        
      int nvalue;
      struct node *pNext;
  }Date;
  
  typedef struct stack{
        
      int nConut;
      Date *pTop;
  }Stack;
  
  void Init(Stack **pStack){
        
      *pStack = (Stack*)malloc(sizeof(Stack));
      (*pStack)->nConut = 0;
      (*pStack)->pTop = NULL;
  }
  
  void Push(Stack *pStack,int nNum){
        
      if (pStack == NULL) {
        
          printf("stack is not exist!\n");
          exit(1);
      }
  
      Date *pTemp = NULL;
      pTemp = (Date*)malloc(sizeof(Date));
      pTemp->nvalue = nNum;
  
      pTemp->pNext = pStack->pTop;
      pStack->pTop = pTemp;
      pStack->nConut++;
  }
  
  int Pop(Stack *pStack){
        
      if (pStack == NULL) {
        
          printf("stack is not exist!\n");
          exit(1);
      }
  
      if (pStack->nConut == 0)    
          return -1;
  
      Date *pDel = NULL;
      pDel = pStack->pTop;
      int nNum = pDel->nvalue;
  
      pStack->pTop = pStack->pTop->pNext;
      free(pDel);
      pStack->nConut--;
      return nNum;
  }
  
  void Clear(Stack *pStack){
        
      if (pStack == NULL || pStack->nConut == 0)
          return;
  
      while (pStack->nConut != 0) {
        
          Pop(pStack);
      }
  }
  
  void Destory(Stack **pStack){
        
      Clear(*pStack);
      free(*pStack);
      *pStack = NULL;
  }
  
  int GetTop(Stack *pStack){
        
      if (pStack == NULL || pStack->nConut == 0) {
        
          printf("stack is not exist or stack is empty!\n");
          exit(1);
      }
      return pStack->pTop->nvalue;
  }
  
  int GetCount(Stack *pStack){
        
      if (pStack == NULL) {
        
          printf("stack is not exist!\n");
          exit(1);
      }
      return pStack->nConut;
  }
  
  int IsEmpty(Stack *pStack){
        
      if (pStack == NULL) {
        
          printf("stack is not exist!\n");
          exit(1);
      }
      return pStack->nConut == 0 ? 1 : 0; //三目运算符
          // 0 ? 1 : 0
          //如果是0(空)则返回true(1)，否则返回false(0)
  }
  
  int main()
  {
        
      Stack *pStack = NULL;
  
      Init(&pStack);
      Push(pStack, 1);
      Push(pStack, 2);
      Push(pStack, 3);
      Push(pStack, 4);
  
      printf("%d\n",GetCount(pStack));
      printf("%d\n",GetTop(pStack)); 
  
      printf("%d\n",Pop(pStack));
      printf("%d\n",Pop(pStack));
      printf("%d\n",Pop(pStack));
      printf("%d\n",Pop(pStack));
  
      printf("%d\n",IsEmpty(pStack));
      Destory(&pStack);
      Push(pStack, 100);
  
      return 0;
  }
  

  题外话：

  指针传递

  • 分析：

  • void fun(char *q){
             
        q = (char*)malloc(100);
    }
    
    int main(){
             
        char *p = NULL;
        fun(p);
        strcpy(p,"haha");
    }
    

  • 

  • typedef struct S{
             
        char *p;
    }ss;
    
    void fun(S *a){
             
        a->p = malloc(100);
    }
    
    int main(){
             
        S *b = malloc(s);
        fun(b);
        strcpy(b->p,"haha");
    }
    

  • 

    PS：也可以理解成，a作为一个指针，p是a中的一个指针，那么a->p相当于指针的指针（二重指针，也就类似于上面的地址传递 **p的形式）

  • 总结：值传递（形参修改改不了实参）；地址传递（形参修改可以改变实参）。但如果遇到封装的情况，看原封装的指针变量有没有空间，如果有的话，值传递也可以进行空间里内容的修改。

队列 queue

• 先进先出 FIFO

• 尾添加 头删除

• 队列元素的出列是在队头，即下标为0的位置，那也就意味着，队列中的所有元素都得向前移动，以保证队列的队头（也就是下标为0的位置）不为空，此时的时间复杂度为0(n)。

  可有时想想，为什么出队列时一定要全部移动呢，如果不去限制队列的元素必须存储在数组的前n个单元这一条件，出队的性能就会大大增加。也就是说，队头不需要一定在下标为0的位置，比如也可以是a[1]等。

  而为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列。

  对于普通队列来说，最好的方法是使用链表实现，因为对于数组来说，队列可能会出现下面这种情况：

  • 假设是长度为5的数组，初始状态，空队列如所示，front与 rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4, front指针依然指向下标为0位置，而rear指针指向下标为4的位置。
    

  出队a1、a2，则front指针指向下标为2的位置，rear不变，如下图所示，再入队a5，此时front指针不变，rear指针移动到数组之外。
  

  问题还不止于此。假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做假溢出。

  此时，不可以继续添加元素，否则会造成数组越界而遭致程序出错。然而此时又不应该扩充数组，因为还有大量实际空间未被占用。此时我们应该如何解决这个问题呢？循环队列可以解决这个问题。解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。也就是利用循环来解决空间浪费问题。

• 队列类型：

  • 单端队列：

    （数组可以实现，但空间受限严重，所以采用链式来实现，尾添加头删除）

    • C语言实现单端队列的几个基础函数

      #include <cstdlib>
      #include <stdio.h>
      #include <stdlib.h>
      
      typedef struct date{
                
          int nValue;
          struct date *pNext;
      }Date;
      
      typedef struct queue{
                
          int nCount;
          Date *pHead;
          Date *pTail;
      }ListQueue;
      
      void Init(ListQueue **pListQueue){
                
          *pListQueue = (ListQueue*)malloc(sizeof(ListQueue));
          (*pListQueue)->nCount = 0;
          (*pListQueue)->pHead = NULL;
          (*pListQueue)->pTail = NULL;
      }
      
      void Push(ListQueue *pListQueue,int nNum){
                
          if (pListQueue == NULL) {
                
              printf("queue is not exist.\n");
              exit(1);
          }
          Date *pTemp = NULL;
          pTemp = (Date*)malloc(sizeof(Date));
          pTemp->nValue = nNum;
          pTemp->pNext = NULL;
      
          if (pListQueue->pHead == NULL) {
                
              pListQueue->pHead = pTemp;
          }else {
                
              pListQueue->pTail->pNext = pTemp;
          }
          pListQueue->pTail = pTemp;
          pListQueue->nCount++;
      }
      
      int Pop(ListQueue * pListQueue){
                
          if (pListQueue == NULL) {
                
              printf("queue is not exist.\n");
              exit(1);
          }
          if (pListQueue->nCount == 0)
              return -1;
          //标记
          Date *pDel = pListQueue->pHead;
          int nNum = pDel->nValue;
          //移动
          pListQueue->pHead = pListQueue->pHead->pNext;
          free(pDel);
          pDel = NULL;
          pListQueue->nCount--;
      
          if (pListQueue->nCount == 0) {
                
              pListQueue->pTail = NULL;
          }
      
          return nNum;
      }
      
      int IsEmpty(ListQueue *pListQueue){
                
          if (pListQueue == NULL) {
                
              printf("queue is not exist.\n");
              exit(1);
          }
          return pListQueue->nCount == 0? 1: 0;
      }
      
      int main()
      {
                
          ListQueue *pListQueue = NULL;
          Init(&pListQueue);
      
          Push(pListQueue, 1);
          Push(pListQueue, 2);
          Push(pListQueue, 3);
          Push(pListQueue, 4);
          printf("%d\n",IsEmpty(pListQueue));
      
          printf("%d\n",Pop(pListQueue));
          printf("%d\n",Pop(pListQueue));
          printf("%d\n",Pop(pListQueue));
          printf("%d\n",Pop(pListQueue));
          printf("%d\n",IsEmpty(pListQueue));
      
          return 0;
      }
      

  • 双端队列

  • 优先级队列：（后面再学~）

  • 循环队列：

    （用数组实现，从尾到头的时候用 r+1%n ，解决假溢出的问题）

    • r+1%n？

    • 首先假设数组长度n=5，r=0表示数据在第一格啦，如此类推r=5的时候数组放满了，r再往下加的话就要变成6了，而6是在数组外了，要放在数组的第1格才对，6 ÷ 5 = 1 余 1，这个余数就是这个数据要放的位置的下标，也就是第一格，r再往下加就是7了，7 ÷ 5 = 1 余 2，这个数据就要放在数组的第二格，也就是r%n。但因为数组的索引是从0开始算，而数组的大小n是从1开始算的，所以r要先加1再对5取余数，也就是r+1%n。

    • 循环队列如何判断队列为空or为满？

      • 当队列空时，条件就是from = rear,当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。 如下图所示，我们就认为此队列已经满了。

        

        由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为QueueSize，那么队列满的条件是(rear+1) %QueueSize == front (取模“%的目的就是为了整合rear与front大小为一个问题)。

        比如上面这个例子， QueueSize = 5，当 front=0，而 rear=4, (4+1) %5 = 0，所以此时队列满。再比如，front = 2而rear =1。(1 + 1) %5 = 2，所以此时 队列也是满的。而对于下图, front = 2而rear= 0, (0+1) %5 = 1，1!=2,所以此时队列并没有满。

        

        另外，当rear > front时，此时队列的长度为rear—front。但当rear < front时，队列长度分为两段，一段是QueueSize-front，另一段是0 + rear，加在一起，队列长度为rear-front + QueueSize，因此通用的计算队列长度公式为：(rear—front + QueueSize) % QueueSize

      • 总结：

        • 队空条件：front == rear
        • 队满条件：(rear+1) %QueueSize == front
        • 队列长度：(rear—front + QueueSize) % QueueSize

      • 循环队列中各个参数的含义：

      （1）队列初始化时，front和rear值都为零；

      （2）当队列不为空时，front指向队列的第一个元素，rear指向队列最后一个元素的下一个位置；

      （3）当队列为空时，front与rear的值相等，但不一定为零；

      • 其他判断队列空or满的方法：

        （1）设置一个标志变量flag，当front == rear且flag = 0时为队列空，当front == rear且flag= 1时为队列满。

        （2）可以用一个变量index来计数，如果index=n则为满，index=0则为空，此时r不需要指向后一个元素。

栈和队列 相关题目

括号匹配问题

一万个括号 判断是否完全匹配？

• 方案：

• ① 利用栈

  遍历一万个括号，左括号就入栈，遇到一个右括号就将一个左括号出栈，如果右括号没有对应的左括号可以出栈，则匹配失败，如果全部遍历完后栈内还有左括号剩余，也匹配失败。只有过程中没有失败，结束后也没剩余，则匹配成功。

• ② 计数器（时间消耗和栈一样，思路和栈一样，但没申请新的空间，空间消耗低，所以该方案比较好）

  碰到左括号+1，碰到右括号-1，如果出现负数就失败，如果操作完成后其值不为0，也失败，只有过程中不出现负数且结束后为0，则成功。

  #include <stdio.h>
  #include <string.h>
  
  int BracketsMatch(const char *strBrackets){
        
      if (strBrackets == NULL)    //空 没有括号 所以不匹配
          return 0;
      
      int i = 0;
      int nCount = 0;
  
      while (i < strlen(strBrackets)) {
        
          //计 ( 的数量
          if (strBrackets[i] == '(') {
        
              nCount++;
          }else if (strBrackets[i] == ')'){
        
              //遇到 )与左括号进行匹配 抵消一个
              nCount--;
              //左括号少于右括号 匹配不成功
              if (nCount < 0) {
        
                  return 0;
              }
          } 
          //遍历下一个括号
          i++;
      }
      //左括号数量是否多于右括号
      return nCount > 0 ? 0 : 1;  
                  //如果大于0则不匹配(0)，否则匹配(1)
  }
  
  int main()
  {
        
      int nResult = BracketsMatch("()()()((()))");
      printf("%d\n",nResult);
      return 0;
  }
  

约瑟夫环问题

约瑟夫环

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。例如，1、2、3、4、5这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是3、1、5、2，因此最后剩下的数字是4。

方案：

• ① 循环链表

  遍历，利用计数器判断是否为第m个，是的话把第m个节点删掉，然后计数器置为0重新开始计数，重复该过程，直到循环链表里只剩下一个数字。

• ② 队列

  先全部入队，然后一个个出队并用计数器判断是否为第m个数字，如果不是则出队后再入队，如果是的话则删除，注意计数器到m后需要清0然后重新计数，如此反复直到队列中只剩下一个数字。

  #include <stdio.h>
  #include <stdlib.h>
  
  typedef struct date{
        
      int nValue;
      struct date *pNext;
  }Date;
  
  typedef struct queue{
        
      int nCount;
      Date *pHead;
      Date *pTail;
  }ListQueue;
  
  void Init(ListQueue **pListQueue){
        
      *pListQueue = (ListQueue*)malloc(sizeof(ListQueue));
      (*pListQueue)->nCount = 0;
      (*pListQueue)->pHead = NULL;
      (*pListQueue)->pTail = NULL;
  }
  
  void Push(ListQueue *pListQueue,int nNum){
        
      if (pListQueue == NULL) {
        
          printf("queue is not exist.\n");
          exit(1);
      }
      Date *pTemp = NULL;
      pTemp = (Date*)malloc(sizeof(Date));
      pTemp->nValue = nNum;
      pTemp->pNext = NULL;
  
      if (pListQueue->pHead == NULL) {
        
          pListQueue->pHead = pTemp;
      }else {
        
          pListQueue->pTail->pNext = pTemp;
      }
      pListQueue->pTail = pTemp;
      pListQueue->nCount++;
  }
  
  int Pop(ListQueue * pListQueue){
        
      if (pListQueue == NULL) {
        
          printf("queue is not exist.\n");
          exit(1);
      }
      if (pListQueue->nCount == 0)
          return -1;
      //标记
      Date *pDel = pListQueue->pHead;
      int nNum = pDel->nValue;
      //移动
      pListQueue->pHead = pListQueue->pHead->pNext;
      free(pDel);
      pDel = NULL;
      pListQueue->nCount--;
  
      if (pListQueue->nCount == 0) {
        
          pListQueue->pTail = NULL;
      }
      return nNum;
  }
  
  int JosephRing(int n,int k){
        
      //辅助队列
      ListQueue * pQueue = NULL;
      Init(&pQueue);
  
      //计数器
      int nCount = 0;
  
      //入队
      int i = 1;
      while (i <= n) {
        
          Push(pQueue, i);
          i++;
      }
  
      //出环
      while (pQueue->nCount > 1) {
        
          //弹出 计数
          i = Pop(pQueue);
          nCount++;
          //是否满足出环条件
          //满足则计数器置为0，无需重新入队 
          if (nCount == k) {
        
              nCount = 0;
              continue;
          }else {
         //不满足，元素重新入队
              Push(pQueue, i);
          }
      }
      i = Pop(pQueue);
      return i;
  }
  
  int main()
  {
        
      int nResult = JosephRing(5, 3);
      printf("%d\n",nResult);
      return 0;
  } 
  

• ③ 数组

  两个计数器，一个用于计是否为第m个，另一个看数组内剩余的没有处理的个数，第m个数置-1，循环遍历，直到整个数组只有一个数没有被处理。

队列和栈的相互转换

如何用两个栈实现队列的先进先出功能？

• S1 输入栈；S2 输出栈

• 如果入栈，那么判断S2是否有元素存在，如果有，把S2的先依次放入S1，然后再将新元素放入S1

• 如果出栈，那么判断S1是否有元素存在，如果有，把S1的先依次放入S2，然后再将S2的元素出栈

• #include <stdio.h>
  #include <stdlib.h>
  
  typedef struct node{
        
      int nvalue;
      struct node *pNext;
  }Date;
  
  typedef struct stack{
        
      int nConut;
      Date *pTop;
  }Stack;
  
  typedef struct queue{
        
      Stack *pStack1;
      Stack *pStack2;
  }Queue;
  
  void Init(Stack **pStack){
        
      *pStack = (Stack*)malloc(sizeof(Stack));
      (*pStack)->nConut = 0;
      (*pStack)->pTop = NULL;
  }
  
  void Push(Stack *pStack,int nNum){
        
      if (pStack == NULL) {
        
          printf("stack is not exist!\n");
          exit(1);
      }
  
      Date *pTemp = NULL;
      pTemp = (Date*)malloc(sizeof(Date));
      pTemp->nvalue = nNum;
  
      pTemp->pNext = pStack->pTop;
      pStack->pTop = pTemp;
      pStack->nConut++;
  }
  
  int Pop(Stack *pStack){
        
      if (pStack == NULL) {
        
          printf("stack is not exist!\n");
          exit(1);
      }
  
      if (pStack->nConut == 0)    
          return -1;
  
      Date *pDel = NULL;
      pDel = pStack->pTop;
      int nNum = pDel->nvalue;
  
      pStack->pTop = pStack->pTop->pNext;
      free(pDel);
      pStack->nConut--;
      return nNum;
  }
  
  int IsEmpty(Stack *pStack){
        
      if (pStack == NULL) {
        
          printf("stack is not exist!\n");
          exit(1);
      }
      return pStack->nConut == 0 ? 1 : 0; 
  }
  
  void q_Init(Queue **pQueue){
        
      *pQueue = (Queue*)malloc(sizeof(Queue));
      Init(&(*pQueue)->pStack1);
      Init(&(*pQueue)->pStack2);
  }
  
  void q_Push(Queue *pQueue,int nNum){
        
      //栈1入队
      //考虑栈2是否非空   如果非空，将栈2元素压入栈1
      while (!IsEmpty(pQueue->pStack2)) {
        
          Push(pQueue->pStack1,Pop(pQueue->pStack2));
      }
      //新元素入栈1
      Push(pQueue->pStack1,nNum);
  }
  
  int q_Pop(Queue *pQueue){
        
      //栈2出队
      //考虑栈1是否非空   如果非空，将栈1元素依次放入栈2
      while (!IsEmpty(pQueue->pStack1)) {
        
          Push(pQueue->pStack2,Pop(pQueue->pStack1));
      }
      //将栈2栈顶元素弹出
      int nNum = Pop(pQueue->pStack2);
      return nNum;
  }
  
  int main(){
        
      Queue *pQueue = NULL;
      q_Init(&pQueue);
  
      q_Push(pQueue, 1);
      q_Push(pQueue, 2);
      q_Push(pQueue, 3);
      q_Push(pQueue, 4);
  
      printf("%d\n",q_Pop(pQueue));
      printf("%d\n",q_Pop(pQueue));
      q_Push(pQueue, 5);
      q_Push(pQueue, 6);
      printf("%d\n",q_Pop(pQueue));
      printf("%d\n",q_Pop(pQueue));
      printf("%d\n",q_Pop(pQueue));
      printf("%d\n",q_Pop(pQueue));
  
      return 0;
  }
  

如何用两个队列实现栈的先进后出功能？

• 比如有两个队列 q1 和 q2 ，将 1 2 3 4 放入队列 q1，我们希望得到 4 3 2 1 的出队情况（类似于栈的先进后出），因此先将1 2 3出队放入q2中，然后把q1中的4出队，再将1 2出队放入q1中，然后再把q2中的3出队，由此类推循环，得到4 3 2 1
• 中途入队时，注意先完成当次操作，然后将元素入到有元素的队列中，让所有元素在一个队列中，否则会乱。

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

typedef struct node{
    
    int nvalue;
    struct node *pNext;
}Date;

typedef struct stack{
    
    int nConut;
    Date *pTop;
}Stack;

typedef struct queue{
    
    Stack *pStack1;
    Stack *pStack2;
}Queue;

void Init(Stack **pStack){
    
    *pStack = (Stack*)malloc(sizeof(Stack));
    (*pStack)->nConut = 0;
    (*pStack)->pTop = NULL;
}

void Push(Stack *pStack,int nNum){
    
    if (pStack == NULL) {
    
        printf("stack is not exist!\n");
        exit(1);
    }

    Date *pTemp = NULL;
    pTemp = (Date*)malloc(sizeof(Date));
    pTemp->nvalue = nNum;

    pTemp->pNext = pStack->pTop;
    pStack->pTop = pTemp;
    pStack->nConut++;
}

int Pop(Stack *pStack){
    
    if (pStack == NULL) {
    
        printf("stack is not exist!\n");
        exit(1);
    }

    if (pStack->nConut == 0)    
        return -1;

    Date *pDel = NULL;
    pDel = pStack->pTop;
    int nNum = pDel->nvalue;

    pStack->pTop = pStack->pTop->pNext;
    free(pDel);
    pStack->nConut--;
    return nNum;
}

int IsEmpty(Stack *pStack){
    
    if (pStack == NULL) {
    
        printf("stack is not exist!\n");
        exit(1);
    }
    return pStack->nConut == 0 ? 1 : 0; 
}

void q_Init(Queue **pQueue){
    
    *pQueue = (Queue*)malloc(sizeof(Queue));
    Init(&(*pQueue)->pStack1);
    Init(&(*pQueue)->pStack2);
}

void q_Push(Queue *pQueue,int nNum){
    
    //栈1入队
    //考虑栈2是否非空   如果非空，将栈2元素压入栈1
    while (!IsEmpty(pQueue->pStack2)) {
    
        Push(pQueue->pStack1,Pop(pQueue->pStack2));
    }
    //新元素入栈1
    Push(pQueue->pStack1,nNum);
}

int q_Pop(Queue *pQueue){
    
    //栈2出队
    //考虑栈1是否非空   如果非空，将栈1元素依次放入栈2
    while (!IsEmpty(pQueue->pStack1)) {
    
        Push(pQueue->pStack2,Pop(pQueue->pStack1));
    }
    //将栈2栈顶元素弹出
    int nNum = Pop(pQueue->pStack2);
    return nNum;
}

int main(){
    
    Queue *pQueue = NULL;
    q_Init(&pQueue);

    q_Push(pQueue, 1);
    q_Push(pQueue, 2);
    q_Push(pQueue, 3);
    q_Push(pQueue, 4);

    printf("%d\n",q_Pop(pQueue));
    printf("%d\n",q_Pop(pQueue));
    q_Push(pQueue, 5);
    q_Push(pQueue, 6);
    printf("%d\n",q_Pop(pQueue));
    printf("%d\n",q_Pop(pQueue));
    printf("%d\n",q_Pop(pQueue));
    printf("%d\n",q_Pop(pQueue));

    return 0;
}

如何找到链表的倒数第k个节点

方法一：暴力

• 遍历链表获得当前表的长度n

• 正数的n-k个就是倒数的第k个

• 注意：比较n和k的大小关系，是否k>n

方法二：双指针

• 1指针先走k步，注意检测有没有结束（k是不是超出了n）
• 12指针同步一起走，先走的1指针走到尾的时候，后出发的2指针就走到k的位置了