栈和队列

作者收录于

2022-05-14 约 4642 字预计阅读 10 分钟

栈和队列可看作是特殊的线性表。它们的特殊性表现在它们的基本运算是线性表运算的子集，它们是运算受限的线性表。

栈

栈的概念

栈（Stack） ：是运算受限的线性表，其上的插入和删除运算限定在表的某一端进行，允许进行插入和删除的一端称为栈顶，另一端称为栈底。不含任何数据元素的栈称为空栈。处于栈顶位置的数据元素称为 栈顶元素。

栈的修改原则：后进先出（LIFO - Last In First Out），因此，栈又称为后进先出的线性表，简称 后进先出表。栈的插入和删除运算分别称为进栈和出栈。

上溢：栈中的数据元素已经填满了，如果再进行进栈操作，会发生「上溢」，为了防止数据丢失，在进栈操作之前应该判断是否栈满。

下溢：栈初始化运算得到一个空栈，此时，栈顶下标值 top==0，如果此时做出栈运算，则产生「下溢」。

栈相关函数定义：

 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
#ifndef DS_ALGO_DEMO_STACK_H
#define DS_ALGO_DEMO_STACK_H

#include <stdbool.h>

#define MAX_STACK_SIZE 5

// 顺序栈
typedef struct stack {
  int data[MAX_STACK_SIZE]; // 存储栈中数据元素的数组
  int top;                  // 标志栈顶位置的变量
} ArrayStack;

ArrayStack *CreateArrayStack();
bool PushArrayStack(ArrayStack *stack, int value);
bool PopArrayStack(ArrayStack *stack);
int GetTopArrayStack(ArrayStack *stack);
bool IsEmptyArrayStack(ArrayStack *stack);

// 链式栈
typedef struct node {
  int data;
  struct node *next;
} LinkedStack;

LinkedStack *CreateLinkedStack();
bool PushLinkedStack(LinkedStack *stack, int value);
bool PopLinkedStack(LinkedStack *stack);
int GetTopLinkedStack(LinkedStack *stack);
bool IsEmptyLinkedStack(LinkedStack *stack);

#endif

顺序栈

实现代码：

 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
#include "stack.h"
#include <stdlib.h>

ArrayStack *CreateArrayStack() {
  ArrayStack *stack = (ArrayStack *) malloc(sizeof(ArrayStack));
  if (stack == NULL) {
    return NULL;
  }
  stack->top = 0;
  return stack;
}

bool PushArrayStack(ArrayStack *stack, int value) {
  if (stack->top == MAX_STACK_SIZE - 1) {
    return false;
  }
  stack->top++;
  stack->data[stack->top] = value;
  return true;
}

bool PopArrayStack(ArrayStack *stack) {
  if (IsEmptyArrayStack(stack)) {
    return false;
  }
  stack->top--;
  return true;
}

int GetTopArrayStack(ArrayStack *stack) {
  if (IsEmptyArrayStack(stack)) {
    return 0;
  }
  return stack->data[stack->top];
}

bool IsEmptyArrayStack(ArrayStack *stack) {
  return stack->top == 0;
}

测试代码：

 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
#include <gtest/gtest.h>
extern "C" {
#include "../src/stack/stack.h"
}

TEST(TestArrayStack, CreateArrayStack) {
  ArrayStack *stack = CreateArrayStack();
  ASSERT_EQ(0, GetTopArrayStack(stack));
  ASSERT_EQ(0, stack->top);
  ASSERT_TRUE(IsEmptyArrayStack(stack));
}

TEST(TestArrayStack, PushArrayStack) {
  ArrayStack *stack = CreateArrayStack();

  for (int i = 1; i < 5; i++) {
    ASSERT_TRUE(PushArrayStack(stack, i));
    ASSERT_EQ(i, GetTopArrayStack(stack));
    ASSERT_EQ(i, stack->top);
  }
  ASSERT_FALSE(PushArrayStack(stack, 5));
  ASSERT_EQ(4, GetTopArrayStack(stack));
  ASSERT_EQ(4, stack->top);
}

