swift&C双语版算法之队列、栈、链表

队列

队列是一种特殊的线性结构，它只允许在队列的首部(head)进行删除操作，这称为“出队”，而在队列的尾部(tail)进行插入操作，这称为“入队”。当队列中没有元素时(即head==tail)，称为空队列。队列遵循“先进先出”(first in first out)原则。
举一个解密qq号的队列操作例子：给定一串数字，首先将第一个数删除，紧接着将第二个数放到这个数的末尾，再将第三个数删除并将第四个书放到这串数的末尾，直至最后一个数删除。按照刚才删除的顺序，把这些删除的数连在一起就是解密后的qq号。

• swift

<pre>
//队列
struct queue {
var data:[Int] = Array.init()
var head:Int = 0
var tail:Int = 0
}
var aQueue = queue()
aQueue.data = [6,3,1,7,5,8,9,2,4]
aQueue.head = aQueue.data.startIndex
aQueue.tail = aQueue.data.endIndex
aQueue.data = aQueue.data + Array.init(repeatElement(0, count: 100))
var array:[Int] = Array.init()
while aQueue.head < aQueue.tail {
array.append(aQueue.data[aQueue.head])
aQueue.head += 1

aQueue.data[aQueue.tail] = aQueue.data[aQueue.head]
aQueue.tail += 1
aQueue.head += 1

}
print(array) //[6, 1, 5, 9, 4, 7, 2, 8, 3]
</pre>

• c
  <pre>
  struct queue {
  int data[100]; //队列的主体，存储数据
  int head; //队首
  int tail; //队尾
  };

int* decryptionQQ(int num[],int count)
{

//创建队列并从对尾插入数据
struct queue q;
q.head = 1;
q.tail = 1;

for (int i = 0; i<count; i++) {
    q.data[q.tail] = num[i];
    q.tail++;
}

for (int i = 0; i<count; i++) {
    num[i] = q.data[q.head];
    q.head++;
    
    q.data[q.tail] = q.data[q.head];
    q.tail++;
    q.head++;
}
return num;

}
</pre>

栈

栈是一种限定为只能在一端进行插入和删除操作的后进先出的数据结构。

swift

<pre>
//栈的应用--回文字符串的判定
func stringCheck(string:String) -> Bool {
if string.isEmpty {
return false
}

var stack:[Character] = Array.init()

let mid:Int = string.characters.count / 2

let midIndex = string.index(string.startIndex, offsetBy: mid)
let leftString = string.substring(to: midIndex)
var rightString = String.init()

if string.characters.count % 2 == 0 {
    let midRightIndex = midIndex
    rightString = string.substring(from: midRightIndex)
} else {
    let midRightIndex = string.index(string.startIndex, offsetBy: mid + 1)
    rightString = string.substring(from: midRightIndex)
}

for character in leftString.characters {
    stack.append(character)
}

var top = stack.count - 1

for character in rightString.characters {
    if character != stack[top]{
        return false
    }
    
    top -= 1
}

return true

}

print(stringCheck(string: "xyzzyx")) //true
</pre>

链表

链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量，以head表示，它存放一个地址。该地址指向一个元素。链表中 每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。因此，head指向第一个元素：第一个元素又指向 第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。

swift

<pre>
//链表节点
class listNode {
var value:Int
var next:listNode?

init(_ val:Int) {
    self.value = val
    self.next = nil
}

}
</pre>

<pre>
//链表
class linkList {
var head:listNode?
var tail:listNode?

//尾插法
func appendTail(value:Int) {
    if tail == nil {
        tail = listNode.init(value)
        head = tail
    } else {
        tail!.next = listNode.init(value)
        tail = tail!.next
    }
}

}
</pre>

<pre>
//链表的创建
let list = [2,3,5,8,9,10,18,26,32]
var link:linkList = linkList.init()
for value in list {
link.appendTail(value: value)
}
</pre>

<pre>
//链表的插入
var aNode = link.head
let num = 20
while aNode != nil {

if (aNode?.next == nil) || (aNode?.next?.value > num) {
    
    var insertNode = listNode.init(num)

    insertNode.next = aNode?.next
    aNode?.next = insertNode
    break
}

aNode = aNode?.next

}
</pre>

<pre>
//链表的打印
var abNode = link.head
while abNode != nil {
print(abNode?.value)
abNode = abNode?.next
}
</pre>