1.定义
栈：后进先出（LIFO-last in first out）:最后插入的元素最先出来。
队列：先进先出（FIFO-first in first out）:最先插入的元素最先出来。
2.用数组实现栈和队列
实现栈：
由于数组大小未知，如果每次插入元素都扩展一次数据（每次扩展都意味着构建一个新数组，然后把旧数组复制给新数组），那么性能消耗相当严重。
这里使用贪心算法，数组每次被填满后，加入下一个元素时，把数组拓展成现有数组的两倍大小。
每次移除元素时，检测数组空余空间有多少。当数组里的元素个数只有整个数组大小的四分之一时，数组减半。
为什么不是当数组里的元素个数只有整个数组大小的四分之一时，数组减半？考虑以下情况：数组有4个元素，数组大小为4个元素空间。此时，加一个元素，数组拓展成8个空间；再减一个元素，数组缩小为4个空间；如此循环，性能消耗严重。
具体代码（Java）:
public ResizingArrayStackOfStrings() { s=new String[1];
int N = 0; } pubilc void Push(String item) { //如果下一个加入元素超出数组容量，拓展数组 if(N == s.length) Resize(2 * s.length); s[N++] = item; } private void Resize(int capacity) { String[] copy = new String[capacity]; //将旧数组元素复制给新数组 for(int i=0; i<N; i++) copy[i] = s[i]; s = copy; } public String Pop() { String item = s[--N]; s[N] = null; //剩余元素只占数组四分之一空间时，数组减半 if(N>0 && N=s.length/4) Resize(s.length/2); return item; }
效果如下图：
实现队列
与栈类似：
数组每次被填满后，加入下一个元素时，把数组拓展成现有数组的两倍大小。
每次移除元素时，检测数组空余空间有多少。当数组里的元素个数只有整个数组大小的四分之一时，数组减半。
不同之处在于：
由于是先进先出，移除是从队列的最前端开始的。所以队列数据是存储在数组的中间部分。令队列数据的尾端数据ID为Num,首端数据ID为HeadIndex，则Num - HeadIndex为队列数据元素个数。
当队列数据元素个数为整个数组空间的四分之一时，数组减半，且队列数据左移至数组最左端。即Num-=HeadIndex；HeadIndex=0；
图中，HeadIndex=2；Num=5；
具体代码：
.h: UCLASS() class ALGORITHM_API AStackAndQueuesExerciseTwo : public AActor { GENERATED_BODY() public: // Sets default values for this actor's properties AStackAndQueuesExerciseTwo(); // Called every frame virtual void Tick(float DeltaTime) override; //输入 void Enqueue(int Input); //重构数组（拓展或缩小） void Resize(int Capacity); //输出且移除 int Dequeue(); //队列里没元素了？ bool IsEmpty(); protected:
