栈就是插入和删除都在一个方向的一种表的数据结构,也就是所谓的“先进后出”,其实就像一个瓶子,只有一面是能够打开的,要想拿出最里面的东西,就要先吧上面的东西移开。下图形象的显示了什么是栈。其实这个图说明了一切
<注意图中的SP与下面程序中的S不是一个东西,SP是栈指针,它指向栈顶元素,而S是为了用链表得到栈表示的一个指针>
有时候我们会说堆栈,把两者放到一块说,实际上,在数据结构中,堆和栈完全是两码事。
对栈的操作比较少,就是入栈,出栈,返回栈顶元素,以及判断是否是空栈几种
对栈的实现可以用链表或数组的形式,链表的形式比较直接,比较形象,因此这里用链表实现。
栈相当于只在一个方向对链表进行操作。
栈的声明
1 | typedef struct Node *PtrToNode; |
创建一个空栈
创建一个空栈只需要创建一个头结点,然后将Next指向NULL;1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23Stack CreateStack(void)
{
Stack S;
S = malloc(sizeof(struct Node));
if(S==NULL)
FatalError("Out of Space!");
S->Next = NULL;
MakeEmpty(S);
return S;
}
void MakeEmpty(Stack S)
{
if(S==NULL)
Error("Must Create Stack First!")
else
while(!IsEmpty(S))
Pop(S);
}
int IsEmpty(Stack S)
{
return S->Next==NULL:
}
那么对于初始的这个指针S到底是什么?请看下图:
出栈
1 | void Pop(Stack S) |
入栈
1 | void Push(ElementType X,Stack S) |
弹出栈顶元素
1 | ElementType Top(Stack S) |