TEST(TestArrayStack, PopArrayStack) {
  ArrayStack *stack = CreateArrayStack();
  for (int i = 1; i < 5; i++) {
    ASSERT_TRUE(PushArrayStack(stack, i));
    ASSERT_EQ(i, GetTopArrayStack(stack));
    ASSERT_EQ(i, stack->top);
  }

  for (int i = 1; i < 5; i++) {
    ASSERT_TRUE(PopArrayStack(stack));
  }
  ASSERT_FALSE(PopArrayStack(stack));
  ASSERT_EQ(0, GetTopArrayStack(stack));
  ASSERT_EQ(0, stack->top);
  ASSERT_TRUE(IsEmptyArrayStack(stack));
}

链式栈

实现代码：

 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
#include "stack.h"
#include <stdlib.h>

LinkedStack *CreateLinkedStack() {
  LinkedStack *stack = (LinkedStack *) malloc(sizeof(LinkedStack));
  if (stack == NULL) {
    return NULL;
  }
  stack->next = NULL;
  return stack;
}

bool PushLinkedStack(LinkedStack *stack, int value) {
  LinkedStack *temp;
  temp = (LinkedStack *) malloc(sizeof(LinkedStack));
  if (temp == NULL) {
    return false;
  }
  temp->data = value;
  temp->next = stack->next;
  stack->next = temp;
  return true;
}

bool PopLinkedStack(LinkedStack *stack) {
  if (IsEmptyLinkedStack(stack)) {
    return false;
  }
  LinkedStack *temp;
  temp = stack->next;
  stack->next = temp->next;
  free(temp);
  return true;
}

int GetTopLinkedStack(LinkedStack *stack) {
  if (IsEmptyLinkedStack(stack)) {
    return 0;
  }
  return stack->next->data;
}

bool IsEmptyLinkedStack(LinkedStack *stack) {
  return stack->next == NULL;
}

测试代码：

 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
#include <gtest/gtest.h>
extern "C" {
#include "../src/stack/stack.h"
}

TEST(TestLinkedStack, CreateLinkedStack) {
  LinkedStack *stack = CreateLinkedStack();
  ASSERT_EQ(0, GetTopLinkedStack(stack));
  ASSERT_EQ(NULL, stack->next);
  ASSERT_TRUE(IsEmptyLinkedStack(stack));
}

TEST(TestLinkedStack, PushLinkedStack) {
  LinkedStack *stack = CreateLinkedStack();

  for (int i = 1; i < MAX_STACK_SIZE * 2; i++) {
    ASSERT_TRUE(PushLinkedStack(stack, i));
    ASSERT_EQ(i, GetTopLinkedStack(stack));
    ASSERT_EQ(i, stack->next->data);
  }
  ASSERT_EQ(9, stack->next->data);
}

TEST(TestLinkedStack, PopLinkedStack) {
  LinkedStack *stack = CreateLinkedStack();
  for (int i = 1; i < MAX_STACK_SIZE * 2; i++) {
    ASSERT_TRUE(PushLinkedStack(stack, i));
    ASSERT_EQ(i, GetTopLinkedStack(stack));
    ASSERT_EQ(i, stack->next->data);
  }

  for (int i = 1; i < MAX_STACK_SIZE * 2; i++) {
    ASSERT_TRUE(PopLinkedStack(stack));
  }
  ASSERT_FALSE(PopLinkedStack(stack));
  ASSERT_TRUE(IsEmptyLinkedStack(stack));
  ASSERT_EQ(0, GetTopLinkedStack(stack));
  ASSERT_EQ(NULL, stack->next);
  ASSERT_EQ(0, stack->data);
}

递归与栈

递归（Recursion）：如果在一个函数或数据结构的定义中又应用了它自身（作为定义项之一），那么这个函数或数据结构称为是递归定义的，简称递归。

递归定义不能是「循环定义」，为此要求任何递归定义必须同时满足如下两个条件：

