0%

数据结构——堆栈

堆栈是一种先进后出的数据结构,我和别人说起来的时候,经常拿井做比较,最先放到井里的东西要最后才能拿出来。具体实现起来有着至少两种方式,链表实现数组实现,实现思路都很简单,代码也都很简短。

堆栈

以下内容摘自维基百科

堆栈(英语: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--;
}
如果帮到了你的话,可以考虑请我喝咖啡