数据结构--队列

发表于 | 分类于 | 阅读次数: |
字数统计: 1.2k

一：介绍队列

队列是一个有序列表，可以用数组或是链表来实现。

遵循先入先出的原则。即：现存入队列的数据，要先取出。后存入的要后去除

1573570155193

二：数组模拟队列

  • 队列本身就是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中maxSize是该队列的最大容量
  • 因为队列的输出、输入是分布从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入二改变
  • rear是队列最后【含】
  • front是队列最前元素【不含】

1573570155193

当我们将数据存入队列时称为“addQueue”,addQueue的处理需要2个步骤：

将尾指针往后移:rear+1,当front==rear[空]

若尾指针rear小于队列的最大下标maxSize-1,则将数据存入rear所指定的数组元素中，否则无法存入数据。rear==maxSize-1[队列满] 

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
public class AarrayQueue
   {
       //使用数组模拟队列
       private int maxSize;//表示数组最大容量
       private int front;//指向队列头
       private int rear;//队列尾
       private int[] arr;//该数组存放数据，模拟队列
       //创建队列的构造器
       public AarrayQueue(int arrMaxSize)
       {
           maxSize = arrMaxSize;
           arr = new int[maxSize];
           front = -1;//指向队列的头部的前一个位置[不包含]
           rear = -1;//指向队列的尾部[包含]
       }
       //判断队列是否满
       public bool isFull()
       {
           return rear == maxSize - 1;
       }
       //判断队列是否为空
       public bool isEmpty()
       {
           return rear == maxSize;
       }
       //添加数据到队列
       public void addQueue(int n)
       {
           if (isFull())
           {
               Console.WriteLine("队列已经满了！");
           }
           else
           {
               rear++;
               arr[rear] = n;
           }
       }
       //获取数据出队列
       public int getQueue()
       {
           if (isEmpty())
           {
               throw new Exception("队列已经满了");
           }
           else
           {
               return arr[rear--];
           }
       }
       //显示队列的所有数据
       public void showQueue()
       {
           if (isEmpty())
           {
               Console.WriteLine("当前队列是空的，没有数据！");
           }
           for (int i = 0; i < maxSize; i++)
           {
               Console.Write(arr[i]+"\t");
           }
       }
       //显示队列的头数据，
       public int headQueue()
       {
           if (isEmpty())
           {
               throw new Exception("队列是空的");
           }
           else
           {
               return arr[front+1];
           }
       }
       //显示队列的尾数据
       public int footQueue()
       {
           if (isEmpty())
           {
               throw new Exception("队列是空的");
           }
           else
           {
               return arr[rear];
           }
       }
   }

三：数组模拟环形队列

思路：

  • front变量的含义做一个调整：front就指向队列的第一个元素，arr[front]就是队列的第一个元素，front初始值=0。
  • real变量的含义做一个调整：real指向队列的最后一个元素的后一位置，因为希望空出一个空间做为约定，real初始值=0。
  • 当队列满的时候，条件改为 (real+1)%maxSize==front[满]
  • 当队列为空的条件，rear==front[空]
  • 队列的有效的数据的个数(real+maxSize-front)%maxSzie
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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace demo2
{
   public class CircleArrayQueue
    {
        //使用数组模拟队列
        private int maxSize;//表示数组最大容量
        private int front;//front就指向队列的第一个元素
        private int rear;//real指向队列的最后一个元素的后一位置
        private int[] arr;//该数组存放数据，模拟队列

        public CircleArrayQueue(int arrMaxSize)
        {
            maxSize = arrMaxSize;
            arr = new int[maxSize];
        }
        //判断队列是否满
        public bool isFull()
        {
            return (rear + 1) % maxSize == front;
        }
        //判断队列是否为空
        public bool isEmpty()
        {
            return rear == front;
        }
        //添加数据到队列
        public void addQueue(int n)
        {
            if (isFull())
            {
                Console.WriteLine("队列已经满了！");
            }
            else
            {
                arr[rear] = n;
                //将readl后移
                rear = (rear + 1) % maxSize;
            }
        }

        //获取数据出队列
        public int getQueue()
        {
            if (isEmpty())
            {
                throw new Exception("队列已经满了");
            }
            else
            {
                //这里需要分析出front是指向队列的第一个元素
                //1.先把front对应的值保存到一个临时变量
                //2.将front后移,考虑取莫
                //3.将临时保存的变量返回
                int temp = arr[front];
                front = (front + 1) % maxSize;
                return temp;
            }
        }
        //显示队列的所有数据
        public void showQueue()
        {
            if (isEmpty())
            {
                Console.WriteLine("当前队列是空的，没有数据！");
            }
            //思路，从front开始变量，变量多少个元素
            for (int i = front; i < front+ size(); i++)
            {
                Console.Write(arr[i%maxSize] + "\t");
            }
            Console.WriteLine("");
        }
        //求当前数组的有效个数
        public int size()
        {
            return (rear + maxSize - front) % maxSize;
        }
        //显示队列的头数据，
        public int headQueue()
        {
            if (isEmpty())
            {
                throw new Exception("队列是空的");
            }
            else
            {
                return arr[front];
            }
        }
        //显示队列的尾数据
        public int footQueue()
        {
            if (isEmpty())
            {
                throw new Exception("队列是空的");
            }
            else
            {
                return arr[size()-1];
            }
        }
    }
}

四：源码地址

https://github.com/zc282840325/DataStructure/tree/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E9%98%9F%E5%88%97