devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C语言实现栈与队列_堆栈和队列c语言

作者：笔触狂放9 | 2024-05-18 18:24:08

赞

踩

堆栈和队列c语言

栈

一.栈的定义

  1.栈：是只允许在一边进行插入或删除的顺序表。■特别之处在于只能在一端进行删除、插入。

  2.栈顶：进行删除或插入操作的一端。

  3.栈底：不能进行删除或插入的一端。

二.栈的算法

 
栈的实现可以用数组（顺序表），也可以使用链表，这里使用顺序表来实现。栈的常见操作有栈的初始化、销毁、增删等等，以下是栈创建过程中使用的函数。

  1.宏定义（初始准备）

  不直接定义一个数组，而采用realloc、malloc来动态管理顺序表大小，使栈的大小不再受限。再定义一个top栈顶指针来方便后续的增删操作。

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<assert.h>
  4. #include<stdbool.h>
  5.  
  6. typedef int MyDataType;//将int类型重定义叫做MyDataType
  7. typedef struct Stack
  8. {
  9. 	MyDataType* a;//一个MyDataType类型的指针，可以进行动态内存开辟
  10. 	int capacity;//栈的最大容量
  11. 	int top;//用于栈顶指针
  12. }ST;

2.栈的初始化

  在初始化中，将top栈顶指针指向0，但此时栈中没有元素（此时栈为空）。当然也可以将top初始化为-1，此时当top为0时栈中含有一个元素。

  1. ST st；//在测试代码中预先定义一个ST类型的变量
  2. void  InitStack(ST* ps)
  3. {
  4. 	assert(ps);
  5. 	ps->a = NULL;
  6. 	ps->capacity = 0;
  7. 	ps->top = 0;//将栈顶指针指向0
  8. }

3.向栈顶插入元素

   在插入数据前，需要判断ps指针是否为空，还要判断栈是否已经达到最大容量，如果size=capacity（栈已达到最大容量）就需要使用realloc扩容（注意：使用realloc函数时，若第一个参数为空，则函数返回一个开辟了指定大小的地址）。当top初始化为0时，先赋值，在++top；而当top初始化为-1时，先++top，再赋值。

  1. void  PushStack(ST* ps, MyDataType x)
  2. {
  3. 	assert(ps);
  4. 	if (ps->top == ps->capacity)
  5. 	{
  6. 		int NewSize = ps->top == 0 ? 4 : ps->capacity * 2;//用三目运算符可以避免对top是否为零的两种情况进行讨论
  7. 		MyDataType* temp = (MyDataType*)realloc(ps->a, sizeof(MyDataType) * NewSize);
  8. 		if (temp == NULL)
  9. 		{
  10. 			perror("realloc");
  11. 			exit(-1);
  12. 		}
  13. 		ps->a = temp;
  14. 		ps->capacity = NewSize;
  15. 	}
  16. 	ps->a[ps->top] = x;
  17. 	ps->top++;//先赋值再将top加一
  18. }

4.判断栈是否为空

  1. bool StackEmpty(ST* ps)
  2. {
  3. 	assert(ps);
  4. 	return ps->top == 0;//ps->top为0，表达式为真返回true
  5. }

 5.删除栈顶元素

  删除栈顶元素之前首先需要判断栈是否为空，如果为空则不能删除元素。顺序表删除尾部元素十分简单，只需要将栈顶指针指向的位置减一即可。

  1. void  PopStack(ST* ps)
  2. {
  3. 	assert(ps);
  4. 	assert(ps->top > 0);
  5. 		--ps->top;
  6. }

6.计算栈中元素个数

  由于对top初始化时的值不同，计数的条件不同，所以读取个数的操作也由我们来书写，而不由使用者自己来判断。

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

7.读取栈顶元素

  1. MyDataType StackTop(ST* ps)
  2. {
  3. 	assert(ps);
  4. 	assert(ps->top > 0);//需要判断栈是否为空，为空则不能读取栈顶元素
  5. 	return ps->a[ps->top-1];
  6. }

