首页 > 代码库 > 基础算法（二）——队列

基础算法（二）——队列

2024-11-24 13:10:02   203人阅读

 队列（queue）在计算机科学中，是一种先进先出的线性表。它只允许在表的前端进行删除操作，而在表的后端进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。  
——来自360百科
 
队列的储存：（大体的结构可以用数组或者链表来实现）一般有两个指针，允许插入的一端焦作队尾（rear），允许删除的一端叫作队头（head），如图1-2所示：
技术分享
图1-2
 
队列设置的一种参考程序（部分）：
var
  Head,tail:longint;
  Doute:array[1..100000]of longint;
Begin
  head:=x;
  tail:=y;
  read……;
...
End. 
对于队列，一般有如下的操作：
1. 入队
2. 出队
3. 判断队列是否为空
【参考模板】
（1）初始化
Procedure c1;
begin
  head:=0;
  tail:=0;
end;
（2）入队
Procedure c2(x:nultype);
begin
  inc(tail);
  doute[tail]:=x;
end;
（3）出队
Procedure c3;
begin
  inc(head);
end;
在操作的时候，两个指针要随时观察、移动。
【重点】假溢出：读图1-3理解何为假溢出：
技术分享先介绍一下循环队列：将普通的队列的首位相连，即可以叫做循环队列，如图1-4
技术分享

观察图1-5，1-6后理解：如何应对假溢出？
一般的，对付这种情况有如下的方法：
1)采用循环队列；
2)按最大可能的进队操作次数设置顺序队列的最大元素个数；
3)修改出队算法，使每次出队列后都把队列中剩余数据元素向队头方向移动一个位置；
4)修改入队算法，增加判断条件，当假溢出时，把队列中的数据元素向对头移动，然后方完成入队操作。 
【例】细胞（cell.pas/c/cpp）
【问题描述】一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如:阵列
 0234500067
 1034560500
 2045600671
 0000000089
中有4个细胞。
【输入】 输入共m+1行 (1<=m<=100, (1<=n<=100)第一行有两个数据，分别表示总行数和总列数以下的m行，每行有n个0-9之间的数
【输出】细胞个数
【样例】
Input：
4  10
0234500067
1034560500
2045600671
0000000089
Output：
4
【参考程序】

const
dx:array[1..4]of longint=(0,-1,0,1);
dy:array[1..4]of longint=(1,0,-1,0);
var
n,m,i,j,tj:longint;
a:array[-10..100,-10..100]of boolean;
x:char;
state:array[0..4000,0..4000]of longint;


procedure bfs(x,y:longint);
var
head,tail,i:longint;
begin
    inc(tj);
    a[x,y]:=false;
    head:=0;tail:=1;
    state[1,1]:=x;state[1,2]:=y;
    repeat
         inc(head);
         for i:=1 to 4 do
         begin
             x:=state[head,1]+dx[i];
             y:=state[head,2]+dy[i];
             if (x>0)and(x<=m)and(y>0)and(y<=n)and(a[x,y]=true) then
             begin
                 inc(tail);
                 state[tail,1]:=x;
                 state[tail,2]:=y;
                 a[x,y]:=false;
             end;
         end;
    until head>=tail;
end;


begin
    readln(m,n);
    fillchar(a,sizeof(a),true);
    for i:=1 to m do
    begin
        for j:=1 to n do
        begin
            read(x);
            if x=‘0‘ then a[i,j]:=false;
        end;
        readln;
    end;
    for i:=1 to m do
    for j:=1 to n do
    if a[i,j]=true then bfs(i,j);
    write(tj);
end.

// （该程序由网上搜集，要用到BFS，找到一个细胞后就进行BFS操作即可）

基础算法（二）——队列


联系
我们