1. 概述

栈和队列都属于线性表，它们均可使用顺序或链式来实现。二者之间的比较：
image.png

栈与队列在开发中的实际应用场景：
image.png

1.1 栈

栈（Stack）：一个有穷线性数据结构，具有后进先出（LIFO）的特性

栈中元素从栈顶（top）压入，也从栈顶弹出

栈的操作：

  • isFull：判断栈是否已满

  • isEmpty：判断是否为空栈

  • push：将元素压栈，添加元素到栈顶

  • pop：将元素出栈，删除栈顶元素

新添加的元素永远存储在栈顶，而删除的也永远是栈顶元素，所以栈是后进先出的数据结构。而栈的top指针，只要是非空栈，它会永远指向栈顶元素
image.png

栈的top指针在压栈和出栈时，会跟随栈中的数据时时变化。如果是空栈，则top = -1
image.png

1.2 队列

队列（Queue）：有穷线性数据结构，具有先进先出（FIFO）的特性

队列中的元素，从队尾（rear）入队，从队头（front）出队
image.png

队列的操作：

  • isFull：判断栈是否已满

  • isEmpty：判断是否为空栈

  • enqueue：将元素入队，添加到队列的队尾

  • dequeue：将元素出队，删除队头的元素

一般来说，空队列的front和rear都为0，而非空队列front指向队头，rear指向队尾的下一个元素

当出队速度大于入队速度，会产生“假溢出”问题。使用循环队列，可以充分利用向量空间，克服“假溢出”现象

循环队列永远不能让它的头尾相遇，否则通过front == rear将无法区分队列是满或是空

正确的做法，可以牺牲队列中一个存储单元，当front == rear表示队列为空，而(rear + 1) % MAXSIZE == front，则表示队列已满

2. 用栈实现队列

请使用两个栈实现先进先出队列，只能使用标准的栈操作是合法的。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）

实现MyQueue类：

  • void push(int x)：将元素x推到队列的末尾

  • int pop()：从队列的开头移除并返回元素

  • int peek()：返回队列开头的元素

  • boolean empty()：如果队列为空，返回 true。否则，返回 false

示例：

  1. MyQueue myQueue = new MyQueue();
  2. myQueue.push(1); // queue is: [1]
  3. myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
  4. myQueue.peek(); // return 1
  5. myQueue.pop(); // return 1, queue is [2]
  6. myQueue.empty(); // return false

使用pushStack和popStack两个栈，实现队列的特性。入队逻辑非常简单，永远只会往pushStack中push数据。而出队逻辑相对复杂，因为要符合队列先进先出的特性

让popStack负责pop操作，由于数据都被push到pushStack中，所以popStack为空栈，我们先将pushStack中的数据导入到popStack中。此时，数据在popStack中的顺序会改变，原本先入栈的数据会存储在栈顶

所以，只要popStack为空栈，我们就先从pushStack中导入数据，然后再pop数据。否则，只要popStack不为空栈，直接从中pop数据即可

切记，只要popStack为非空栈，就不能从pushStack中导入新的数据，因为会破坏popStack的先进先出结构

代码实现：

  1. class MyQueue {
  3.     fileprivate var pushStack : LinkedStack<Int>;
  4.     fileprivate var popStack : LinkedStack<Int>;
  6.     init() {
  7.         pushStack = LinkedStack<Int>();
  8.         popStack = LinkedStack<Int>();
  9.     }
  11.     func enter(x : Int){
  12.         pushStack.push(element: x);
  13.     }
  15.     func out() -> Int?{
  17.         let front = peek();
  19.         if(front == nil){
  20.             return front;
  21.         }
  23.         return popStack.pop();
  24.     }
  26.     func peek() -> Int?{
  27.         if(isEmpty()){
  28.             return nil;
  29.         }
  31.         if(popStack.isEmpty()) {
  33.             while(!pushStack.isEmpty()){
  34.                 popStack.push(element: pushStack.pop()!);
  35.             }
  36.         }
  38.         return popStack.getTop();
  39.     }
  41.     func isEmpty() -> Bool {
  43.         if(popStack.isEmpty() && pushStack.isEmpty()){
  44.             return true;
  45.         }
  47.         return false;
  48.     }
  49. }

  • 时间复杂度：入队操作O(1)，出队操作O(1)

  • 空间复杂度：O(n)

