devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

重生之“我打数据结构，真的假的？”--3.栈和队列

作者：从前慢现在也慢 | 2024-07-27 23:11:11

赞

踩

重生之“我打数据结构，真的假的？”--3.栈和队列

1.栈和队列的基本概念

1.1 栈

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

1.2 初始化及功能实现

  1. #include"stack.h"
  2.  
  3. typedef int datatype;
  4. typedef struct stack
  5. {
  6. 	datatype* a;
  7. 	int top;
  8. 	int capacity;
  9. }ST;
  10.  
  11. void InitST(ST* sl)
  12. {
  13. 	assert(sl);                  //sl不为NULL
  14. 	sl->a = NULL;
  15. 	sl->top = 0;
  16. 	sl->capacity = 0;
  17. }//初始化
  18.  
  19. void STpush(ST* sl, int data)
  20. {
  21. 	assert(sl);
  22. 	if (sl->top == sl->capacity)
  23. 	{
  24. 		int newcapacity = sl->capacity == 0 ? 2 : sl->capacity * 2;
  25. 		datatype* tmp = (datatype*)realloc(sl->a, newcapacity * sizeof(datatype));
  26. 		sl->a = tmp;
  27. 		sl->capacity = newcapacity;
  28. 	}
  29. 	sl->a[sl->top] = data;
  30. 	sl->top++;
  31. }//插入
  32. void STpop(ST* sl)
  33. {
  34. 	assert(sl);                //！！！！！！判断指针是否为空，《《《《判断的是栈是否存在》》》》》》          
  35. 	assert(!STempty(sl));      //！！！！！！！！！与上文不同，《《《《判断的是栈是否为空》》》》》》
  36. 		sl->top--;
  37. }//删除
  38.  
  39. datatype STtop(ST* sl)
  40. {
  41. 	assert(sl);
  42. 	assert(!STempty(sl));
  43. 	return sl->a[sl->top-1];
  44. }//取栈顶
  45.  
  46. void STdestroy(ST* sl)
  47. {
  48. 	assert(sl);
  49. 	free(sl->a);
  50. 	sl->a = NULL;
  51. 	sl->top = sl->capacity = 0;
  52. }
  53.  
  54. bool STempty(ST* sl)
  55. {
  56. 	assert(sl);
  57. 	return sl->top == 0;
  58. }

1.3 括号匹配问题

. - 力扣（LeetCode）

思路：

1.设立一个栈，依次从s中取出元素，如果为左括号类型 则入栈

2.否则取栈顶元素（如果栈为空则直接返回false）如果匹配

则删除栈顶元素，如果不匹配，返回false

