队列

队列的抽象数据类型描述

具有一定操作约束的线性表,只能在一端插入,而在另一端删除

  • 数据插入:入队
  • 数据删除:出队
  • 先进先出(FIFO)

类型名称:队列(Queue)

数据对象集:一个有0个或多个元素的有穷线性表

操作集

  • 创建空队列
  • 判读队列是否已满
  • 插入元素
  • 队列是否为空
  • 将队列头部元素删除并返回

队列的顺序存储实现

队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成

 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

swift的特性不适合描述一个数组实现的队列,故采用老师提供的C语音实现

#define MaxSize <储存数据元素的最大个数> 
struct QNode {
    ElementType Data[ MaxSize ]; 
    int rear;
    int front;
};
typedef struct QNode *Queue;

void AddQ( Queue PtrQ, ElementType item) {
    if ( (PtrQ->rear+1) % MaxSize == PtrQ->front ) { 
        printf(“队列满”);
        return;
    }
    PtrQ->rear = (PtrQ->rear+1)% MaxSize; 
    PtrQ->Data[PtrQ->rear] = item;
}

ElementType DeleteQ ( Queue PtrQ ) {
    if ( PtrQ->front == PtrQ->rear ) { 
        printf(“队列空”);
        return ERROR;
    } else {
        PtrQ->front = (PtrQ->front+1)% MaxSize; 
        return PtrQ->Data[PtrQ->front];
    } 
}

队列的链式存储实现

队列的链式存储结构也可以用一个单链表实现,插入和删除操作分别在链表的两头进行.

 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

class QueueNode<T:Hashable> : Equatable {
    static func == (lhs: QueueNode<T>, rhs: QueueNode<T>) -> Bool {
        if lhs.data == rhs.data && lhs.next == rhs.next {
            return true
        }
        else {
            return false
        }
    }
    
    var data : T?
    var next : QueueNode<T>?
    
}

class Queue<T:Hashable> {
    var rear : QueueNode<T>?
    var front : QueueNode<T>?
    
    func isEmpty() -> Bool {
        if rear == nil && front == nil {
            return true
        }
        else {
            return false;
        }
    }
    
    func add(item:T) -> Void {
        let node = QueueNode<T>()
        node.data = item
        
        if isEmpty() {
            rear = node
            front = node
            return
        }
        
        rear!.next = node
        rear = node
    }
    
    func delete() -> T? {
        if isEmpty() {
            print("队列空")
            return nil
        }
        
        if front == rear {
            let data = front!.data
            front = nil
            rear = nil
            return data
        }
        
        let data = front?.data
        front = front?.next
        return data
    }
}

let q = Queue<String>()
q.add(item: "aaaa")
q.add(item: "bbbb")
print(q.rear?.data)
print(q.front?.data)
print(q.delete())
print(q.rear?.data)
print(q.front?.data)
q.add(item: "cccc")
print(q.rear?.data)
print(q.front?.data)
print(q.delete())
print(q.delete())
print(q.delete())