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:
// Called when the game starts or when spawned
virtual void BeginPlay() override; public: private:
//记录数组中有多少个Int
int Num;
//队列数组
TArray<int> MyIntArray;
//记录下一个移除的数据ID
int HeadIndex;
}; .cpp: AStackAndQueuesExerciseTwo::AStackAndQueuesExerciseTwo()
{
// Set this actor to call Tick() every frame. You can turn this off to improve performance if you don't need it.
PrimaryActorTick.bCanEverTick = true;
//一开始数组没成员
Num = ;
HeadIndex = ;
//数组中有一个假元素
MyIntArray.Add();
} // Called when the game starts or when spawned
void AStackAndQueuesExerciseTwo::BeginPlay()
{
Super::BeginPlay();
//测试
Enqueue();
Enqueue();
Enqueue();
Enqueue();
Enqueue();
Dequeue();
Dequeue();
Dequeue();
//队列数组成员
for (int i = HeadIndex; i < Num; i++)
{
UKismetSystemLibrary::PrintString(this, "i: " + FString::FromInt(i) + " End: " + FString::FromInt(MyIntArray[i]));
}
//队列数组的容量
UKismetSystemLibrary::PrintString(this, "MyIntArray.Num(): " + FString::FromInt(MyIntArray.Num()));
} // Called every frame
void AStackAndQueuesExerciseTwo::Tick(float DeltaTime)
{
Super::Tick(DeltaTime); } void AStackAndQueuesExerciseTwo::Enqueue(int Input)
{
//如果队列数组已满，拓展数组
if (Num == MyIntArray.Num())
{
Resize( * MyIntArray.Num());
}
//拓展或者数组有空位时，添加元素
if (Num < MyIntArray.Num())
{
MyIntArray[Num] = Input;
}
Num++;
} void AStackAndQueuesExerciseTwo::Resize(const int Capacity)
{
//int a[] = new int[Capacity];
TArray<int> Copy;
//添加数个假元素填充数组
for (int i = ; i < Capacity; i++)
{
Copy.Add();
}
//将队列数组赋值给Copy数组，如果是缩小数组，则把队列数组左移，节省空间
for (int i = HeadIndex; i < Num; i++)
{
Copy[i - HeadIndex] = MyIntArray[i];
}
MyIntArray = Copy;
} int AStackAndQueuesExerciseTwo::Dequeue()
{
//判断数组是否为空
if (IsEmpty())
{
UKismetSystemLibrary::PrintString(this, "No Element Exist!!!");
return ;
}
else
{
UKismetSystemLibrary::PrintString(this, "Dequeue: " + FString::FromInt(MyIntArray[HeadIndex]));
}
HeadIndex++;
//如果移除元素后，所剩元素为数组空间的四分之一，则数组减半
if ((Num - HeadIndex) != && (Num - HeadIndex) == (MyIntArray.Num() / ))
{
Resize(MyIntArray.Num() / );
//移除空间后，队列数组左移，节省空间
Num -= HeadIndex;
HeadIndex = ;
return MyIntArray[HeadIndex];
}
else
{
return MyIntArray[HeadIndex - ];
} }
//如果下一个要移除的数据不存在，则为空数组
bool AStackAndQueuesExerciseTwo::IsEmpty()
{
return HeadIndex >= Num;
}