8.销毁栈

  销毁需要把动态开辟的空间全部释放，并将指针置为空。

  1. void DestroyStack(ST* ps)
  2. {
  3. 	assert(ps);
  4. 	free(ps->a);
  5. 	ps->a = NULL;
  6. 	ps->capacity = ps->top = 0;
  7. }

三.栈的例题

题目链接：

有效的括号

题目解答：

栈的特点是后入先出，与括号之间匹配判断一致

  1. typedef char MyDataType;
  2. typedef struct Stack
  3. {
  4. 	MyDataType* a;
  5. 	int capacity;
  6. 	int top;
  7. }ST;
  8.  
  9. void  InitStack(ST*ps);
  10. void  PushStack(ST* ps,MyDataType x);
  11. void  PopStack(ST* ps);
  12. void DestroyStack(ST* ps);
  13. bool StackEmpty(ST* ps);
  14. MyDataType StackTop(ST* ps);
  15. int StackSize(ST* ps);
  16. void  InitStack(ST* ps)
  17. {
  18. 	assert(ps);
  19. 	ps->a = NULL;
  20. 	ps->capacity = 0;
  21. 	ps->top = 0;
  22. }
  23. void  PushStack(ST* ps, MyDataType x)
  24. {
  25. 	assert(ps);
  26. 	if (ps->top == ps->capacity)
  27. 	{
  28. 		int NewSize = ps->top == 0 ? 4 : ps->capacity * 2;
  29. 		MyDataType* temp = (MyDataType*)realloc(ps->a, sizeof(MyDataType) * NewSize);
  30. 		if (temp == NULL)
  31. 		{
  32. 			perror("realloc");
  33. 			exit(-1);
  34. 		}
  35. 		ps->a = temp;
  36. 		ps->capacity = NewSize;
  37. 	}
  38. 	ps->a[ps->top] = x;
  39. 	ps->top++;
  40. }
  41. void  PopStack(ST* ps)
  42. {
  43. 	assert(ps);
  44. 	assert(ps->top > 0);
  45. 		--ps->top;
  46. }
  47. void DestroyStack(ST* ps)
  48. {
  49. 	assert(ps);
  50. 	free(ps->a);
  51. 	ps->a = NULL;
  52. 	ps->capacity = ps->top = 0;
  53. }
  54. bool StackEmpty(ST* ps)
  55. {
  56. 	assert(ps);
  57. 	return ps->top == 0;
  58. }
  59. MyDataType StackTop(ST* ps)
  60. {
  61. 	assert(ps);
  62. 	assert(ps->top > 0);
  63. 	return ps->a[ps->top-1];
  64. }
  65. int StackSize(ST* ps)
  66. {
  67. 	assert(ps);
  68. 	assert(ps->top >= 0);
  69. 	return ps->top ;
  70. }//手动搭建一个栈
  71. bool isValid(char* s) 
  72. {
  73.     ST st;
  74.     InitStack(&st);  
  75.     while(*s)
  76.     {
  77.         if(*s=='('||*s=='['||*s=='{')//当为左括号时入栈
  78.         {
  79.             PushStack(&st,*s);
  80.         }
  81.         else//当为右括号的时候
  82.         {
  83.             if(StackEmpty(&st))
  84.             {
  85.                 DestroyStack(&st);
  86.                 return false;
  87.             }//如果栈为空时就读取到右括号，
  88.              //即说明还未有左括号就有右括号，显然不符合规律
  89.             int stacktop=StackTop(&st);
  90.             PopStack(&st);
  91.                 if(*s==')'&&stacktop!='('||
  92.                *s==']'&&stacktop!='['||
  93.                *s=='}'&&stacktop!='{' )//出栈并一一判断
  94.                {
  95.                    DestroyStack(&st);
  96.                    return false;
  97.                }
  98.         }
  99.         s++;
  100.     }  
  101.     bool ret=StackEmpty(&st);
  102.     return ret;
  103. }

队列

一.队列的定义

  队列是只允许在一端插入元素，另一端删除元素的线性表，特点是先进先出。

