【数据结构与算法】栈（Stack）之 浅谈数组和链表实现栈各自的优缺点_堆栈选择链表还是数组

往期相关文章：

1. 线性表之顺序表
2. 线性表之链表

1.栈介绍

  栈是一种特殊的线性表，只允许在栈顶（Top）进行插入和删除元素操作，另一端称为栈底，栈中的数据元素遵守后进先出LIFO（Last In First Out）或 先进后出的原则。

1. 栈的插入操作（Push）：称为压栈 或 入栈 或 进栈。
2. 栈的删除操作（Pop）：也叫出栈 或 弹栈。

  栈顶（top）也可以是最后一次进栈的数据位置，比如上图中，栈顶可以分别是100、200、300的位置，这取决于栈顶初始化成 0 还是 -1。如果栈顶最开始初始化为0，则栈顶是如上图所演示的位置，因为是先Push，然后再栈底top++；如果栈顶初始化为-1，则栈顶是最后一次进栈的数据下标位置，因为是先top++，然后再Push。

2. 哪种结构实现栈会更优？

  栈的实现一般可以使用数组或链表实现。对栈而言数组的结构实现更优一些，因为数组在尾上插入和删除数据的代价很小，时间复杂度均为O(1)，且没有其它额外开销。下面具体分析两种结构实现栈的优缺点。

对于链表实现栈，问题很多。一是链表有八种，二是每种链表实现起来都存在缺点。下面简单分析下链表实现栈的问题：

1. 先说单向链表实现栈，即便是多维护一个尾指针，对于栈的删除操作还是需要遍历，因为需要找到尾节点的上一个节点。

2. 而对于双向链表，为了解决单向链表实现栈的删除操作问题，唯一可行的只有双向循环链表，不仅轻松地找到尾结点，同时还能找到上一个节点，确实能解决上面谈到的问题。不过这又有其它问题了，每个节点相比于单向链表都多维护了一个指针变量，有一定内存开销。

所以说实现栈的最优结构，还得是数组，且数组自身的特性也产生了几个优点。数组的存储是连续的，正是因为这个原因：

1. 数组的寄存器命中率比链表高；
2. 寄存器命中后，不会产生寄存器空间污染。

数组实现栈的话就没有任何缺点吗？答案是有的，前面也说过，栈是一种特殊的线性表。

1. 空间给大了或每次扩容扩大了，然后又不使用，那空间就浪费了；4
2. 空间给小了或者每次扩容扩小了，那插入数据时容量不够经常需要扩容（realloc），扩容本身也有一些消耗；
3. 最不能接受的是，如果后面的内存不足以扩容设定的大小，realloc扩容可能会异地扩容，内存碎片增多，异地扩容意思是跳过这段大小不够的内存空间，到另一片内存区域扩容，这也会导致跳过的那一段内存变成内存碎片，如果一直没有程序去使用，空间也浪费掉了！关于realloc扩容，可以看看我的这篇文章 指针与动态内存 2.3realloc部分。

不过上述数组的缺点，也是能控制的。比如数组初始化大小根据需求给一个折中，扩容方案也折中，比如按自身1.5倍扩，这样能控制扩容的频率不至于太频繁，异地扩容的几率也小一些！优点相比于缺点，利大于弊！最重要的是，比起链表的优缺点，也要好上许多！

3.栈代码实现（C语言）

stack.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int valuetype;

typedef struct {
	valuetype* arr;
	int top;
	int capacity;
} Stack;

void Init(Stack* stack);

void Push(Stack* stack, valuetype value);
void Pop(Stack* stack);

valuetype Top(Stack* stack);
int Size(Stack* stack);
bool Empty(Stack* stack);

void Destroy(Stack* 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

stack.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Stack.h"

void Init(Stack* stack) {
	assert(stack);
	stack->arr = NULL;
	stack->capacity = stack->top = 0;
}

void Push(Stack* stack, valuetype value) {
	assert(stack);
	if (stack->top == stack->capacity) {
		stack->capacity = stack->capacity == 0 ? 10 : (int)(stack->capacity * 1.5);
		stack->arr = (valuetype*)realloc(stack->arr, sizeof(valuetype) * stack->capacity);
		if (stack->arr == NULL) {
			perror("realloc failed in the function Push(Stack*, valuetype).");
			return;
		}
	}
	stack->arr[stack->top++] = value;
}

void Pop(Stack* stack) {
	assert(stack && stack->top > 0);
	stack->top--;
}

valuetype Top(Stack* stack) {
	assert(stack && stack->top > 0);
	return stack->arr[stack->top - 1];
}

int Size(Stack* stack) {
	assert(stack);
	return stack->top;
}

bool Empty(Stack* stack) {
	assert(stack);
	return stack->top == 0;
}

void Destroy(Stack* stack) {
	assert(stack);
	free(stack->arr);
	stack->arr = NULL;
	stack->capacity = 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
42
43
44
45
46
47
48
49