3.s访问完后，如果栈为空，则返回true，否则返回false

  1. bool isValid(char* s) {
  2.  
  3. typedef struct stack
  4. {
  5. 	char * a;
  6. 	int top;
  7. 	int capacity;
  8. }ST;
  9.  
  10. bool STempty(ST* sl)
  11. {
  12. 	assert(sl);
  13. 	return sl->top == 0;
  14. }
  15. void InitST(ST* sl)
  16. {
  17. 	assert(sl);                  //sl不为NULL
  18. 	sl->a = NULL;
  19. 	sl->top = 0;
  20. 	sl->capacity = 0;
  21. }
  22.  
  23. void STpush(ST* sl, char data)
  24. {
  25. 	assert(sl);
  26. 	if (sl->top == sl->capacity)
  27. 	{
  28. 		int newcapacity = sl->capacity == 0 ? 2 : sl->capacity * 2;
  29. 		char* tmp = (char*)realloc(sl->a, newcapacity * sizeof(char));
  30. 		sl->a = tmp;
  31. 		sl->capacity = newcapacity;
  32. 	}
  33. 	sl->a[sl->top] = data;
  34. 	sl->top++;
  35. }
  36. void STpop(ST* sl)
  37. {
  38. 	assert(sl);                //！！！！！！判断指针是否为空，《《《《判断的是栈是否存在》》》》》》          
  39. 	assert(!STempty(sl));      //！！！！！！！！！与上文不同，《《《《判断的是栈是否为空》》》》》》
  40. 		sl->top--;
  41. }
  42.  
  43. char STtop(ST* sl)
  44. {
  45. 	assert(sl);
  46. 	assert(!STempty(sl));
  47. 	return sl->a[sl->top-1];
  48. }
  49.  
  50. void STdestroy(ST* sl)
  51. {
  52. 	assert(sl);
  53. 	free(sl->a);
  54. 	sl->a = NULL;
  55. 	sl->top = sl->capacity = 0;
  56. }
  57.  
  58.     int i=0;
  59.     char j;
  60.     char k;
  61.     ST L;
  62.     ST R;
  63.     InitST(&L);
  64.     InitST(&R);
  65.     while(s[i]!='\0')
  66.     {
  67.      if(s[i]=='('||s[i]=='['||s[i]=='{')
  68.     {
  69.         STpush(&L, s[i]);
  70.         i++;
  71.     }
  72.      else
  73.      {
  74.        if(STempty(&L))
  75.        return false;
  76.       if((STtop(&L)=='('&&s[i]==')')||(STtop(&L)=='{'&&s[i]=='}')||(STtop(&L)=='['&&s[i]==']'))
  77.        {
  78.         STpop(&L);
  79.         i++;
  80.        }
  81.       else
  82.       return false;
  83.      }
  84.     }
  85.    if(STempty(&L))
  86.    return true;
  87.    else
  88.    return false;
  89.  
  90. }

2.队列 

2.1 概念

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素

2.2 初始化及功能实现

  1. typedef int datatype;
  2. typedef struct Queuenode
  3. {
  4. 	datatype data;
  5. 	struct Queuenode * next;
  6. }Qnode;
  7.  
  8. typedef struct QT
  9. {
  10. 	Qnode* head;
  11. 	Qnode* tail;
  12. 	int size;
  13. }QT;
  14.  
  15.  
  16. void QueueInit(QT* sl)
  17. {
  18. 	assert(sl);
  19. 	sl->head = NULL;
  20. 	sl->tail = NULL;
  21. 	sl->size = 0;
  22. }
  23.  
  24. bool Queueempty(QT* sl)
  25. {
  26. 	assert(sl);
  27. 	return sl->head ==NULL;
  28. }
  29.  
  30. void Queuepush(QT* sl, int x)
  31. {
  32. 	assert(sl);
  33. 	Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
  34. 	newnode->next = NULL;
  35. 	newnode->data = x;
  36. 	if (Queueempty(sl))
  37. 	{
  38. 		sl->head = newnode;
  39. 		sl->tail = newnode;
  40. 	}
  41. 	else
  42. 	{
  43. 		sl->tail->next = newnode;
  44. 		sl->tail = newnode;
  45. 	}
  46. 	sl->size++;
  47. }
  48.  
  49. void Queuepop(QT* sl)
  50. {
  51. 	assert(sl);
  52. 	assert(!Queueempty(sl));
  53. 	Qnode* next = sl->head->next;
  54. 	free(sl->head);
  55. 	sl->head = next;
  56. 	sl->size--;
  57. }
  58.  
  59. int Queuetop(QT* sl)
  60. {
  61. 	assert(sl);
  62. 	assert(!Queueempty(sl));
  63. 	return sl->head->data;
  64. }
  65.  
  66.  
  67. void Queuedestroy(QT* sl)
  68. {
  69. 	assert(sl);
  70. 	while (!Queueempty(sl))
  71. 		Queuepop(sl);
  72. 	sl->head = sl->tail = NULL;
  73. 	sl->size = 0;
  74. }

2.3 循环队列 