单次出队操作，可能需要先进行数据的导入。这种情况操作代价可能很大，但是最大执行次数跟它之前执行过入队操作的次数有关，并且在导入的数据全部出队之前，不会再触发这种最坏的情况。所以平均复杂度应为O(1)

3. 用队列实现栈

请使用两个队列实现一个后进先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop、empty）。

实现MyStack类：

  • void push(int x)：将元素x压入栈顶

  • int pop()：移除并返回栈顶元素

  • int top()：返回栈顶元素

  • boolean empty()：如果栈是空的，返回 true。否则，返回false

示例：

  1. MyStack myStack = new MyStack();
  2. myStack.push(1);
  3. myStack.push(2);
  4. myStack.top(); // 返回 2
  5. myStack.pop(); // 返回 2
  6. myStack.empty(); // 返回 False

3.1 两个队列实现

定义queue1与queue2两个队列，当queue1为空队列，直接将数据入队queue1即可。而queue1为非空队列，先将数据入队queue2，然后再将queue1中的数据入队queue2，最后交换queue1和queue2的指针

此时，最后添加的数据在队头，而之前添加的数据，会被导入在队尾，这符合栈的后进先出结构

使用这种方式，有数据的一定只有queue1，所以top和pop操作，只需要针对queue1进行peek与out操作即可

代码实现：

  1. class MyStack {
  3.     fileprivate var queue1 : LinkedQueue<Int>;
  4.     fileprivate var queue2 : LinkedQueue<Int>;
  6.     init() {
  7.         queue1 = LinkedQueue<Int>();
  8.         queue2 = LinkedQueue<Int>();
  9.     }
  11.     func push(x : Int){
  13.         if(queue1.isEmpty()){
  14.             queue1.enter(element: x);
  15.             return;
  16.         }
  18.         queue2.enter(element: x);
  20.         while(!queue1.isEmpty()){
  21.             queue2.enter(element: queue1.out()!);
  22.         }
  24.         let tmp = queue1;
  25.         queue1 = queue2;
  26.         queue2 = tmp;
  27.     }
  29.     func pop() -> Int?{
  31.         let top = getTop();
  33.         if(top == nil){
  34.             return top;
  35.         }
  37.         return queue1.out();
  38.     }
  40.     func getTop() -> Int?{
  41.         if(isEmpty()){
  42.             return nil;
  43.         }
  45.         return queue1.peek();
  46.     }
  48.     func isEmpty() -> Bool {
  50.         if(queue1.isEmpty()){
  51.             return true;
  52.         }
  54.         return false;
  55.     }
  56. }

  • 时间复杂度：入栈操作O(n)，其余操作O(1)

  • 空间复杂度：O(n)

3.2 一个队列实现

我们需要记录添加到队列中的数据数n，有新数据入队，同时进行n + 1。入队后，将队列遍历n - 1次，将队列中的数据依次出队再入队，这样就会将队头的数据导入到队尾，同样实现了栈的后进先出结构

代码实现：

  1. class MyStack {
  3.     fileprivate var queue : LinkedQueue<Int>;
  5.     init() {
  6.         queue = LinkedQueue<Int>();
  7.     }
  9.     func push(x : Int){
  11.         queue.enter(element: x);
  13.         for _ in 0..<queue.length - 1 {
  14.             queue.enter(element: queue.out()!);
  15.         }
  16.     }
  18.     func pop() -> Int?{
  20.         let top = getTop();
  22.         if(top == nil){
  23.             return top;
  24.         }
  26.         return queue.out();
  27.     }
  29.     func getTop() -> Int?{
  30.         if(isEmpty()){
  31.             return nil;
  32.         }
  34.         return queue.peek();
  35.     }
  37.     func isEmpty() -> Bool {
  39.         if(queue.isEmpty()){
  40.             return true;
  41.         }
  43.         return false;
  44.     }
  45. }

  • 时间复杂度：入栈操作O(n)，其余操作O(1)

  • 空间复杂度：O(n)

4. 自动释放池

