• Day 64 栈的顺序和链式存储 队列

    1.栈的概念：

    栈（ stack ）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新 元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶 元素删除掉，使其相邻的元素成为新的栈顶元素。
    栈 （ Stack ）：是只允许在一端进行插入或删除的线性表。首先栈是一 种线性表， 但限定这种线性表只能在某一端进行插入和删除操作。
    栈顶 （ Top ）：线性表允许进行插入删除的那一端。
    栈底 （ Bottom ）：固定的，不允许进行插入和删除的另一端。
    空栈 ：不含任何元素的空表。
    栈又称为后进先出（ Last In First Out ）的线性表，简称 LIFO 结构
    特性：
    它的特殊之处在于限制了这个线性表的插入和删除的位置 , 它始终只在栈顶进行。这也就使
    得 : == 栈底是固定的 , 最先进栈的只能在栈底 == 。
    对栈的操作：
    示例如下： 
    1. #include
    2. #include
    3. #include
    4. #define MAX_SIZE 50
    5.  
    6. typedef struct{
    7. 	void *data[MAX_SIZE];
    8. 	int size;
    9. }Stack;
    10.  
    11. typedef struct{
    12. 	char name[15];
    13. 	int age;
    14. 	char breed[10]; 
    15. }Stu;
    16.  
    17. Stack *initstack(void){
    18. 	Stack *stack=(Stack *)malloc(sizeof(Stack));
    19. 	if(stack==NULL){
    20. 		printf("malloc error.\n");
    21. 		return NULL;
    22. 	}
    23. 	for(int i=0;i
    24. 		stack->data[i]=NULL;
    25. 	}
    26. 	stack->size=0;
    27. 	return stack;
    28. }
    29.  
    30. void pushstack(Stack *stack,void *data){
    31. 	if(stack==NULL){
    32. 		return;
    33. 	}
    34. 	if(stack->size==MAX_SIZE){
    35. 		return;
    36. 	}
    37. 	if(data==NULL){
    38. 		return;
    39. 	}
    40. 	stack->data[stack->size]=data;
    41. 	stack->size++;
    42. } 
    43.  
    44. void popstack(Stack *stack){
    45. 	if(stack==NULL){
    46. 		return;
    47. 	}
    48. 	if(stack->size==0){
    49. 		return;
    50. 	}
    51. 	stack->data[stack->size-1]=NULL;
    52. 	stack->size--;
    53. }
    54.  
    55. void *topelement(Stack *stack){
    56. 	if(stack==NULL){
    57. 		return NULL;
    58. 	}
    59. 	if(stack->size==0){
    60. 		return NULL;
    61. 	}
    62. 	return stack->data[stack->size-1];
    63. }
    64.  
    65. int isempty(Stack *stack){
    66. 	if(stack==NULL){
    67. 		return 0;
    68. 	}
    69. 	if(stack->size==0){
    70. 		return 0;
    71. 	}
    72. 	return 1;
    73. }
    74.  
    75. int sizestack(Stack *stack){
    76. 	if(stack==NULL){
    77. 		return -1;
    78. 	}
    79. 	return stack->size;
    80. }
    81.  
    82. void clearstack(Stack *stack){
    83. 	if(stack==NULL){
    84. 		return;
    85. 	}
    86. 	for(int i=0;isize;i++){
    87. 		stack->data[i]=NULL;
    88. 	}
    89. 	stack->size=0;
    90. }
    91.  
    92. void freestack(Stack *stack){
    93. 	if(stack==NULL){
    94. 		return;
    95. 	}
    96. 	free(stack);
    97. }
    98.  
    99. int main(){
    100. 	Stack *stack=initstack();
    101. 	Stu p1={"洛羽晨",18,"人类"};
    102. 	Stu p2={"虚构康",20,"不详"};
    103. 	Stu p3={"丁真",23,"出生"};
    104. 	Stu p4={"谷爱凌",22,"剑冢"};
    105. 	pushstack(stack,&p1);
    106. 	pushstack(stack,&p2);
    107. 	pushstack(stack,&p3);
    108. 	pushstack(stack,&p4);
    109. 	while(sizestack(stack)>0){
    110. 		Stu *p=(Stu *)topelement(stack);
    111. 		printf("name:%s,age=%d,breed=%s\n",p->name,p->age,p->breed);
    112. 		popstack(stack);
    113. 	}
    114. 	freestack(stack);
    115. 	return 0;
    116. }

    2.栈的链式存储结构：

    概念：上面讲的是栈的顺序存储结构，相当于一个线性表，只是操作位置有限制。链式存储结构也就是链表形式的栈。它和链表的结构是一样的，操作方式和上面的一样。

    操作：

    示例如下：

    1.  
    2. #include "linkstack.h"
    3. typedef struct
    4. {
    5. char name[64];
    6. int age;
    7. int score;
    8. }Person;
    9. //打印函数
    10. void my_print(void *data)
    11. {
    12. Person *p=(Person *)data;
    13. printf("name:%s age:%d score:%d\n",p->name,p->age,p->score);
    14. }
    15. int main()
    16. {
    17. //创建链表
    18. LinkStack *stack=init_linkstack();
    19. //获取链表长度
    20. printf("stack 长度：%d\n",size_linkstack(stack));
    21. //创建数据
    22. //创建数据
    23. Person p1={"aaa",10,80};
    24. Person p2={"bbb",11,81};
    25. Person p3={"ccc",12,82};
    26. Person p4={"ddd",13,83};
    27. //入栈
    28. push_linkstack(stack, &p1);
    29. push_linkstack(stack, &p2);
    30. //打印
    31. print_linkstack(stack, my_print);
    32. printf("\n");
    33. //入栈
    34. push_linkstack(stack, &p3);
    35. push_linkstack(stack, &p4);
    36. //打印
    37. print_linkstack(stack, my_print);
    38. printf("\n");
    39. //出栈
    40. void *data=pop_linkstack(stack);
    41. my_print(data);
    42. printf("\n");
    43. //打印
    44. print_linkstack(stack, my_print);
    45. printf("\n");
    46. //获取链表长度
    47. printf("stack 长度：%d\n",size_linkstack(stack));
    48. //返回第一个结点
    49. Person *p=(Person *)top_element(stack);
    50. printf("top_element：name-%s,age-%d,score-%d\n",p->name,p->age,p->score);
    51. //销毁
    52. free_linkstack(stack);
    53. return 0;
    54. }
    55. #include "linkstack.h"
    56. //初始链表
    57. LinkStack *init_linkstack(void)
    58. {
    59. LinkStack *stack=(LinkStack *)malloc(sizeof(LinkStack));
    60. stack->size=0;
    61. //头结点
    62. stack->head=(LinkNode *)malloc(sizeof(LinkNode));
    63. stack->head->data=NULL;
    64. stack->head->next=NULL;
    65. return stack;
    66. }
    67. //指定位置插入
    68. void push_linkstack(LinkStack *stack, void *data)
    69. {
    70. if(stack == NULL)
    71. {
    72. return ;
    73. }
    74. if(data == NULL)
    75. {
    76. return ;
    77. }
    78. //创建新的结点
    79. LinkNode *newnode=(LinkNode *)malloc(sizeof(LinkNode));
    80. newnode->data=data;
    81. newnode->next=NULL;
    82. //找结点
    83. //辅助指针变量
    84. LinkNode *pcurrent=stack->head;
    85. //新结点插入链表
    86. newnode->next=pcurrent->next;
    87. pcurrent->next=newnode;
    88. stack->size++;
    89. }
    90. //删除指定位置的值
    91. void *pop_linkstack(LinkStack *stack)
    92. {
    93. if(stack == NULL)
    94. {
    95. return NULL;
    96. }
    97. //找结点
    98. //辅助指针变量
    99. LinkNode *pcurrent=stack->head;
    100. //删除结点
    101. LinkNode *delnode=pcurrent->next;
    102. pcurrent->next=delnode->next;
    103. void *data=delnode->data;
    104. free(delnode);
    105. stack->size--;
    106. return data;
    107. }
    108. //获取链表长度
    109. int size_linkstack(LinkStack *stack)
    110. {
    111. return stack->size;
    112. }
    113. //返回栈顶元素数据域
    114. void *top_element(LinkStack *stack)
    115. {
    116. return stack->head->next->data;
    117. }
    118. //打印栈内所有内容
    119. void print_linkstack(LinkStack *stack, printlinknode print)
    120. {
    121. if(stack == NULL)
    122. {
    123. return ;
    124. }
    125. //辅助指针变量
    126. LinkNode *pcurrent=stack->head->next;
    127. while(pcurrent!=NULL)
    128. {
    129. print(pcurrent->data);
    130. pcurrent=pcurrent->next;
    131. }
    132. }
    133. //释放链表内存
    134. void free_linkstack(LinkStack *stack)
    135. {
    136. if(stack == NULL)
    137. {
    138. return ;
    139. }
    140. //辅助指针变量
    141. LinkNode *pcurrent=stack->head;
    142. while(pcurrent!=NULL)
    143. {
    144. //缓存下一个结点
    145. LinkNode *pnext=pcurrent->next;
    146. free(pcurrent);
    147. pcurrent=pnext;
    148. }
    149. //释放链表内存
    150. stack->size=0;
    151. free(stack);
    152. }
    153. #ifndef LINKLIST_H
    154. #define LINKLIST_H
    155. #include 
    156. #include 
    157. #include 
    158. #endif
    159. //结点结构体
    160. typedef struct NODE
    161. {
    162. void *data;
    163. struct NODE *next;
    164. }LinkNode;
    165. //栈表结构体
    166. typedef struct
    167. {
    168. LinkNode *head;
    169. int size;
    170. }LinkStack;
    171. //打印函数指针
    172. typedef void(*printlinknode)(void *);
    173. //初始栈表
    174. LinkStack *init_linkstack(void);
    175. //入栈
    176. void push_linkstack(LinkStack *stack, void *data);
    177. //出栈
    178. void *pop_linkstack(LinkStack *stack);
    179. //获取链表长度
    180. int size_linkstack(LinkStack *stack);
    181. //返回第一个结点
    182. void *top_element(LinkStack *stack);
    183. //打印栈内结点
    184. void print_linkstack(LinkStack *stack, printlinknode print);
    185. //释放栈内存
    186. void free_linkstack(LinkStack *stack);

    2.队列的概念：

    队列是一种特殊的 线性表 ，特殊之处在于它只允许在表的前端（ front ）进行删除操作，而在表的后端（ rear ）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进 行删除操作的端称为队头。

     

    队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中 删除， == 故队列又称为先进先出（ FIFO—first in first out ） 线性表 。
    2.对队列的操作： 增删改查
    示例如下： 
    1. #include 
    2. #include 
    3. #define MAX_SIZE 1024
    4. typedef struct
    5. {
    6. void *data[MAX_SIZE];
    7. int size;
    8. }Queue;
    9. //初始化
    10. Queue * init_queue(void)
    11. {
    12. Queue *queue=(Queue *)malloc(sizeof(Queue));
    13. for(int i=0;i
    14. {
    15. queue->data[i]=NULL;
    16. }
    17. queue->size=0;
    18. return queue;
    19. }
    20. //入队
    21. void push_queue(Queue *queue, void *data)
    22. {
    23. //数组左边当做对头
    24. if(queue==NULL)
    25. {
    26. return ;
    27. }
    28. if(data==NULL)
    29. {
    30. return ;
    31. }
    32. queue->data[queue->size]=data;
    33. queue->size++;
    34. }
    35. //返回对头元素
    36. void *front_queue(Queue *queue)
    37. {
    38. if(queue==NULL)
    39. {
    40. return NULL;
    41. }
    42. if(queue->size==0)
    43. {
    44. return NULL;
    45. }
    46. return queue->data[0];
    47. }
    48. //出队
    49. void pop_queue(Queue *queue)
    50. {
    51. //需要移动元素
    52. if(queue==NULL)
    53. {
    54. return ;
    55. }
    56. if(queue->size==0)
    57. {
    58. return ;
    59. }
    60. for(int i=0;isize-1;i++)
    61. {
    62. queue->data[i]=queue->data[i+1];
    63. }
    64. queue->size--;
    65. }
    66. //返回队尾元素
    67. void *back_queue(Queue *queue)
    68. {
    69. if(queue==NULL)
    70. {
    71. return NULL;
    72. }
    73. if(queue->size==0)
    74. {
    75. return NULL;
    76. }
    77. return queue->data[queue->size-1];
    78. }
    79. //返回大小
    80. int size_queue(Queue *queue)
    81. {
    82. if(queue==NULL)
    83. {
    84. return -1;
    85. }
    86. return queue->size;
    87. }
    88. //清空队列
    89. void clear_queue(Queue *queue)
    90. {
    91. if(queue==NULL)
    92. {
    93. return ;
    94. }
    95. while(queue->size>0)
    96. {
    97. queue->size--;
    98. queue->data[queue->size]=NULL;
    99. }
    100. }
    101. //销毁
    102. void free_queue(Queue *queue)
    103. {
    104. if(queue==NULL)
    105. {
    106. return ;
    107. }
    108. free(queue);
    109. }
    110. typedef struct
    111. {
    112. char name [64];
    113. int age;
    114. }Person;
    115. int main()
    116. {
    117. //创建队列
    118. Queue *queue=init_queue();
    119. //创建数据
    120. Person p1={"aaa",10};
    121. Person p2={"bbb",10};
    122. Person p3={"ccc",10};
    123. Person p4={"ddd",10};
    124. //入队
    125. push_queue(queue,&p1);
    126. push_queue(queue,&p2);
    127. push_queue(queue,&p3);
    128. push_queue(queue,&p4);
    129. //取出对尾元素
    130. Person *p=(Person *)back_queue(queue);
    131. printf("name:%s, age=%d\n",p->name,p->age);
    132. printf("\n");
    133. clear_queue(queue);
    134. printf("\n");
    135. //入队
    136. push_queue(queue,&p1);
    137. push_queue(queue,&p2);
    138. push_queue(queue,&p3);
    139. push_queue(queue,&p4);
    140. //输出
    141. while(size_queue(queue)>0)
    142. {
    143. //取出对头元素
    144. Person *p=(Person *)front_queue(queue);
    145. printf("name:%s, age=%d\n",p->name,p->age);
    146. //出队
    147. pop_queue(queue);
    148. }
    149. //销毁队列
    150. free_queue(queue);
    151. return 0;
    152. }

  • 相关阅读:
    stm32之dma
    标记蛋白用PEG衍生物Fmoc-PEG4-NHS ester，1314378-14-7
    每日一博 - 图解进程（Process）和线程（Thread）区别联系
    C++基础——第1章：C++初探
    antv G6在vue项目中的实践总结
    DataGridView 控件分页
    Inno Setup 选择安装路径的问题
    python的类属性和实例属性
    【ETL工具】本地环境IDEA远程DEBUG调试Flume代码
    【JavaSE】基础语法知识汇总
  • 原文地址：https://blog.csdn.net/m0_60247706/article/details/127794234