被定义项在定义中的应用（即作为定义项的出现）具有更小的「规模」；
被定义项在最小「规模」上的定义是非递归，这是递归的结束条件；

递归函数的运行引起递归调用。为了保证在不同层次的递归调用能正确地返回，必须将每一次递归调用的参数和返回地址保存起来。由于函数的递归调用是后进先出的，所以要用栈来保存这些值。

对列

对列的概念

队列（Queue）：是有限个同类型数据元素的线性序列，是一种先进先出（FIFO - First In First Out）的线性表，新加入的数据元素插在队列尾端，出队列的数据元素在队列首端被删除。

队列结构的几个属性：

队尾：插入的一端叫做队尾；
队头：删除的一端叫做队头；
入队：向队列中插入新节点元素称为入队；
出队：从队列中删除节点元素称为出队；
队空：当队列中无节点元素时，表示队空；
队满：当队列中节点超过允许存储空间时，表示队满（链队无队满的状态）；

循环队列中的几个约束：

队空：head = tail；
队满：head = (tail+1)%size；
进队：head = (head+1)%size；
出队：tail = (tail+1)%size；
个数：(tail-head+size)%size；

队列相关函数定义：

 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
#ifndef DS_ALGO_DEMO_QUEUE_H
#define DS_ALGO_DEMO_QUEUE_H

#include <stdbool.h>

#define MAX_QUEUE_SIZE 100

// 顺序队列
typedef struct queue {
  int data[MAX_QUEUE_SIZE];
  int head, tail;
} ArrayQueue;

ArrayQueue *CreateArrayQueue();
bool EnArrayQueue(ArrayQueue *queue, int value);
bool DeArrayQueue(ArrayQueue *queue);
int GetHeadArrayQueue(ArrayQueue *queue);
bool IsFullArrayQueue(ArrayQueue *queue);
bool IsEmptyArrayQueue(ArrayQueue *queue);

// 循环顺序队列
typedef struct caqueue {
  int data[MAX_QUEUE_SIZE];
  int head, tail;
} CircularArrayQueue;

CircularArrayQueue *CreateCircularArrayQueue();
bool EnCircularArrayQueue(CircularArrayQueue *queue, int value);
bool DeCircularArrayQueue(CircularArrayQueue *queue);
int GetHeadCircularArrayQueue(CircularArrayQueue *queue);
bool IsFullCircularArrayQueue(CircularArrayQueue *queue);
bool IsEmptyCircularArrayQueue(CircularArrayQueue *queue);

// 链式队列
typedef struct node {
  int data;
  struct node *next;
} LinkedQueueNode;

typedef struct lkqueue {
  LinkedQueueNode *head, *tail;
} LinkedQueue;

LinkedQueue *CreateLinkedQueue();
bool EnLinkedQueue(LinkedQueue *queue, int value);
bool DeLinkedQueue(LinkedQueue *queue);
int GetHeadLinkedQueue(LinkedQueue *queue);
bool IsEmptyLinkedQueue(LinkedQueue *queue);

// 循环链式队列
typedef struct cnode {
  int data;
  struct cnode *next;
} CircularLinkedQueueNode;

typedef struct clkqueue {
  CircularLinkedQueueNode *head, *tail;
  int len;
  int cap;
} CircularLinkedQueue;

CircularLinkedQueue *CreateCircularLinkedQueue(int cap);
bool EnCircularLinkedQueue(CircularLinkedQueue *queue, int value);
bool DeCircularLinkedQueue(CircularLinkedQueue *queue);
int GetHeadCircularLinkedQueue(CircularLinkedQueue *queue);
bool IsEmptyCircularLinkedQueue(CircularLinkedQueue *queue);
bool IsFullCircularLinkedQueue(CircularLinkedQueue *queue);

#endif

顺序对列

顺序对列（Sequential Queue）：是由一个一维数组（用于存储对列中元素）及两个分别指示队列首和队列尾元素的变量组成，这两个变量分别称为「队列首指针」和「队列尾指针」。