二.队列的算法

      队列是从队尾进，队头出，所以采用链表的结构来实现，如果采用数组结构，则会使队头操作繁琐。与栈类似，我们仍然是实现以下函数代码。

 1.宏定义（初始准备）

  Queue这个结构体中还包含两个QNode结点结构体。包含队列头尾结点，能够帮助从队尾插入和从队头删除。

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<assert.h>
  4. #include<stdbool.h>
  5.  
  6. typedef int MyDataType;//将int类型重命名为MyDataType
  7. typedef struct QueueNode
  8. {
  9. 	MyDataType val;
  10. 	struct QueueNode* next;
  11. }QNode;//单链表的结点结构
  12.  
  13. typedef struct Queue//队列中包含队头、队尾、队列大小
  14. {
  15. 	QNode* front;
  16. 	QNode* back;
  17. 	int size;
  18. }QL;

2.队列的初始化

  1. void QueueInit(QL* pq)
  2. {
  3. 	assert(pq);//判断pq是否为空指针
  4. 	pq->size = 0;
  5. 	pq->front = pq->back = NULL;
  6. }

3.向队尾插入元素

  1. void QueuePush(QL* pq, MyDataType x)
  2. {
  3. 	assert(pq);
  4. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
  5. 	if (newnode == NULL)
  6. 	{
  7. 		perror("malloc fail");
  8. 		exit(-1);
  9. 	}
  10. 	newnode->val = x;
  11. 	newnode->next = NULL;
  12. 	if (pq->back == NULL)
  13. 		pq->front = pq->back = newnode;//链表为空，则让front和back都指向newnode
  14. 	else
  15. 	{
  16. 		pq->back->next = newnode;
  17. 		pq->back = newnode;
  18. 	}
  19. 	pq->size++;
  20. }//与单链表搭建类似，由于不含头结点，
  21. //所以需要分链表是否为空的两种情况讨论。

4.删除队头元素

  1. void QueuePop(QL* pq)//与单链表不同，这里不需要传二级指针，
  2.                      //因为这里只是修改结构体中的内容，而不是改变结构体地址
  3. {
  4. 	assert(pq);
  5. 	assert(!QueueEmpty(pq));//断言链表不为空，为空则不能删除数据
  6. 	if (pq->front->next == NULL)//链表只含有一个数据
  7. 	{
  8. 		free(pq->front);
  9. 		pq->back = pq->front = NULL;
  10. 	}
  11. 	else
  12. 	{
  13. 		QNode* cur = pq->front->next;
  14. 		free(pq->front);
  15. 		pq->front = cur;
  16. 	}
  17. 	pq->size--;
  18. }

5.读取队尾和队头元素

  1. MyDataType QueueFront(QL* pq)//队头元素
  2. {
  3. 	assert(pq);
  4. 	assert(!QueueEmpty(pq));//不能为空链表
  5. 	return pq->front->val;
  6. }
  7. MyDataType QueueBack(QL* pq)//队尾元素
  8. {
  9. 	assert(pq);
  10. 	assert(!QueueEmpty(pq));//不能为空链表
  11. 	return pq->back->val;
  12. }

6.判断队列是否为空，读取队列大小

    即使是读取队列元素个数这样的操作也靠函数实现，能有效避免使用者不明变量含义而造成读取元素个数错误。

  1. bool QueueEmpty(QL* pq)//判断队列是否为空
  2. {
  3. 	assert (pq);
  4. 	return  pq->front==NULL;//若头结点为空，则队列不含任何元素，队列为空
  5. }
  6. int QueueSize(QL* pq)//读取队列大小
  7. {
  8. 	return pq->size;
  9. }

7.队列的销毁

  1. void QueueDestroy(QL* pq)
  2. {
  3. 	assert(pq);
  4. 	QNode* cur = pq->front;
  5. 	while (cur)
  6. 	{
  7. 		QNode* next = cur->next;
  8. 		free(cur);
  9. 		cur = next;
  10. 	}//每个结点一一释放空间
  11. 	pq->back = pq->front = NULL;
  12. 	pq->size = 0;
  13. }

三.队列的例题

题目链接：

设计循环队列

