栈就是插入和删除都在一个方向的一种表的数据结构,也就是所谓的“先进后出”,其实就像一个瓶子,只有一面是能够打开的,要想拿出最里面的东西,就要先吧上面的东西移开。下图形象的显示了什么是栈。其实这个图说明了一切

stack1

<注意图中的SP与下面程序中的S不是一个东西,SP是栈指针,它指向栈顶元素,而S是为了用链表得到栈表示的一个指针>

有时候我们会说堆栈,把两者放到一块说,实际上,在数据结构中,堆和栈完全是两码事。

对栈的操作比较少,就是入栈,出栈,返回栈顶元素,以及判断是否是空栈几种

对栈的实现可以用链表或数组的形式,链表的形式比较直接,比较形象,因此这里用链表实现。

lianbiao1

栈相当于只在一个方向对链表进行操作。

栈的声明

1
2
3
4
5
6
7
8
9
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;
typedef int ElementType

struct Node
{
ElementType Element;
PtrToNode Next;
};

创建一个空栈

创建一个空栈只需要创建一个头结点,然后将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
Stack 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到底是什么?请看下图:

stack2

出栈

1
2
3
4
5
6
7
8
9
10
11
12
void Pop(Stack S)
{
PtrToNode Tmp;
if(IsEmpty(S))
Error("Empty Stack!");
else
{
Tmp->Next = S->Next;
S->Next = S->Next->Next;
free(Tmp);
}
}

入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
void Push(ElementType X,Stack S)
{
PtrToNode Tmp;
Tmp = malloc(sizeof(struct Node));
if(Tmp == NULL)
FatalError("Out of Space!");
else
{
Tmp->Element = X;
Tmp->Next = S->Next;
S->Next = Tmp;
}
}

弹出栈顶元素

1
2
3
4
5
6
7
8
9
10
ElementType Top(Stack S)
{
if(!IsEmpty(S))
return S->Next->Element;
else
{
Error("Empty Stack!");
return 0;
}
}