如何实现一个高效的队列

发表于 | 更新于: | 分类于 | | 阅读次数:

1 队列简介

队列(Queue)
是运算受限的线性表。一种先进先出(First In First Out ，简称FIFO)的线性表。只允许在表的一端进行插入，而在另一端进行删除。先进先出 是队列特有的性质。


举例来说

  • 我们购买东西需要排队，而这个排好的队伍就是队列。先来的人可以先买到东西离开。
  • 乘坐电动扶梯时，乘客都是从扶梯的一头进入，另一头离开电梯。先上电梯的乘客，先下电梯。


队列示意图

2 逻辑与实现

2.1 队列的基本功能

理解完队列概念，再来列出队列具有的功能：

  • 插入

    向队列 队尾 增加一个对象。

  • 弹出

    从队列 队首 弹出一个对象。

  • 计数

    计算当前队列中数据的总个数。

2.2 队列的需要的变量

好了，功能也有了，现在来更具这些功能来准备准备我们的材料：

  • 单位容量 FCapacity

    总要告诉内存你每次打算征用人家多少区域来给你排队用吧。

  • 一块内存 FMem

    更具你的单位容量，去申请‘场地’来排队用，用完了再来申请。

  • 队尾计数器 FPopIndex

    有了它，你就知道你在队伍里排的多少号了。

  • 队首计数器 FPushIndex

    有了它，你就只当队伍最前面的人拍的是几号了。

2.3 队列实现

2.3.1 初始化

先来初始化队列，设置容量并重置计数器。

1
2
3
4
5
6
7
8
9
PageCapacity = 7;
//初始化 计数器
FPushIndex = 0;
FPopIndex = 0;
//更具容量申请 固定大小的空间
SetLength(FMem, PageCapacity);
FCapacity = PageCapacity;

这里写图片描述

2.3.2 载入数据

向队列加载数据时，队尾计数器自加，自加后如果发现 排号和容量大小一样了，说明空间不够了，就向商场（内存）申请连续的扩容空间（已用空间大小+单位容量）

1
2
3
4
5
6
7
8
9
10
//新来的元素放到空间末尾
FMem[FPushIndex] = NewItem;
//每加载一个新的元素进来，都要增加FPushIndex
FPushIndex = FPushIndex + 1;
//这里还需要保证 队尾 计数器始终小于 总容量 ，否则 要扩容
if (FPushIndex >= FCapacity)
  SetLength(FMem, FCapacity+ PageCapacity);
  FCapacity = FCapacity + PageCapacity;

载入队列

2.3.3 弹出数据

好了，现在队伍有了，该卖东西了，正真的队伍是卖一个走一个，所以我们按照号码(内存下标)来叫号卖。

1
2
3
4
//按照 队首 下标开始 获取元素( FPopIndex 前提小于 排队人数 FPushIndex )
if FPopIndex < FPushIndex
  PopItem = FMem[FPopIndex];  
  FPopIndex = FPopIndex + 1;    //每弹出一个元素，都要增加FPopIndex

弹出数据

弹出数据的过程中也会有新的数据来加载，但是不影响我们改变内存的规律：

  • 载入数据
    • 直接将数据放到队列末尾
    • 队尾计数器 +1
    • 判断内存是否足够
  • 弹出数据
    • 拿出队首计数器指向数据
    • 队首计数器 +1

加载并弹出数据

2.4 代码实现

废话说了这么多，好了贴代码。
代码功能说明：

  • 基本功能
    • 载入功能
    • 弹出功能
    • 清空队列功能
    • 队列计数功能
    • 自动扩容功能
  • 拓展功能
    • 为了线程安全，使用临界区加锁控制
    • 字符串加载/弹出功能
    • 容量设置功能

代码如下：

.\FastQueue.pas
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
unit FastDemo;
interface
//线程安全版本
uses
  Windows, SysUtils;
const
  CONST_BYTE_SIZE = 4;
  CONST_PAGE_SINGLE = 1024;
  COSNT_PAGE_SINGLE_SIZE = CONST_PAGE_SINGLE * CONST_BYTE_SIZE;
type
  TFastQueue = class
  private
    FCS: TRTLCriticalSection;
    //
    FMem: Pointer;
    FTmpMem: Pointer;
    //
    FPushIndex: Integer;                //压入队列计数器
    FPopIndex: Integer;                 //弹出队列计数器
    FCapacity: Integer;                 //队列容量，始终大于 FPushIndex
    //
    procedure Lock();
    procedure UnLock();
    procedure SetCapacity(const AValue: Integer);
    //
    procedure setSynCapacity(const AValue: Integer);
    function getSynCapacity: Integer;
    function getSynCurCount: Integer;
  public
    constructor Create(AInitCapacity: Integer = CONST_PAGE_SINGLE);
    destructor Destroy(); override;
    //
    function Push(AItem: Pointer): Pointer;
    function Pop(): Pointer;
    function PushString(AItem: string): Pointer;
    function PopString(): string;
    procedure Clear;
  public
    property Capacity: Integer read getSynCapacity write setSynCapacity;
    property Count: Integer read getSynCurCount;
  end;
implementation
{ TFastQueue }
constructor TFastQueue.Create(AInitCapacity: Integer);
begin
  InitializeCriticalSection(FCS);
  FPushIndex := 0;
  FPopIndex := 0;
  if AInitCapacity < CONST_PAGE_SINGLE then
    AInitCapacity := CONST_PAGE_SINGLE;
  SetCapacity(AInitCapacity);
