从零开始学数据结构系列之第二章《栈》

---

栈的介绍

栈的英文为(stack)

栈是一个先进后出(FILO-First In Last Out)的有序列表。

  栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。

  根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

图解方式说明出栈(pop)和入栈(push)的顺序

逻辑示意图

我们可以抽象的将栈表示成一个弹夹，来进行理解

在最上面的子弹是最后被压入，也是最先被射出的

先入后出，后入先出
1

​   弹匣里的子弹在被压入时的顺序和被射出时的顺序正好相反，最先被压入的子弹在最后一个位置，同时也是最后被射出，而最后被压入的子弹在最上面的位置，也是最先被射出。

栈的常见基本操作

InitStack(&S)：初始化一个空栈S。
StackEmpty(S)：判断一个栈是否为空，若栈为空则返回true，否则返回false。
Push(&S, x)：进栈（栈的插入操作），若栈S未满，则将x加入使之成为新栈顶。
Pop(&S, &x)：出栈（栈的删除操作），若栈S非空，则弹出栈顶元素，并用x返回。
GetTop(S, &x)：读栈顶元素，若栈S非空，则用x返回栈顶元素。
DestroyStack(&S)：栈销毁，并释放S占用的存储空间（“&”表示引用调用）。
1
2
3
4
5
6

代码总体与头插法的单链表比较相似

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


typedef struct Node 
{
	int data;
    struct Node *next;
} Node;

/* 
初始化数据
*/
Node *initStack() 
{
	Node *list = (Node *)malloc(sizeof(Node));
	list -> data = 0;
	list -> next = NULL;
	return list;
}

/* 
判断数据是否为空
如：列表或者里面的数据为空，返回1，否则返回0
*/
int isEmpty(Node *list) 
{
    if (list->data == 0 || list->next == NULL) 
	{
        return 1;
    } 
	else 
	{
        return 0;
    }
}

/* 
将数据载入栈项，可以类比为头插法插入数据
*/
void push(Node *list, int data)
{
    Node *head = list;
	Node *node = (Node *)malloc(sizeof(Node));
	node -> data = data;
	node -> next = list -> next;
	list -> next = node;
	head -> data++;
}

/* 
弹出数据
先判断栈中的数据是否为空
如不为空，则弹出相应的数据
*/
int pop(Node *list)
{
	Node *head = list;
	if(isEmpty(list))
		return 0;
	else
	{
		Node *node = list->next;
		int data = node -> data;
		list->next = node -> next;
		free(node);
		head -> data--;
		return data;
	}
}

void printStack(Node *stack) 
{
	Node *node = stack -> next;
	while(node)
	{
		printf("%d->",node -> data);
		node = node -> next;
	}
	printf("NULL\r\n");
}


int main() {
    Node *stack = initStack();
    push(stack, 1);
    push(stack, 2);
    push(stack, 3);
    push(stack, 4);
    printStack(stack);
    printf("pop = %d\n", pop(stack));
    printStack(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
88
89
90
91
92
93

往期回顾

1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》