LeetCode刷题过程中，常常用到的线性表主要包括以下四个重要的数据结构:数组、链表、栈、队列。
下面将分别讲解数组、链表、栈和队列。
线性表概述线性:这里的线性是逻辑上的连续，而非物理存储的连续。
存储的数据:线性表是一个有n个相同类型数据的有序序列。
数组array介绍数组是物理存储连续的线性表，其常见的形式为a[0]、a[1]...a[n-1]，a[i-1]是a的前驱，a[i+1]是a的后继。
基本操作插入插入元素，要将插入位置后的元素全部向后移动一位。
下图以数组长度为6，数据为0、1、2、3、4、5，在位置3插入一个元素X举例。
删除删除元素，要讲删除位置后的元素全部向前移动一位。
下图以数组长度为6，数据为0、1、2、3、4、5，删除位置3上的元素X举例。
反转翻转数组，本质是将数组存储的数据进行反转。
下图以数组长度为6，数据为0、1、2、3、4、5，反转整个数组举例。
例题LeetCode27.移除元素题意
删除数组中所有等于val的元素，返回移除后数组的新长度。要求不使用额外的空间。
示例
输入：nums=[3,2,2,3],val=3输出：2,nums=[2,2]
题解
数组的删除操作，但如何不使用额外的空间呢？因为删除val后的数组的长度小于等于原数组的长度，因此可以一边将不等于val的数组放入原数组中，同时判断原数组的数是否等于val。
代码
classSolution{publicintremoveElement(int[]nums,intval){//left存当前nums数组中不等于val的数字数量intleft=0;for(intright=0;rightnums.length;right++){if(nums[right]!=val){nums[left]=nums[right];left++;}}returnleft;}}习题推荐
LeetCode35.搜索插入位置
链表介绍链表的出现是为了解决数组插入、删除带来的线性开销。
区别于数组，链表中的元素可以不连续存储，每一个元素包含该元素的数据和指向链表下一个节点的指针。
基本操作插入插入元素，要将插入元素前一个位置的指针指向插入元素本身，将插入元素的指针指向前一个位置。
删除删除元素，要将删除元素前一个元素的指针指向删除元素后一个元素，代码实现上需要将删除元素指针指向的位置记录下来。
下图是以长度为5的链表，删除位置3上的元素为例子。
翻转翻转链表，可以一边遍历同时用一个临时变量记录当前元素的下一个元素的指针所指向的位置，然后再将当前元素的下一个元素的指针指向自己。
下图是以长度为5的链表，翻转链表为例子。
例题1.LeetCode.反转链表题意
给单链表的头节点head，请反转链表，并返回反转后的链表。
示例
输入：head=[1,2,3,4,5]输出：[5,4,3,2,1]
题解
按上述链表翻转操作思路实现代码。
代码
publicListNodereverseList(ListNodehead){//pre存的是当前节点的上一个节点ListNodeprev=null;//curr存的是当前链表遍历到节点ListNodecurr=head;while(curr!=null){//next存的是当前节点下一个节点ListNodenext=curr.next;curr.next=prev;prev=curr;curr=next;}returnprev;}习题推荐LeetCode.删除链表中的节点LeetCode21.合并两个有序链表LeetCode.相交链表栈和队列栈
栈被限定必须在栈顶进行插入和删除操作，因此其特点为是后进先出。
下图是栈的插入(入栈)、删除(出栈)示意图。
队列队列被限定在队头进行删除操作，队尾进行插入操作，因此其特点为先进先出。
下图是队列的插入(入队)、删除(出队)示意图。
基本操作栈和队列的插入和删除操作上图已解释。
例题LeetCode.最小栈题意设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。
push(x)——将元素x推入栈中。pop()——删除栈顶的元素。top()——获取栈顶元素。getMin()——检索栈中的最小元素。示例
输入：["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]]输出：[null,null,null,null,-3,null,0,-2]解释：MinStackminStack=newMinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin();--返回-3.minStack.pop();minStack.top();--返回0.minStack.getMin();--返回-2.
题解
建一个辅助栈，辅助栈的栈顶表示原栈所有数字最小值，下面分别讨论题目要求的四种操作，如何实现。
push(x):若插入的数字小于等于辅助栈的栈顶元素，则这个数字在原栈是最小值(之一)，我们将其插入辅助栈中。pop():若原栈删除的数字等于辅助栈的栈顶元素，则这个数字在原栈是最小值(之一)，我们同时原栈和辅助栈的栈顶元素；反之，只删除原栈栈顶元素。top():返回原栈的栈顶元素。getMin():返回辅助栈的栈顶元素。代码
classMinStack{publicStackIntegers,min_s;publicMinStack(){s=newStack();min_s=newStack();}publicvoidpush(intx){s.push(x);if(min_s.isEmpty()
x=min_s.peek())min_s.push(x);}publicvoidpop(){if(s.pop().equals(min_s.peek()))min_s.pop();}publicinttop(){returns.peek();}publicintgetMin(){returnmin_s.peek();}}
大家会了吗？