end;
destructor TFastQueue.Destroy;
begin
  FreeMem(FMem);
  if FTmpMem <> nil then
    FreeMem(FTmpMem);
  DeleteCriticalSection(FCS);
  inherited;
end;
procedure TFastQueue.Lock;
begin
  EnterCriticalSection(FCS);
end;
procedure TFastQueue.UnLock;
begin
  LeaveCriticalSection(FCS);
end;
procedure TFastQueue.SetCapacity(const AValue: Integer);
var
  vPageCount, vOldSize, vNewSize: Integer;
begin
  if AValue > FCapacity then
  begin
    if FTmpMem <> nil then
      FreeMem(FTmpMem);
    vPageCount := AValue div CONST_PAGE_SINGLE;
    if (AValue mod CONST_PAGE_SINGLE) > 0 then
      Inc(vPageCount);
    //保存旧的容量
    vOldSize := FCapacity * CONST_BYTE_SIZE;
    //计算新的容量
    FCapacity := vPageCount * CONST_PAGE_SINGLE;
    vNewSize := FCapacity * CONST_BYTE_SIZE;
    //扩容
    GetMem(FTmpMem, vNewSize);
    FillChar(FTmpMem^, vNewSize, #0);
    //转移数据
    if FMem <> nil then
    begin
      Move(FMem^, FTmpMem^, vOldSize);
      FreeMem(FMem);
    end;
    FMem := FTmpMem;
    //FTmpMem （保证弹出、插入数据时使用） 与 FMem 大小一致
    GetMem(FTmpMem, vNewSize);
  end;
end;
function TFastQueue.Push(AItem: Pointer): Pointer;
var
  vPMem: PInteger;
  vNextPriority, vPriority, vIndex: Integer;
  vNotPushed: boolean;
begin
  Lock();
  try
    vPMem := PInteger(FMem);
    Inc(vPMem, FPushIndex);
    vPMem^ := Integer(AItem);
    Inc(FPushIndex);
    //检测栈容量是否足够（至少保留一位空位，否则扩容 1024）
    if FPushIndex >= FCapacity then
    begin
      SetCapacity(FCapacity + CONST_PAGE_SINGLE);
    end;
  finally
    UnLock();
  end;
end;
function TFastQueue.Pop: Pointer;
  procedure MoveMem();
  var
    vvPSrc: PInteger;
    vvTmpMem: Pointer;
  begin
    FillChar(FTmpMem^, FCapacity * CONST_BYTE_SIZE, #0);
    vvPSrc := PInteger(FMem);
    Inc(vvPSrc, FPopIndex);
    Move(vvPSrc^, FTmpMem^, (FCapacity - FPopIndex) * CONST_BYTE_SIZE);
    //交换指针
    vvTmpMem := FMem;
    FMem := FTmpMem;
    FTmpMem := vvTmpMem;
  end;
var
  vPMem: PInteger;
begin
  Lock();
  try
    Result := nil;
    if (FPopIndex = FPushIndex) then
      Exit;
    // 1.获取弹出元素
    vPMem := PInteger(FMem);
    Inc(vPMem, FPopIndex);
    Result := Pointer(vPMem^);
    // 2.弹出元素后 弹出计数器 +1
    Inc(FPopIndex);
    // 3.队列底部空余内存达到 1024 整体迁移
    if FPopIndex = CONST_PAGE_SINGLE then
    begin
      //迁移数据
      MoveMem();
      //重置弹出位置
      FPopIndex := 0;
      //减少压入队列的数量
      Dec(FPushIndex, CONST_PAGE_SINGLE);
    end;
  finally
    UnLock();
  end;
end;
function TFastQueue.PushString(AItem: string): Pointer;
var
  vPChar: PChar;
begin
  vPChar := StrAlloc(256);
  StrCopy(vPChar, pchar(AItem + '   |' + inttostr(FPushIndex)));
  Push(vPChar);
end;
function TFastQueue.PopString: string;
var
  vPChar: PChar;
begin
  Result := 'nil';
  vPChar := Pop;
  if vPChar <> '' then
  begin
    Result := vPChar;
    StrDispose(vPChar);
  end;
end;
procedure TFastQueue.Clear;
begin
  Lock();
  try
    FPushIndex := 0;
    FPopIndex := 0;
    SetCapacity(CONST_PAGE_SINGLE);
  finally
    UnLock();
  end;
end;
procedure TFastQueue.setSynCapacity(const AValue: Integer);
begin
  Lock();
  try
    SetCapacity(AValue);
  finally
    UnLock();
  end;
end;
function TFastQueue.getSynCapacity: Integer;
begin
  Lock();
  try
    Result := FCapacity;
  finally
    UnLock();
  end;
end;
function TFastQueue.getSynCurCount: Integer;
begin
  Lock();
  try
    Result := FPushIndex - FPopIndex;
  finally
    UnLock();
  end;
end;
end.

2.5 使用Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
procedure UseFastQueue();
var
  vQueue: TFastQueue;
begin
  vQueue := TFastQueue.Create;
  try
    vQueue.Push('A1');
    vQueue.Push('A2');
    vQueue.Push('A3');
    vQueue.Push('A4');
    vQueue.Push('A5');
    vQueue.Push('A6');
    while vQueue.Count > 0 do
    begin
      OutputDebugString(vQueue.PopString);
    end;
  finally
    vQueue.Free;
    vQueue := nil;
  end;
end;

输出:

A1
A2
A3
A4
A5

如果觉得我的文章对您有用，请随意打赏。您的支持将是我继续创作的动力！