堆栈是一种先进后出的数据结构，我和别人说起来的时候，经常拿井做比较，最先放到井里的东西要最后才能拿出来。具体实现起来有着至少两种方式，链表实现和数组实现，实现思路都很简单，代码也都很简短。
堆栈
以下内容摘自维基百科
堆栈（英语：stack）又称为栈或堆叠，是计算机科学中一种特殊的串列形式的抽象资料型别，其特殊之处在于只能允许在连结串列或阵列的一端（称为堆叠顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算
链表实现
节点
由于拿链表实现栈，因此最小单位是节点，使用一个结构来包装节点。
1
2
3
4
5
6
| typedef struct Node
{
ElementType data;
struct Node *next;
} Node;
typedef Node *Stack;
|
创建
链表实现的栈本质上是一个有头结点的链表，因此，建立一个新栈就是申请一个节点的内存。
1
2
3
4
5
6
| Stack CreateStack()
{
Node *ret = (Node *)malloc(sizeof(Node));
ret->next = NULL;
return ret;
}
|
push
向栈里 push 数据的话，其实就是在链表头再加一个节点。
1
2
3
4
5
6
7
| void Push(Stack stack, ElementType data)
{
Node *temp = (Node *)malloc(sizeof(Node));
temp->data = data;
temp->next = stack->next;
stack->next = temp;
}
|
pop
与 push 相反，pop 是删除头节点后的第一个节点。
1
2
3
4
5
6
7
8
9
| void Pop(Stack stack)
{
if (!Empty(stack))
{
Node *temp = stack->next;
stack->next = temp->next;
free(temp);
}
}
|
top
top 的话，直接取出第一个节点的值
1
2
3
4
| ElementType Top(Stack stack)
{
return stack->next->data;
}
|
empty
想要检查栈是否为空，可以直接检查头结点后面有没有节点。
1
2
3
4
| bool Empty(Stack 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
41
42
43
44
45
46
47
| #define ElementType int
#define bool int
#define true 1
#define false 0
typedef struct Node
{
ElementType data;
struct Node *next;
} Node;
typedef Node *Stack;
Stack CreateStack()
{
Node *ret = (Node *)malloc(sizeof(Node));
ret->next = NULL;
return ret;
}
bool Empty(Stack stack)
{
return stack->next == NULL;
}
void Push(Stack stack, ElementType data)
{
Node *temp = (Node *)malloc(sizeof(Node));
temp->data = data;
temp->next = stack->next;
stack->next = temp;
}
void Pop(Stack stack)
{
if (!Empty(stack))
{
Node *temp = stack->next;
stack->next = temp->next;
free(temp);
}
}
ElementType Top(Stack stack)
{
return stack->next->data;
}
|
数组实现
数组实现的思路有点像是做了个实实在在的井，容量有限，然后用记录下现在的元素数量，进而进行一系列操作。
结构
用数组实现的栈已经不是一个简单的数据类型了，需要有个数组，还需要记录长度以及当前元素数量。因此使用结构表示，出于效率的考虑，最终决定使用结构指针。
1
2
3
4
5
6
7
| typedef struct
{
ElementType *datas;
int top;
unsigned int length;
} Node;
typedef Node *Stack;
|
创建
与链表创建栈不同，数组版本的栈需要为其指定一个长度，然后申请对应大小的空间，同时初始化其他的元素。
1
2
3
4
5
6
7
8
| Stack CreateStack(const unsigned int length)
{
Stack stack = (Node *)malloc(sizeof(Node));
stack->length = length;
stack->top = 0;
stack->datas = (ElementType *)malloc(length * sizeof(ElementType));
return stack;
}
|
push
向栈里 push 数据，相当与在数组当前记录过的元素后赋值，并更新top值。需要注意的是，此时要判断栈是否满。
1
2
3
4
5
6
7
8
9
10
11
| void Push(Stack stack, ElementType data)
{
if (stack->top < stack->length)
{
stack->datas[++stack->top] = data;
}
else
{
exit(-1);
}
}
|
pop
数组版的pop只需要将top值减小就好。
1
2
3
4
5
6
7
| void Pop(Stack stack)
{
if (!Empty(stack))
{
stack->top--;
}
}
|
top
top的话，只需取出top值对应的元素即可。
1
2
3
4
| ElementType Top(Stack stack)
{
return stack->datas[stack->top];
}
|
empty
只要查看 top 的值即可确定是否为空栈
1
2
3
4
| bool Empty(Stack stack)
{
return stack->top == -1;
}
|
代码
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
| #define ElementType int
#define bool int
#define true 1
#define false 0
typedef struct
{
ElementType *datas;
int top;
unsigned int length;
} Node;
typedef Node *Stack;
Stack CreateStack(const unsigned int length)
{
Stack stack = (Node *)malloc(sizeof(Node));
stack->length = length;
stack->top = 0;
stack->datas = (ElementType *)malloc(length * sizeof(ElementType));
return stack;
}
bool Empty(Stack stack)
{
return stack->top == -1;
}
void Pop(Stack stack)
{
if (!Empty(stack))
{
stack->top--;
}
}
void Push(Stack stack, ElementType data)
{
if (stack->top < stack->length)
{
stack->datas[++stack->top] = data;
}
}
ElementType Top(Stack stack)
{
return stack->datas[stack->top];
}
|
模板类实现
最后贴上在 C++中包装成模板类的实现，仿照STL 中的 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
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
76
77
78
79
80
81
82
83
84
85
86
87
| template <class T>
class Node
{
public:
T data;
Node *next;
Node();
Node(T data, Node *next = nullptr);
};
template <class T>
class stack
{
public:
stack();
T top();
unsigned int size();
bool empty();
void push(T data);
void pop();
private:
Node<T> *datas;
unsigned int length;
};
template <class T>
Node<T>::Node(T data, Node *next)
{
this->data = data;
this->next = next;
}
template <class T>
Node<T>::Node()
{
this->next = nullptr;
}
template <class T>
stack<T>::stack()
{
this->datas = new Node<T>();
this->length = 0;
}
template <class T>
T stack<T>::top()
{
if (!this->empty())
{
return this->datas->next->data;
}
else
{
exit(-1);
}
}
template <class T>
unsigned int stack<T>::size()
{
return this->length;
}
template <class T>
bool stack<T>::empty()
{
return this->datas->next == nullptr;
}
template <class T>
void stack<T>::push(T data)
{
Node<T> *temp = new Node<T>(data, this->datas->next);
this->datas->next = temp;
this->length++;
}
template <class T>
void stack<T>::pop()
{
Node<T> *temp = this->datas->next;
this->datas->next = temp->next;
delete temp;
this->length--;
}
|