实现代码：

 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
#include "queue.h"
#include <stdlib.h>

ArrayQueue *CreateArrayQueue() {
  ArrayQueue *queue = (ArrayQueue *) malloc(sizeof(ArrayQueue));
  if (queue == NULL) {
    return NULL;
  }
  queue->head = queue->tail = 0;
  return queue;
}

bool EnArrayQueue(ArrayQueue *queue, int value) {
  if (IsFullArrayQueue(queue) || value <= 0) {
    return false;
  }
  queue->data[queue->tail] = value;
  queue->tail++;
  return true;
}

bool DeArrayQueue(ArrayQueue *queue) {
  if (IsEmptyArrayQueue(queue)) {
    return false;
  }
  queue->head++;
  return true;
}

int GetHeadArrayQueue(ArrayQueue *queue) {
  if (IsEmptyArrayQueue(queue)) {
    return 0;
  }

  return queue->data[queue->head];
}

bool IsFullArrayQueue(ArrayQueue *queue) {
  return queue->tail == MAX_QUEUE_SIZE;
}

bool IsEmptyArrayQueue(ArrayQueue *queue) {
  return queue->head == queue->tail;
}

测试代码：

 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
#include <gtest/gtest.h>
extern "C" {
#include "../src/queue/queue.h"
}

TEST(TestArrayQueue, CreateArrayQueue) {
  ArrayQueue *queue = CreateArrayQueue();
  ASSERT_EQ(0, queue->head);
  ASSERT_EQ(0, queue->tail);
  ASSERT_TRUE(IsEmptyArrayQueue(queue));
  ASSERT_FALSE(IsFullArrayQueue(queue));
  ASSERT_EQ(0, GetHeadArrayQueue(queue));
}

TEST(TestArrayQueue, EnArrayQueue) {
  ArrayQueue *queue = CreateArrayQueue();

  ASSERT_FALSE(EnArrayQueue(queue, 0));
  for (int i = 1; i <= MAX_QUEUE_SIZE; i++) {
    ASSERT_TRUE(EnArrayQueue(queue, i));
    ASSERT_EQ(1, GetHeadArrayQueue(queue));
  }
  ASSERT_TRUE(IsFullArrayQueue(queue));
  ASSERT_FALSE(EnArrayQueue(queue, MAX_QUEUE_SIZE));
  ASSERT_EQ(1, GetHeadArrayQueue(queue));
}

TEST(TestArrayQueue, DeArrayQueue) {
  int i;
  ArrayQueue *queue = CreateArrayQueue();
  ASSERT_FALSE(DeArrayQueue(queue));

  for (i = 1; i <= MAX_QUEUE_SIZE; i++) {
    EnArrayQueue(queue, i);
  }

  for (i = 1; i <= MAX_QUEUE_SIZE; i++) {
    ASSERT_EQ(i, GetHeadArrayQueue(queue));
    ASSERT_TRUE(DeArrayQueue(queue));
  }
  ASSERT_FALSE(DeArrayQueue(queue));
  ASSERT_TRUE(IsEmptyArrayQueue(queue));
  ASSERT_EQ(0, GetHeadArrayQueue(queue));
}

循环顺序队列

实现代码：

 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
#include "queue.h"
#include <stdlib.h>

CircularArrayQueue *CreateCircularArrayQueue() {
  CircularArrayQueue *queue = (CircularArrayQueue *) malloc(sizeof(CircularArrayQueue));
  if (queue == NULL) {
    return NULL;
  }
  queue->head = queue->tail = 0;
  queue->data[queue->head] = 0;
  return queue;
}

bool EnCircularArrayQueue(CircularArrayQueue *queue, int value) {
  if (IsFullCircularArrayQueue(queue) || value <= 0) {
    return false;
  }
  queue->tail = (queue->tail + 1) % MAX_QUEUE_SIZE;
  queue->data[queue->tail] = value;
  return true;
}