. - 力扣（LeetCode）

  1. typedef struct Queuenode
  2. {
  3. 	int data;
  4. 	struct Queuenode * next;
  5. }Qnode;
  6.  
  7. typedef struct {
  8. Qnode* head;
  9. Qnode* tail;
  10. int size;
  11. int flag;
  12. } MyCircularQueue;
  13.  
  14. MyCircularQueue* myCircularQueueCreate(int k) {
  15.      MyCircularQueue* sl=NULL;
  16.      sl=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  17.      sl->head = NULL;
  18.      sl->tail = NULL;
  19.      sl->size = 0;
  20.      sl->flag = k;
  21.      return sl;
  22. }
  23.  
  24. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  25.     return obj->head ==NULL;
  26. }
  27.  
  28. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  29.     if(obj->size>=obj->flag)
  30.     return false;
  31.     Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
  32.     newnode->next = NULL;
  33.     newnode->data = value;
  34.     if(myCircularQueueIsEmpty(obj))
  35.     {
  36. 	obj->head = newnode;
  37. 	obj->tail = newnode;
  38.     obj->tail->next=obj->head;
  39.     obj->head->next=obj->tail;
  40.     }
  41.    else
  42.    { 
  43. 	obj->tail->next = newnode;
  44. 	obj->tail = newnode;
  45.     if(obj->head->next==obj->head)
  46.     obj->head->next=obj->tail;
  47.     obj->tail->next=obj->head;
  48.     }
  49. obj->size++;
  50. return true;
  51.  
  52. }
  53.  
  54. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  55.     
  56.   if(myCircularQueueIsEmpty(obj))
  57.   return false;
  58.   else{
  59.    if(obj->head!=obj->tail)
  60.    {
  61.      Qnode* next = obj->head->next;
  62.      obj->tail->next=next;
  63.     free(obj->head);
  64.     obj->head = next;
  65.     obj->size--;
  66.    }
  67.    else{
  68.     free(obj->head);
  69.      obj->head = obj->tail = NULL;
  70.      obj->size = 0;
  71.    }
  72.   }
  73.   return true;
  74. }
  75.  
  76. int myCircularQueueFront(MyCircularQueue* obj) {
  77.     int i=0;
  78.     if(myCircularQueueIsEmpty(obj))
  79.     return -1;
  80.     else
  81.     return obj->head->data;
  82. }
  83.  
  84. int myCircularQueueRear(MyCircularQueue* obj) {
  85.     if(myCircularQueueIsEmpty(obj))
  86.     return -1;
  87.     else
  88.     return obj->tail->data;
  89. }
  90.  
  91. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  92.     return obj->size==obj->flag;
  93. }
  94.  
  95. void myCircularQueueFree(MyCircularQueue* obj) {
  96.    
  97.     while (!myCircularQueueIsEmpty(obj))
  98. 	{
  99.      Qnode* next = obj->head->next;
  100.      obj->tail->next=next;
  101.      if(obj->head!=obj->tail)
  102.      { free(obj->head);
  103.       obj->head = next;
  104.       obj->size--;
  105.      }
  106.      else{
  107.         obj->head = obj->tail = NULL;
  108.         obj->size = 0;
  109.         break;
  110.      }
  111.     }
  112.     
  113. }

3.用栈实现队列 

 . - 力扣（LeetCode）

 思路：

1.可以设立两个栈 p，q

（1）入队：将p中元素依次入栈q，再将函数传递的数据入栈q