自动释放池是一个存储指针的栈结构，指针要么是一个要释放的对象，要么是自动释放池的边界，俗称：哨兵对象。自动释放池的栈空间，被分成一个双向链接结构的页面列表，可添加和删除页面

  • 栈原则，后进先出。对象最后被push，最先被pop

  • 双向链表的特点，一个页中同时存在父结点和子结点。可向前找到父页面，也可向后找到子页面

4.1 定义默认值

  1. #import <Foundation/Foundation.h>
  2. #include <pthread.h>
  3. #include <malloc/malloc.h>
  4. #import <objc/runtime.h>
  6. // 哨兵对象
  7. #define POOL_BOUNDARY nil
  8. // 线程局部存储的key
  9. static pthread_key_t const key = 39;
  10. // 空池占位符
  11. #define EMPTY_POOL_PLACEHOLDER ((id*)1)
  12. // 自动释放池中对象销毁，使用0xA3填充
  13. static uint8_t const SCRIBBLE = 0xA3;  // 0xA3A3A3A3 after releasing
  14. // 自动释放池一页预设大小
  15. static size_t const SIZE = PAGE_MIN_SIZE;

4.2 页的数据结构

  1. @class AutoreleasePoolPage;
  3. @interface AutoreleasePoolPageData : NSObject {
  4.     // 存储对象的指针域
  5.     @package __unsafe_unretained id* _next;
  6.     // 父页面指针域
  7.     AutoreleasePoolPage *_parent;
  8.     // 子页面指针域
  9.     AutoreleasePoolPage *_child;
  10. }
  12. @end
  14. @implementation AutoreleasePoolPageData
  16. @end

4.3 页的初始化

  1. @interface AutoreleasePoolPage : AutoreleasePoolPageData
  3. @end
  5. @implementation AutoreleasePoolPage
  7. // 开辟空间
  8. + (instancetype)allocWithZone:(struct _NSZone *)zone {
  9.     // 起始地址为4k整数倍 + 4k
  10.     void *as = malloc_zone_memalign(malloc_default_zone(), SIZE, SIZE);
  11.     // 用来对一段内存空间全部设置为某个字符。使用0填充as首地址之后4k长度
  12.     memset(as, 0, SIZE);
  14.     // 开辟空间
  15.     void *src = [super allocWithZone:zone];
  16.     // 正常开辟空间，我们无法控制对象所在地址，但我们可以在它开辟后，将其拷贝到指定空间中
  17.     // 从src空间中移动n个元素，将其赋值给as的内存中。从内存的第一个地址所指向的数据开始复制，直到赋值n个数据
  18.     // 该函数也就调用结束，同时返回as
  19.     // 如果源区域和目的区域有重叠部分的话，可以在源区域未被目的区域覆盖的时候拷贝到目的区域中
  20.     memmove(as, src, sizeof(src));
  21.     // 拷贝后将src释放
  22.     [(id)src release];
  24.     return as;
  25. }
  27. // 初始化
  28. - (instancetype)initWithPage:(AutoreleasePoolPage *)page {
  30.     self = [super init];
  31.     if (self) {
  32.         // 将next默认设置为：当前对象首地址 + 对象大小
  33.         _next = [self begin];
  35.         // 连接双向链表，设置当前对象的父结点
  36.         _parent = page;
  38.         if (_parent) {
  39.             // 将父结点的子结点设置为自身
  40.             _parent->_child = self;
  41.         }
  42.     }
  44.     return self;
  45. }
  47. // 当前页的起始地址，结构体首地址 + 结构体大小
  48. - (id *)begin {
  49.     return (id *)((uint8_t *)self + class_getInstanceSize(self.class));
  50. }
  52. // 当前页的结束地址，结构体首地址 + 预设大小
  53. - (id *)end {
  54.     return (id *) ((uint8_t *)self + SIZE);
  55. }
  57. // next指向结束地址，当前页已满
  58. - (BOOL)full {
  59.     return _next == [self end];
  60. }
  62. // next指向起始地址，当前页为空
  63. - (BOOL)empty {
  64.     return _next == [self begin];
  65. }
  67. @end