bool DeCircularArrayQueue(CircularArrayQueue *queue) {
  if (IsEmptyCircularArrayQueue(queue)) {
    return false;
  }
  queue->head = (queue->head + 1) % MAX_QUEUE_SIZE;
  return true;
}

int GetHeadCircularArrayQueue(CircularArrayQueue *queue) {
  if (IsEmptyCircularArrayQueue(queue)) {
    return 0;
  }
  return queue->data[(queue->head + 1) % MAX_QUEUE_SIZE];
}

bool IsFullCircularArrayQueue(CircularArrayQueue *queue) {
  return (queue->tail + 1) % MAX_QUEUE_SIZE == queue->head;
}

bool IsEmptyCircularArrayQueue(CircularArrayQueue *queue) {
  return queue->head == queue->tail;
}

测试代码：

 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
#include <gtest/gtest.h>
extern "C" {
#include "../src/queue/queue.h"
}

TEST(TestCircularArrayQueue, CreateCircularArrayQueue) {
  CircularArrayQueue *queue = CreateCircularArrayQueue();
  ASSERT_EQ(0, queue->head);
  ASSERT_EQ(0, queue->tail);
  ASSERT_EQ(0, queue->data[queue->head]);
}

TEST(TestCircularArrayQueue, EnCircularArrayQueue) {
  CircularArrayQueue *queue = CreateCircularArrayQueue();

  ASSERT_TRUE(IsEmptyCircularArrayQueue(queue));
  ASSERT_FALSE(DeCircularArrayQueue(queue));
  ASSERT_FALSE(EnCircularArrayQueue(queue, 0));
  for (int i = 1; i < MAX_QUEUE_SIZE; i++) {
    ASSERT_TRUE(EnCircularArrayQueue(queue, i));
    ASSERT_EQ(1, GetHeadCircularArrayQueue(queue));
  }
  ASSERT_TRUE(IsFullCircularArrayQueue(queue));
  ASSERT_FALSE(EnCircularArrayQueue(queue, MAX_QUEUE_SIZE));
  ASSERT_EQ(1, GetHeadCircularArrayQueue(queue));
}

TEST(TestCircularArrayQueue, DeCircularArrayQueue) {
  int i;
  CircularArrayQueue *queue = CreateCircularArrayQueue();
  ASSERT_TRUE(IsEmptyCircularArrayQueue(queue));

  for (i = 1; i < MAX_QUEUE_SIZE; i++) {
    ASSERT_TRUE(EnCircularArrayQueue(queue, i));
  }

  for (i = 1; i < MAX_QUEUE_SIZE; i++) {
    ASSERT_FALSE(IsEmptyCircularArrayQueue(queue));
    ASSERT_EQ(i, GetHeadCircularArrayQueue(queue));
    ASSERT_TRUE(DeCircularArrayQueue(queue));
  }
  ASSERT_TRUE(IsEmptyCircularArrayQueue(queue));
  ASSERT_EQ(0, GetHeadCircularArrayQueue(queue));
  ASSERT_FALSE(DeCircularArrayQueue(queue));
}

链式对列

实现代码：

 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
#include "queue.h"
#include <stdlib.h>

LinkedQueue *CreateLinkedQueue() {
  LinkedQueue *queue = (LinkedQueue *) malloc(sizeof(LinkedQueue));
  if (queue == NULL) {
    return NULL;
  }
  LinkedQueueNode *node = (LinkedQueueNode *) malloc(sizeof(LinkedQueueNode));
  if (node == NULL) {
    return NULL;
  }
  queue->head = queue->tail = node;
  return queue;
}

bool EnLinkedQueue(LinkedQueue *queue, int value) {
  if (queue == NULL || value <= 0) {
    return false;
  }
  LinkedQueueNode *node;
  node = (LinkedQueueNode *) malloc(sizeof(LinkedQueueNode));
  if (node == NULL) {
    return false;
  }
  node->data = value;
  node->next = NULL;
  queue->tail->next = node;
  queue->tail = node;
  return true;
}

