数据结构【栈和队列附顺序表应用算法】
栈和队列和顺序表应用算法练习
1.栈
1.1概念与结构
栈：⼀种特殊的线性表，其只允许在固定的⼀端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈，出数据也在栈顶。
1.2栈的实现
typedefint STDataType;typedefstructStack{ STDataType * a;int top;int capacity;}ST;// 初始化栈voidSTInit(ST* ps);// 销毁栈voidSTDestroy(ST* ps);// ⼊栈voidSTPush(ST* ps, STDataType x);//出栈voidSTPop(ST* ps);//取栈顶元素 STDataType STTop(ST* ps);//获取栈中有效元素个数intSTSize(ST* ps);//栈是否为空 bool STEmpty(ST* ps);2.队列
2.1概念与结构
概念：只允许在⼀端进行插入数据操作，在另⼀端进行删除数据操作的特殊线性表，队列具有先进先出。
入队列：进行插⼊操作的⼀端称为队尾。
出队列：进行删除操作的⼀端称为队头。
2.2队列的实现
typedefint QDataType;//队列结点结构typedefstructQueueNode{int val;structQueueNode* next;}QNode;//队列结构typedefstructQueue{ QNode* phead; QNode* ptail;int size;}Queue;//初始化队列voidQueueInit(Queue* pq);//销毁队列voidQueueDestroy(Queue* pq);// ⼊队列，队尾voidQueuePush(Queue* pq, QDataType x);// 出队列，队头voidQueuePop(Queue* pq);//取队头数据 QDataType QueueFront(Queue* pq);//取队尾数据 QDataType QueueBack(Queue* pq);//队列判空 bool QueueEmpty(Queue* pq);//队列有效元素个数intQueueSize(Queue* pq);3.附（顺序表应用算法）
3.1移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k。
- 更改
nums数组，使nums的前 k 个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。 - 返回
k。
intremoveElement(int* nums,int numsSize,int val){int dst =0, src =0;while(src < numsSize){if(nums[src]!= val){ nums[dst]= nums[src]; dst++;} src++;}return dst;}3.2删除有序数组中的重复项
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
- 更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。 - 返回
k。
intremoveDuplicates(int* nums,int numsSize){int dst =0, src = dst +1;while(src < numsSize){if(nums[src]!=nums[dst]&&++dst != src){ nums[dst]= nums[src];}++src;}return dst +1;}3.3合并两个有序数组
给你两个按非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
voidmerge(int* nums1,int nums1Size,int m,int* nums2,int nums2Size,int n){int l1 = m -1;int l2 = n -1;int l3 = m + n -1;while(l1 >=0&& l2 >=0){if(nums1[l1]> nums2[l2]){ nums1[l3--]= nums1[l1--];}else{ nums1[l3--]= nums2[l2--];}while(l2 >0){ nums1[l3--]= nums2[l2--];}}}