4.4 将对象添加至自动释放池

  1. @implementation AutoreleasePoolPage
  3. // 添加哨兵对象（边界）
  4. + (void *)push {
  5.     // 添加哨兵对象到自动释放池，返回哨兵对象在池子中的地址
  6.     id *dest = [self autoreleaseFast:POOL_BOUNDARY];
  7.     // 返回的地址不是空池占位符，并且里面存储的不是哨兵对象，程序终止
  8.     assert(dest == EMPTY_POOL_PLACEHOLDER || *dest == POOL_BOUNDARY);
  9.     // 返回哨兵对象的地址
  10.     return dest;
  11. }
  13. // 添加对象
  14. + (id)autorelease:(id)obj {
  15.     // 对象为空，程序终止
  16.     assert(obj);
  17.     // 添加对象到自动释放池，返回对象在池子中的地址
  18.     id *dest __unused = [self autoreleaseFast:obj];
  19.     // 返回地址非空，并且地址不是空池占位符，并且里面存储的不是传入的对象，程序终止
  20.     assert(!dest  ||  dest == EMPTY_POOL_PLACEHOLDER  ||  *dest == obj);
  21.     // 返回传入的对象
  22.     return obj;
  23. }
  25. // 将对象添加到自动释放池
  26. - (id *)add:(id)obj {
  27.     // 当前页已满，程序终止
  28.     assert(!self.full);
  29.     // 得到当前next地址
  30.     id *ret = _next;
  31.     // 将对象存储在next中
  32.     *_next = obj;
  33.     // next向下平移
  34.     _next++;
  36.     // 返回存储对象的地址
  37.     return ret;
  38. }
  40. @end

添加对象到自动释放池：

  1. @implementation AutoreleasePoolPage
  3. // 快速创建自动释放池
  4. + (id *)autoreleaseFast:(id)obj {
  6.     // 获取热页
  7.     AutoreleasePoolPage *page = [self hotPage];
  9.     if (page && ![page full]) {
  10.         // 存在，并且未满，将对象加入自动释放池
  11.         return [page add:obj];
  12.     } else if (page) {
  13.         // 存在，并且已满，先添加新页，再添加对象
  14.         return [self autoreleaseFullPage:obj page:page];
  15.     } else {
  16.         // 不存在，先创建，然后添加对象
  17.         return [self autoreleaseNoPage:obj];
  18.     }
  19. }
  21. // 创建自动释放池，然后添加数据
  22. + (id *)autoreleaseNoPage:(id)obj {
  24.     // 存在热页，终止程序
  25.     assert(!self.hotPage);
  27.     // 加入哨兵对象的标记，默认为false
  28.     BOOL pushExtraBoundary = false;
  30.     // 判断当前线程是否已存在空池占位符
  31.     if (self.haveEmptyPoolPlaceholder) {
  32.         // We are pushing a second pool over the empty placeholder pool
  33.         // or pushing the first object into the empty placeholder pool.
  34.         // Before doing that, push a pool boundary on behalf of the pool
  35.         // that is currently represented by the empty placeholder.
  37.         // 已存在，先插入哨兵对象，修改标记为true
  38.         pushExtraBoundary = true;
  39.     }
  40.     else if (obj == POOL_BOUNDARY) {
  41.         // We are pushing a pool with no pool in place,
  42.         // and alloc-per-pool debugging was not requested.
  43.         // Install and return the empty pool placeholder.
  45.         // 不存在，且当前插入的对象为哨兵对象，当前线程先创建一个空池占位符
  46.         return [self setEmptyPoolPlaceholder];
  47.     }
  49.     // 创建一个新页，当前新页为根结点，所以父结点为nil
  50.     AutoreleasePoolPage *page = [[AutoreleasePoolPage alloc] initWithPage:nil];
  51.     // 将当前新页设置为热页
  52.     [self setHotPage:page];
  54.     // 判断插入哨兵对象的标记
  55.     if (pushExtraBoundary) {
  56.         // 标记为true，插入哨兵对象
  57.         [page add:POOL_BOUNDARY];
  58.     }
  60.     // Push the requested object or pool.
  61.     // 将对象加入自动释放池
  62.     return [page add:obj];
  63. }
  65. // 热页已满，先添加新页，再添加对象
  66. + (id *)autoreleaseFullPage:(id)obj page:(AutoreleasePoolPage *)page {
  67.     // The hot page is full.
  68.     // Step to the next non-full page, adding a new page if necessary.
  69.     // Then add the object to that page.
  71.     // 当前传入的页不是热页，程序终止
  72.     assert(page == self.hotPage);
  73.     // 当前页未满，程序终止
  74.     assert([page full]);
  76.     do {
  78.         // 判断当前页是否存在子页
  79.         if (page->_child) {
  80.             // 存在，继续向下找
  81.             page = page->_child;
  82.         }
  83.         else {
  84.             // 不存在，创建新页，传入当前页作为父结点，新页为当前页的子页
  85.             page = [[self alloc] initWithPage:page];
  86.         }
  88.         // 如果找到未写满的页，停止循环
  89.     } while ([page full]);
  91.     // 将未写满的页设置为热页
  92.     [self setHotPage:page];
  94.     // 将对象加入自动释放池
  95.     return [page add:obj];
  96. }
  98. @end