bool DeLinkedQueue(LinkedQueue *queue) {
  if (IsEmptyLinkedQueue(queue)) {
    return false;
  }
  LinkedQueueNode *node = queue->head->next; // 使 node 指向队列的首结点
  queue->head->next = node->next;            // 修改头结点的指针域指向新的首结点
  if (node->next == NULL) {
    queue->tail = queue->head;
  }
  free(node);
  return true;
}

int GetHeadLinkedQueue(LinkedQueue *queue) {
  if (IsEmptyLinkedQueue(queue)) {
    return 0;
  }
  LinkedQueueNode *node = queue->head->next;
  return node->data;
}

bool IsEmptyLinkedQueue(LinkedQueue *queue) {
  return queue->head == queue->tail;
}

测试代码：

 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
#include <gtest/gtest.h>
extern "C" {
#include "../src/queue/queue.h"
}

TEST(TestLinkedQueue, CreateLinkedQueue) {
  LinkedQueue *queue = CreateLinkedQueue();
  ASSERT_EQ(NULL, queue->head->next);
  ASSERT_EQ(NULL, queue->tail->next);
  ASSERT_EQ(0, GetHeadLinkedQueue(queue));
  ASSERT_TRUE(IsEmptyLinkedQueue(queue));
}

TEST(TestLinkedQueue, EnLinkedQueue) {
  LinkedQueue *queue = CreateLinkedQueue();

  ASSERT_FALSE(EnLinkedQueue(queue, 0));
  ASSERT_TRUE(IsEmptyLinkedQueue(queue));
  for (int i = 1; i <= MAX_QUEUE_SIZE; i++) {
    ASSERT_TRUE(EnLinkedQueue(queue, i));
    ASSERT_EQ(1, GetHeadLinkedQueue(queue));
  }
  ASSERT_FALSE(IsEmptyLinkedQueue(queue));
  ASSERT_EQ(1, GetHeadLinkedQueue(queue));
}

TEST(TestLinkedQueue, DeLinkedQueue) {
  int i;
  LinkedQueue *queue = CreateLinkedQueue();
  ASSERT_FALSE(DeLinkedQueue(queue));

  for (i = 1; i <= MAX_QUEUE_SIZE; i++) {
    ASSERT_TRUE(EnLinkedQueue(queue, i));
    ASSERT_EQ(1, GetHeadLinkedQueue(queue));
  }

  for (i = 1; i <= MAX_QUEUE_SIZE; i++) {
    ASSERT_TRUE(DeLinkedQueue(queue));
  }
  ASSERT_FALSE(DeLinkedQueue(queue));
  ASSERT_TRUE(IsEmptyLinkedQueue(queue));
  ASSERT_EQ(0, GetHeadLinkedQueue(queue));
}

循环链式队列

实现代码：

 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
#include "queue.h"
#include <stdlib.h>

CircularLinkedQueue *CreateCircularLinkedQueue(int cap) {
  if (cap <= 0) {
    return NULL;
  }
  CircularLinkedQueue *queue = (CircularLinkedQueue *) malloc(sizeof(CircularLinkedQueue));
  if (queue == NULL) {
    return NULL;
  }
  CircularLinkedQueueNode *p, *q;
  p = (CircularLinkedQueueNode *) malloc(sizeof(CircularLinkedQueueNode));
  queue->head = queue->tail = p;
  queue->len = 0;
  queue->cap = cap;
  p->next = q = p;
  for (int i = 0; i < cap; i++) {
    q->next = (CircularLinkedQueueNode *) malloc(sizeof(CircularLinkedQueueNode));
    q = q->next;
  }
  q->next = p; // 首尾链接
  return queue;
}

bool EnCircularLinkedQueue(CircularLinkedQueue *queue, int value) {
  if (IsFullCircularLinkedQueue(queue) || value <= 0) {
    return false;
  }
  queue->tail->data = value;
  queue->tail = queue->tail->next;
  queue->len++;
  return true;
}