题目解答：

  可以使用单链表和数组，但显然使用数组更方便。问题的关键在于数组尾元素的处理，这时要灵活使用取模操作。

  1.  
  2. typedef struct {
  3.     int *a;
  4.     int front;
  5.     int rear;
  6.     int k;
  7. } MyCircularQueue;
  8.  
  9.  
  10. MyCircularQueue* myCircularQueueCreate(int k) {
  11.     MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  12.     obj->k=k;
  13.     obj->a=(int *)malloc(sizeof(int)*(k+1));
  14.     obj->front=obj->rear=0;
  15.     return obj;
  16. }
  17.  
  18. bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
  19. {
  20.     return obj->front==obj->rear;    
  21. }
  22.  
  23. bool myCircularQueueIsFull(MyCircularQueue* obj) 
  24. {
  25.     return (obj->rear+1)% (obj->k+1)==obj->front;   
  26. }
  27.  
  28.  
  29. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
  30. {
  31.         if(myCircularQueueIsFull(obj))
  32.         return false;
  33.         obj->a[obj->rear]=value;
  34.         obj->rear=(obj->rear+1)%(obj->k+1);
  35.         return true;
  36. }
  37.  
  38. bool myCircularQueueDeQueue(MyCircularQueue* obj) 
  39. {
  40.     if(myCircularQueueIsEmpty(obj))
  41.     return false;
  42.     obj->front=(obj->front+1)%(obj->k+1);
  43.     return true;    
  44. }
  45.  
  46. int myCircularQueueFront(MyCircularQueue* obj) 
  47. {
  48.     if(myCircularQueueIsEmpty(obj))
  49.     return -1;
  50.     else
  51.     return obj->a[obj->front];    
  52. }
  53.  
  54. int myCircularQueueRear(MyCircularQueue* obj) {
  55.     if(myCircularQueueIsEmpty(obj))
  56.     return -1;
  57.     else
  58.     return obj->a[(obj->rear+obj->k)%(obj->k+1)];
  59.  
  60. }
  61.  
  62. void myCircularQueueFree(MyCircularQueue* obj) {
  63.     free(obj->a);
  64.     free(obj);
  65.     
  66. }

栈与队列的互相实现

题目链接：

题目一：用栈实现队列

题目二：用队列实现栈