空池占位符：

  1. @implementation AutoreleasePoolPage
  3. // 当前线程是否已存在空池占位符
  4. + (BOOL)haveEmptyPoolPlaceholder {
  5.     // 从线程局部存储中获取
  6.     id *tls = (id *)pthread_getspecific(key);
  7.     // 结果为空池占位符，返回true
  8.     return (tls == EMPTY_POOL_PLACEHOLDER);
  9. }
  11. // 当前线程创建一个空池占位符
  12. + (id*)setEmptyPoolPlaceholder {
  13.     // 线程局部存储中有值，程序中断
  14.     assert(pthread_getspecific(key) == nil);
  15.     // 将空池占位符写入线程局部存储中
  16.     pthread_setspecific(key, (void *)EMPTY_POOL_PLACEHOLDER);
  17.     // 返回空池占位符
  18.     return EMPTY_POOL_PLACEHOLDER;
  19. }
  21. // 获取冷页
  22. + (AutoreleasePoolPage *)coldPage {
  24.     // 获取热页
  25.     AutoreleasePoolPage *result = self.hotPage;
  26.     // 判断结果是否为空
  27.     if (result) {
  28.         // 结果非空，一直遍历到根结点
  29.         while (result->_parent) {
  30.             result = result->_parent;
  31.         }
  32.     }
  33.     // 返回结果
  34.     return result;
  35. }
  37. //获取热页
  38. + (AutoreleasePoolPage *)hotPage {
  39.     // 从线程局部存储中获取
  40.     AutoreleasePoolPage *result = (AutoreleasePoolPage *)pthread_getspecific(key);
  41.     // 返回的结果为空池占位符，返回nil
  42.     if ((id *)result == EMPTY_POOL_PLACEHOLDER) return nil;
  43.     // 返回结果
  44.     return result;
  45. }
  47. // 设置热页
  48. + (void)setHotPage:(AutoreleasePoolPage *)page {
  49.     // 写入线程局部存储中
  50.     pthread_setspecific(key, page);
  51. }
  53. @end

冷页 & 热页：

  1. @implementation AutoreleasePoolPage
  3. // 获取冷页
  4. + (AutoreleasePoolPage *)coldPage {
  6.     // 获取热页
  7.     AutoreleasePoolPage *result = self.hotPage;
  8.     // 判断结果是否为空
  9.     if (result) {
  10.         // 结果非空，一直遍历到根结点
  11.         while (result->_parent) {
  12.             result = result->_parent;
  13.         }
  14.     }
  15.     // 返回结果
  16.     return result;
  17. }
  19. //获取热页
  20. + (AutoreleasePoolPage *)hotPage {
  21.     // 从线程局部存储中获取
  22.     AutoreleasePoolPage *result = (AutoreleasePoolPage *)pthread_getspecific(key);
  23.     // 返回的结果为空池占位符，返回nil
  24.     if ((id *)result == EMPTY_POOL_PLACEHOLDER) return nil;
  25.     // 返回结果
  26.     return result;
  27. }
  29. // 设置热页
  30. + (void)setHotPage:(AutoreleasePoolPage *)page {
  31.     // 写入线程局部存储中
  32.     pthread_setspecific(key, page);
  33. }
  35. @end