（2）出队：将q中元素依次入栈p，再取q栈顶元素

  1. typedef struct stack
  2. {
  3. 	int * a;
  4. 	int top;
  5. 	int capacity;
  6. }ST;
  7.  
  8. typedef struct {
  9. ST* p;
  10. ST* q;
  11. } MyQueue;
  12.  
  13.  
  14. MyQueue* myQueueCreate() 
  15. {
  16.     MyQueue*sl=NULL;
  17.     sl=(MyQueue*)malloc(sizeof(MyQueue));
  18.     sl->q=(ST*)malloc(sizeof(ST));
  19.     sl->p=(ST*)malloc(sizeof(ST));
  20.     sl->q->a=NULL;
  21.     sl->q->top=0;
  22.     sl->q->capacity=0;
  23.     sl->p->a=NULL;
  24.     sl->p->top=0;
  25.     sl->p->capacity=0;
  26.     return sl;
  27. }
  28.  
  29. bool STempty(ST* sl)
  30. {
  31. 	assert(sl);
  32. 	return sl->top == 0;
  33. }
  34.  
  35. int STtop(ST* sl)
  36. {
  37. 	assert(sl);
  38. 	assert(!STempty(sl));
  39.     int i;
  40. 	i=sl->a[sl->top-1];
  41.     return i;
  42. }
  43.  
  44.  
  45. void myQueuePush(MyQueue* obj, int x) {
  46.     while(!STempty(obj->q))
  47.     {
  48. if (obj->p->top == obj->q->capacity)
  49. {
  50. 	int newcapacity = obj->q->capacity == 0 ? 2 : obj->p->capacity * 2;
  51. 	int * tmp = (int*)realloc(obj->p->a, newcapacity * sizeof(int));
  52. 	obj->p->a = tmp;
  53. 	obj->p->capacity = newcapacity;
  54. }
  55. obj->p->a[obj->p->top] =STtop(obj->q) ;
  56. obj->p->top++;
  57. obj->q->top--;
  58.  
  59.  
  60.     }
  61.     if (obj->p->top == obj->p->capacity)
  62. {
  63. 	int newcapacity = obj->p->capacity == 0 ? 2 : obj->p->capacity * 2;
  64. 	int * tmp = (int*)realloc(obj->p->a, newcapacity * sizeof(int));
  65. 	obj->p->a = tmp;
  66. 	obj->p->capacity = newcapacity;
  67. }
  68. obj->p->a[obj->p->top] = x;
  69. obj->p->top++;
  70. }
  71.  
  72. int myQueuePop(MyQueue* obj) {
  73.     while(!STempty(obj->p))
  74.     {
  75.         if (obj->q->top == obj->q->capacity)
  76. {
  77. 	int newcapacity = obj->q->capacity == 0 ? 2 : obj->q->capacity * 2;
  78. 	int * tmp = (int*)realloc(obj->q->a, newcapacity * sizeof(int));
  79. 	obj->q->a = tmp;
  80. 	obj->q->capacity = newcapacity;
  81. }
  82. obj->q->a[obj->q->top] =STtop(obj->p) ;
  83. obj->q->top++;
  84. obj->p->top--;
  85.     }
  86.     int i=STtop(obj->q);
  87.     obj->q->top--;
  88.     return i;
  89. }
  90.  
  91. int myQueuePeek(MyQueue* obj) {
  92.     while(!STempty(obj->p))
  93.     {
  94.  
  95.    if (obj->q->top == obj->q->capacity)
  96. {
  97. 	int newcapacity = obj->q->capacity == 0 ? 2 : obj->q->capacity * 2;
  98. 	int * tmp = (int*)realloc(obj->q->a, newcapacity * sizeof(int));
  99. 	obj->q->a = tmp;
  100. 	obj->q->capacity = newcapacity;
  101. }
  102. obj->q->a[obj->q->top] =STtop(obj->p) ;
  103. obj->q->top++;
  104. obj->p->top--;
  105.     }
  106.      int i=STtop(obj->q);
  107.     return i;
  108. }
  109.  
  110. bool myQueueEmpty(MyQueue* obj) {
  111.     if(STempty(obj->p)&&STempty(obj->q))
  112.     return true;
  113.     else
  114.     return false;
  115. }
  116.  
  117. void myQueueFree(MyQueue* obj) {
  118.     free(obj->p);
  119.     free(obj->q);
  120. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/892018
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号