题目解答：

 题目一：由于C语言没有库函数来搭建栈，所以我们必须手动搭建一个栈。思路很简单：用一个栈专门来进数据；另一个栈专门来出数据。

  1. typedef int MyDataType;
  2. typedef struct Stack
  3. {
  4. 	MyDataType* a;
  5. 	int capacity;
  6. 	int top;
  7. }ST;
  8.  
  9. void  InitStack(ST*ps);
  10. void  PushStack(ST* ps,MyDataType x);
  11. void  PopStack(ST* ps);
  12. void DestroyStack(ST* ps);
  13. bool StackEmpty(ST* ps);
  14. MyDataType StackTop(ST* ps);
  15. int StackSize(ST* ps);
  16. void  InitStack(ST* ps)
  17. {
  18. 	assert(ps);
  19. 	ps->a = NULL;
  20. 	ps->capacity = 0;
  21. 	ps->top = 0;
  22. }
  23. void  PushStack(ST* ps, MyDataType x)
  24. {
  25. 	assert(ps);
  26. 	if (ps->top == ps->capacity)
  27. 	{
  28. 		int NewSize = ps->top == 0 ? 4 : ps->capacity * 2;
  29. 		MyDataType* temp = (MyDataType*)realloc(ps->a, sizeof(MyDataType) * NewSize);
  30. 		if (temp == NULL)
  31. 		{
  32. 			perror("realloc");
  33. 			exit(-1);
  34. 		}
  35. 		ps->a = temp;
  36. 		ps->capacity = NewSize;
  37. 	}
  38. 	ps->a[ps->top] = x;
  39. 	ps->top++;
  40. }
  41. void  PopStack(ST* ps)
  42. {
  43. 	assert(ps);
  44. 	assert(ps->top > 0);
  45. 		--ps->top;
  46. }
  47. void DestroyStack(ST* ps)
  48. {
  49. 	assert(ps);
  50. 	free(ps->a);
  51. 	ps->a = NULL;
  52. 	ps->capacity = ps->top = 0;
  53. }
  54. bool StackEmpty(ST* ps)
  55. {
  56. 	assert(ps);
  57. 	return ps->top == 0;
  58. }
  59. MyDataType StackTop(ST* ps)
  60. {
  61. 	assert(ps);
  62. 	assert(ps->top > 0);
  63. 	return ps->a[ps->top-1];
  64. }
  65. int StackSize(ST* ps)
  66. {
  67. 	assert(ps);
  68. 	assert(ps->top >= 0);
  69. 	return ps->top ;
  70. }
  71.  
  72.  
  73. typedef struct {
  74.     ST pushstack;
  75.     ST popstack;
  76.     int size;
  77. } MyQueue;
  78.  
  79.  
  80. MyQueue* myQueueCreate() 
  81. {
  82.     MyQueue*queue=(MyQueue*)malloc(sizeof(MyQueue));
  83.     InitStack(&queue->pushstack);
  84.     InitStack(&queue->popstack);
  85.     queue->size=0;
  86.     return queue;
  87. }
  88.  
  89. void myQueuePush(MyQueue* obj, int x) 
  90. {
  91.     assert(obj);    
  92.     PushStack(&obj->pushstack,x);
  93. }
  94.  
  95. int myQueuePop(MyQueue* obj) 
  96. {
  97.     if(StackEmpty(&obj->popstack))
  98.     {
  99.         while(!StackEmpty(&obj->pushstack))
  100.         {
  101.             int push=StackTop(&obj->pushstack);
  102.             PopStack(&obj->pushstack);
  103.             PushStack(&obj->popstack,push);
  104.         }
  105.     }   
  106.     int pop=StackTop(&obj->popstack);
  107.     PopStack(&obj->popstack);
  108.     return pop; 
  109. }
  110.  
  111. int myQueuePeek(MyQueue* obj) 
  112. {
  113.     if(StackEmpty(&obj->popstack))
  114.     {
  115.         while(!StackEmpty(&obj->pushstack))
  116.         {
  117.             int push=StackTop(&obj->pushstack);
  118.             PopStack(&obj->pushstack);
  119.             PushStack(&obj->popstack,push);
  120.         }
  121.     }   
  122.     int pop=StackTop(&obj->popstack);
  123.     return pop;     
  124. }
  125.  
  126. bool myQueueEmpty(MyQueue* obj) 
  127. {
  128.     return StackEmpty(&obj->pushstack)&&StackEmpty(&obj->popstack);    
  129. }
  130.  
  131. void myQueueFree(MyQueue* obj) 
  132. {
  133.     DestroyStack(&obj->pushstack);
  134.     DestroyStack(&obj->popstack);
  135.     free(obj);    
  136. }