4.5 将对象从自动释放池中移除

  1. @implementation AutoreleasePoolPage
  3. // 移除并销毁对象
  4. + (void)pop:(void *)token {
  6.     AutoreleasePoolPage *page;
  7.     id *stop;
  9.     // 判断传入的地址是否等于空池占位符
  10.     if (token == (void*)EMPTY_POOL_PLACEHOLDER) {
  11.         // Popping the top-level placeholder pool.
  12.         // 当前地址为空池占位符，获取热页
  13.         page = self.hotPage;
  15.         // 热页不存在
  16.         if (!page) {
  17.             // Pool was never used. Clear the placeholder.
  18.             // 将其标记为nil
  19.             return [self setHotPage:nil];
  20.         }
  21.         // Pool was used. Pop its contents normally.
  22.         // Pool pages remain allocated for re-use as usual.
  24.         // 获取冷页（根结点）
  25.         page = self.coldPage;
  26.         // 记录根结点页面的起始地址
  27.         token = page.begin;
  28.     } else {
  29.         // 获取地址所属页的首地址
  30.         page = [self pageForPointer:(uintptr_t)token];
  31.     }
  32.     // 将stop赋值
  33.     stop = (id *)token;
  34.     // 将对象依次销毁，到指定位置结束
  35.     return [self popPage:token page:page stop:stop];
  36. }
  38. @end

获取地址所属页的首地址：

  1. @implementation AutoreleasePoolPage
  3. // 获取地址所属页的首地址
  4. + (AutoreleasePoolPage *)pageForPointer:(uintptr_t)p {
  6.     AutoreleasePoolPage *result;
  7.     // 当前地址和4K取余，得到偏移量，也就是已使用的容量
  8.     uintptr_t offset = p % SIZE;
  9.     // 如果偏移量小于AutoreleasePoolPage类的容量，程序终止
  10.     assert(offset >= sizeof([AutoreleasePoolPage class]));
  11.     // 使用当前地址 - 偏移量，得到页的首地址
  12.     result = (AutoreleasePoolPage *)(p - offset);
  13.     // 返回结果
  14.     return result;
  15. }
  17. @end

将对象依次销毁，到指定位置结束：

  1. @implementation AutoreleasePoolPage
  3. // 将对象依次销毁，到指定位置结束
  4. + (void)popPage:(void *)token page:(AutoreleasePoolPage *)page stop:(id *)stop {
  6.     // 将对象依次销毁，到指定位置结束
  7.     [page releaseUntil:stop];
  9.     // 判断当前页是否存在子页
  10.     if (page->_child) {
  11.         // hysteresis: keep one empty child if page is more than half full
  12.         // 存在子页，判断当前页使用的容量是否小于一半
  13.         if (page.lessThanHalfFull) {
  14.             // 小于一半，释放当前页之后的全部子页
  15.             [page->_child kill];
  16.         }
  17.         else if (page->_child->_child) {
  18.             // 超过一半，仅保留一个子页，释放子页之后的全部子页
  19.             [page->_child->_child kill];
  20.         }
  21.     }
  22. }
  24. // 判断当前页的使用量不满一半
  25. - (BOOL)lessThanHalfFull {
  26.     // 已使用地址 - 起始地址 < (结束地址 - 起始地址) / 2
  27.     return (_next - self.begin < (self.end - self.begin) / 2);
  28. }
  30. // 将对象依次销毁，到指定位置结束
  31. - (void)releaseUntil:(id *)stop {
  32.     // Not recursive: we don't want to blow out the stack
  33.     // if a thread accumulates a stupendous amount of garbage
  35.     // next不等于指定地址，持续遍历
  36.     while (self->_next != stop) {
  37.         // Restart from hotPage() every time, in case -release
  38.         // autoreleased more objects
  40.         // 获取热页
  41.         AutoreleasePoolPage *page = self.class.hotPage;
  43.         // fixme I think this `while` can be `if`, but I can't prove it
  44.         // 判断当前热页是否为空
  45.         while (page.empty) {
  46.             // 已经是空页，说明当前页中的数据全部销毁，但还未达到指定位置
  47.             // 获取父页，继续销毁父页中的对象
  48.             page = page->_parent;
  49.             // 将其设置为新的热页
  50.             [self.class setHotPage:page];
  51.         }
  53.         // next向上平移
  54.         page->_next--;
  55.         // 获取next中的对象
  56.         id obj = *page->_next;
  57.         // 将next存储的数据使用0xA3填充
  58.         memset((void*)page->_next, SCRIBBLE, sizeof(*page->_next));
  60.         // 判断当前对象是否为哨兵对象
  61.         if (obj != POOL_BOUNDARY) {
  62.             // 不是哨兵对象，调用它的release方法
  63.             [obj release];
  64.         }
  65.     }
  67.     // 将当前页设置为热页
  68.     [self.class setHotPage:self];
  69. }
  71. @end