bool DeCircularLinkedQueue(CircularLinkedQueue *queue) {
  if (IsEmptyCircularLinkedQueue(queue)) {
    return false;
  }
  queue->head = queue->head->next;
  queue->len--;
  return true;
}

int GetHeadCircularLinkedQueue(CircularLinkedQueue *queue) {
  if (IsEmptyCircularLinkedQueue(queue)) {
    return 0;
  }
  return queue->head->data;
}

bool IsEmptyCircularLinkedQueue(CircularLinkedQueue *queue) {
  return queue->len == 0;
}

bool IsFullCircularLinkedQueue(CircularLinkedQueue *queue) {
  return queue->len == queue->cap;
}

测试代码：

 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
#include <gtest/gtest.h>
extern "C" {
#include "../src/queue/queue.h"
}

TEST(TestCircularLinkedQueue, CreateCircularLinkedQueue) {
  CircularLinkedQueue *queue = CreateCircularLinkedQueue(MAX_QUEUE_SIZE);
  ASSERT_EQ(NULL, queue->head->next->data);
  ASSERT_EQ(NULL, queue->tail->next->data);
  ASSERT_EQ(0, GetHeadCircularLinkedQueue(queue));
}

TEST(TestCircularLinkedQueue, EnCircularArrayQueue) {
  CircularLinkedQueue *queue = CreateCircularLinkedQueue(MAX_QUEUE_SIZE);

  ASSERT_FALSE(EnCircularLinkedQueue(queue, 0));
  ASSERT_TRUE(IsEmptyCircularLinkedQueue(queue));
  for (int i = 1; i <= MAX_QUEUE_SIZE; i++) {
    ASSERT_TRUE(EnCircularLinkedQueue(queue, i));
    ASSERT_EQ(1, GetHeadCircularLinkedQueue(queue));
  }
  ASSERT_FALSE(IsEmptyCircularLinkedQueue(queue));
  ASSERT_EQ(1, GetHeadCircularLinkedQueue(queue));
}

TEST(TestCircularLinkedQueue, DeCircularArrayQueue) {
  int i;
  CircularLinkedQueue *queue = CreateCircularLinkedQueue(MAX_QUEUE_SIZE);
  ASSERT_FALSE(DeCircularLinkedQueue(queue));

  for (i = 1; i <= MAX_QUEUE_SIZE; i++) {
    ASSERT_TRUE(EnCircularLinkedQueue(queue, i));
    ASSERT_EQ(1, GetHeadCircularLinkedQueue(queue));
  }

  for (i = 1; i <= MAX_QUEUE_SIZE; i++) {
    ASSERT_TRUE(DeCircularLinkedQueue(queue));
  }
  ASSERT_FALSE(DeCircularLinkedQueue(queue));
  ASSERT_TRUE(IsEmptyCircularLinkedQueue(queue));
  ASSERT_EQ(0, GetHeadCircularLinkedQueue(queue));
}

数组

数组的逻辑结构

数组可以看成线性表的一种推广。一维数组又称向量，它由一组具有相同类型的数据元素组成，并存储在一组连续的存储单元中。若一维数组中的元素又是一个二维数组结构，则称为 二维数组，依次类推，逐渐升维。

一般地，一个 n 维数组可以看成元素为 n-1 维数组的线性表。

数组通常有两种基本运算：

读：给定一组下标，返回该位置的元素内容；
写：给定一组下标，修改该位置的元素内容；

数组的存储结构

一维数组元素的内存单元地址是连续的，二维数组可能有两种存储方法：一种是以列序为主的存储；另一种是以行序为主的存储。在类 C 语言的编译程序中，数组采用的是以行序为主序的存储方法。

数组元素的存储位置是下标的线性函数，假设二维数组 a[m][n]，如果每个元素占 k 个存储单元，则有：

行序位置：loc[i,j] = loc[0,0] + (n*i+j)*k；
列序位置：loc[i,j] = loc[0,0] + (m*j+i)*k；

矩阵的压缩存储