题目二：C语言仍然需要手动搭建队列。思路也不难：出数据时，现将数据导入另一个队列，只剩一个元素时，再弹出数据，如此反复。

  1. typedef int MyDataType;
  2. typedef struct QueueNode
  3. {
  4. 	MyDataType val;
  5. 	struct QueueNode* next;
  6. }QNode;
  7.  
  8. typedef struct Queue
  9. {
  10. 	QNode* front;
  11. 	QNode* back;
  12. 	int size;
  13. }QL;
  14.  
  15. void QueueInit(QL* pq);
  16. void QueueDestroy(QL* pq);
  17. void QueuePush(QL* pq, MyDataType x);
  18. void QueuePop(QL* pq);
  19. MyDataType QueueFront(QL* pq);
  20. MyDataType QueueBack(QL* pq);
  21. bool QueueEmpty(QL* pq);
  22. int QueueSize(QL* pq);
  23. void QueueInit(QL* pq)
  24. {
  25. 	assert(pq);
  26. 	pq->size = 0;
  27. 	pq->front = pq->back = NULL;
  28. }
  29. void QueueDestroy(QL* pq)
  30. {
  31. 	assert(pq);
  32. 	QNode* cur = pq->front;
  33. 	while (cur)
  34. 	{
  35. 		QNode* next = cur->next;
  36. 		free(cur);
  37. 		cur = next;
  38. 	}
  39. 	pq->back = pq->front = NULL;
  40. 	pq->size = 0;
  41. }
  42. void QueuePush(QL* pq, MyDataType x)
  43. {
  44. 	assert(pq);
  45. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
  46. 	if (newnode == NULL)
  47. 	{
  48. 		perror("malloc fail");
  49. 		exit(-1);
  50. 	}
  51. 	newnode->val = x;
  52. 	newnode->next = NULL;
  53. 	if (pq->back == NULL)
  54. 		pq->front = pq->back = newnode;
  55. 	else
  56. 	{
  57. 		pq->back->next = newnode;
  58. 		pq->back = newnode;
  59. 	}
  60. 	pq->size++;
  61. }
  62. void QueuePop(QL* pq)
  63. {
  64. 	assert(pq);
  65. 	assert(!QueueEmpty(pq));
  66. 	if (pq->front->next == NULL)
  67. 	{
  68. 		free(pq->front);
  69. 		pq->back = pq->front = NULL;
  70. 	}
  71. 	else
  72. 	{
  73. 		QNode* cur = pq->front->next;
  74. 		free(pq->front);
  75. 		pq->front = cur;
  76. 	}
  77. 	pq->size--;
  78. }
  79. MyDataType QueueFront(QL* pq)
  80. {
  81. 	assert(pq);
  82. 	assert(!QueueEmpty(pq));
  83. 	return pq->front->val;
  84. }
  85. MyDataType QueueBack(QL* pq)
  86. {
  87. 	assert(pq);
  88. 	assert(!QueueEmpty(pq));
  89. 	return pq->back->val;
  90. }
  91. bool QueueEmpty(QL* pq)
  92. {
  93. 	assert (pq);
  94. 	return  pq->back==NULL;
  95. }
  96. int QueueSize(QL* pq)
  97. {
  98. 	return pq->size;
  99. }
  100.  
  101.  
  102. typedef struct {
  103.     QL queue1;
  104.     QL queue2;
  105. } MyStack;
  106.  
  107.  
  108. MyStack* myStackCreate() {
  109.     MyStack*mystack=(MyStack*)malloc(sizeof(MyStack));
  110.     QueueInit(&mystack->queue1);
  111.     QueueInit(&mystack->queue2);
  112.     return mystack;
  113. }
  114.  
  115. void myStackPush(MyStack* obj, int x) 
  116. {
  117.     if(QueueEmpty(&obj->queue1))
  118.     {
  119.         QueuePush(&obj->queue2,x);
  120.     }    
  121.     else{
  122.         QueuePush(&obj->queue1,x);
  123.     }
  124. }
  125.  
  126. int myStackPop(MyStack* obj) 
  127. {
  128.     QL* empque=&obj->queue1;
  129.     QL *noempque=&obj->queue2;
  130.     if(QueueEmpty(&obj->queue2))
  131.     {
  132.         empque=&obj->queue2;
  133.         noempque=&obj->queue1;
  134.     }
  135.     while(QueueSize(noempque)!=1)
  136.     {
  137.         int push=QueueFront(noempque);
  138.         QueuePop(noempque);
  139.         QueuePush(empque,push);
  140.     }
  141.     int pop=QueueFront(noempque);
  142.     QueuePop(noempque);
  143.     return pop;
  144. }
  145.  
  146. int myStackTop(MyStack* obj) {
  147.     if(!QueueEmpty(&obj->queue1))
  148.     return QueueBack(&obj->queue1);
  149.     else
  150.     return QueueBack(&obj->queue2);
  151.  
  152. }
  153.  
  154. bool myStackEmpty(MyStack* obj) {
  155.  
  156.     return QueueEmpty(&obj->queue1)&&QueueEmpty(&obj->queue2);
  157.     
  158. }
  159.  
  160. void myStackFree(MyStack* obj) {
  161.     free(obj);
  162.     
  163. }

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

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

  

闽ICP备14008679号