销毁当前页以及之后的子页：

  1. @implementation AutoreleasePoolPage
  3. // 销毁当前页以及之后的子页
  4. - (void)kill
  5. {
  6.     // Not recursive: we don't want to blow out the stack
  7.     // if a thread accumulates a stupendous amount of garbage
  9.     // 将当前页赋值给临时变量
  10.     AutoreleasePoolPage *page = self;
  11.     // 遍历，找到最后一个子页
  12.     while (page->_child) {
  13.         page = page->_child;
  14.     }
  16.     AutoreleasePoolPage *deathptr;
  17.     do {
  18.         // 从最后的子页开始销毁，一直到当前页停止
  19.         deathptr = page;
  20.         page = page->_parent;
  21.         if (page) {
  22.             page->_child = nil;
  23.         }
  24.         [deathptr release];
  25.     } while (deathptr != self);
  26. }
  28. @end

4.6 入口函数

  1. // 添加边界
  2. void * objc_autoreleasePoolPush(void) {
  3.     return [AutoreleasePoolPage push];
  4. }
  6. // 将对象添加至自动释放池
  7. id objc_autorelease(id obj) {
  8.     return [AutoreleasePoolPage autorelease:obj];
  9. }
  11. // 将对象从自动释放池中移除
  12. void objc_autoreleasePoolPop(void * _Nonnull context) {
  13.     return [AutoreleasePoolPage pop:context];
  14. }

总结

概述：

  • 栈（Stack）：一个有穷线性数据结构，具有后进先出（LIFO）的特性

    • 栈中元素从栈顶（top）压入，也从栈顶弹出

  • 队列（Queue）：有穷线性数据结构，具有先进先出（FIFO）的特性

    • 队列中的元素，从队尾（rear）入队，从队头（front）出队

用栈实现队列：

  • 使用pushStack和popStack两个栈，实现队列的特性。入队逻辑非常简单，永远只会往pushStack中push数据。而出队逻辑相对复杂，因为要符合队列先进先出的特性

  • 让popStack负责pop操作，由于数据都被push到pushStack中，所以popStack为空栈，我们先将pushStack中的数据导入到popStack中。此时，数据在popStack中的顺序会改变，原本先入栈的数据会存储在栈顶

  • 所以，只要popStack为空栈，我们就先从pushStack中导入数据，然后再pop数据。否则，只要popStack不为空栈，直接从中pop数据即可

  • 切记，只要popStack为非空栈，就不能从pushStack中导入新的数据，因为会破坏popStack的先进先出结构

用队列实现栈：

  • 两个队列实现：定义queue1与queue2两个队列，当queue1为空队列，直接将数据入队queue1即可。而queue1为非空队列，先将数据入队queue2，然后再将queue1中的数据入队queue2，最后交换queue1和queue2的指针

  • 一个队列实现：我们需要记录添加到队列中的数据数n，有新数据入队，同时进行n + 1。入队后，将队列遍历n - 1次，将队列中的数据依次出队再入队，这样就会将队头的数据导入到队尾，同样实现了栈的后进先出结构

自动释放池：

  • 是一个存储指针的栈结构，指针要么是一个要释放的对象，要么是自动释放池的边界，俗称：哨兵对象。自动释放池的栈空间，被分成一个双向链接结构的页面列表，可添加和删除页面

    • 栈原则，后进先出。对象最后被push，最先被pop

    • 双向链表的特点，一个页中同时存在父结点和子结点。可向前找到父页面，也可向后找到子页面