矩阵的压缩存储：在数值分析中经常出现一些高阶矩阵，这些高阶矩阵中有许多值相同的元素或零元素，为了节省存储空间，对这类矩阵采用多个值相同的元素只分配一个存储空间，零元素不存储的策略，称为矩阵的压缩存储。

特殊矩阵

如果值相同的元素或零元素在矩阵中的分布有一定规律，称此矩阵为 特殊矩阵。

对称矩阵

对称矩阵：若有一个 n 阶方阵 A 中的元素满足 a_ij= a_ji(0<=i, j<=n-1>)，则称 A 为对称矩阵。

对称矩阵有近一半的元素可以通过其对称元素获得，为每一对对称元素只分配一个存储单元，则可将 n² 个元素压缩存储到 n(n+1)/2 个元素的一维数组中。

设矩阵元素 a_ij 在数组 M 中的位置为 k，(i, k) 和 k 存在如下对应关系：

1
2
3
    ⎧ i(i+1)/2+j (i>=j)
k = ⎨
    ⎩ j(j+1)/2+i (i<j)

三角矩阵

三角矩阵：以主对角线为界的上（下）半部分是一个固定的值 c 或零，这样的矩阵叫做下（上）三角矩阵。

上三角矩阵：

上三角矩阵中，M[k] 和 a_ij 的对应关系是：

1
2
3
    ⎧ i(2n-i+1)/2+j-i (i<=j)
k = ⎨
    ⎩ n(n+1)/2 (i>j)

下三角矩阵：

下三角矩阵中，M[k] 和 a_ij 的对应关系是：

1
2
3
    ⎧ i(i+1)/2+j (i>=j)
k = ⎨
    ⎩ n(n+1)/2 (i<j)

稀疏矩阵

假设 m 行 n 列的矩阵有 t 个非零元素，当 t<=m*n 时，则称矩阵为 稀疏矩阵（Sparse Matrix），稀疏矩阵中非零元素的个数很少。

习题

设一个链栈的输入序列为 A、B、C，试写出所有得到的可能输出序列，即输出出栈操作得到的数据元素序列。

共有 5 种可能的输出序列：

ABC，A 进 A 出，B 进 B 出，C 进 C 出；
BCA，A 进 B 进，B 出 C 进，C 出 A 出；
BAC，A 进 B 进，B 出 A 出，C 进 C 出；
CBA，A 进 B 进，C 进 C 出，B 出 A 出；
ACB，A 进 A 出，B 进 C 进，C 出 B 出；

写出下列程序的运行结果。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include "stack.h"
#include <stdio.h>
#include <stdlib.h>

int main() {
  char ch;
  ArrayStack *stack = CreateArrayStack();
  for (ch = 'A'; ch <= 'A' + 10; ch++) {
    PushArrayStack(stack, ch);
    printf("%c", ch);
  }
  printf("\n");

  while (!IsEmptyArrayStack(stack)) {
    ch = GetTopArrayStack(stack);
    PopArrayStack(stack);
    printf("%c", ch);
  }
  printf("\n");
}

1
2
ABCDEFGHIJK
KJIHGFEDCBA

设有二维数组 int M[10][20]，每个元素（整数）占 2 个存储单元，数组的起始地址为 2000，求元素 M[5][10] 的存储位置，M[8][19] 的存储位置。

1
2
M[5][10] = 2000+(20*5+10)*2 = 2220
M[8][19] = 2000+(20*8+19)*2 = 2358

使用一个元素个数为 100 的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队列空和队列满，约定队列首指针 front 等于队列尾指针 rear 时表示队列为空。若 front=8, rear=7 时，求队列中的元素个数。

1
队列中的元素个数 = (7-8+100)%100 = 99

目录

栈和队列

栈

栈的概念

顺序栈

链式栈

递归与栈

对列

对列的概念

顺序对列

循环顺序队列

链式对列

循环链式队列

数组

数组的逻辑结构

数组的存储结构

矩阵的压缩存储

特殊矩阵

对称矩阵

三角矩阵

稀疏矩阵

习题