第14课-栈的定义及实现
1. 栈的定义
(1) 栈是一种特殊的线性表。
(2) 栈仅能在线性表的一端进行操作。
l 栈顶（Top）：允许操作的一端。
l 栈底（Bottom）：不允许操作的一端。
2. 栈的性质--后进先出
3. 栈的操作
(1) 创建栈。
(2) 销毁栈。
(3) 清空栈。
(4) 进栈。
(5) 出栈。
(6) 获取栈顶元素。
(7) 获取栈的大小。
例子：
将上一节的文件SeqList.h和SeqList.c，加到我们建立的工程文件夹之中。然后建立下面的三个文件。
（1）SeqStack.h
#ifndef _SEQSTACK_H_
#define _SEQSTACK_H_
typedef void SeqStack;
SeqStack* SeqStack_Create(int capacity);
void SeqStack_Destroy(SeqStack* stack);
void SeqStack_Clear(SeqStack* stack);
int SeqStack_Push(SeqStack* stack, void* iteam);
void* SeqStack_Pop(SeqStack* stack);
void* SeqStack_Top(SeqStack* stack);
int SeqStack_Size(SeqStack* stack);
int SeqStack_Capacity(SeqStack* stack);
#endif
（2）SeqStack.c
#include"SeqStack.h"
#include"SeqList.h"
SeqStack* SeqStack_Create(int capacity)
{
return SeqList_Create(capacity);
}
void SeqStack_Destroy(SeqStack* stack)
{
SeqList_Destroy(stack);
}
void SeqStack_Clear(SeqStack* stack)
{
SeqList_Clear(stack);
}
int SeqStack_Push(SeqStack* stack, void* item)
{
return SeqList_Insert(stack,item,SeqList_Length(stack));
}
void* SeqStack_Pop(SeqStack* stack)
{
return SeqList_Delete(stack,SeqList_Length(stack) - 1);
}
void* SeqStack_Top(SeqStack* stack)
{
return SeqList_Get(stack,SeqList_Length(stack) - 1);
}
int SeqStack_Size(SeqStack* stack)
{
return SeqList_Length(stack);
}
int SeqStack_Capacity(SeqStack* stack)
{
return SeqList_Capacity(stack);
}
（3）main.c
#include <stdio.h>
#include <stdlib.h>
#include "SeqStack.h"
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char *argv[])
{
SeqStack* stack = SeqStack_Create(20);
int a[10];
int i = 0;
for(i=0; i<10; i++)
{
a[i] = i;
SeqStack_Push(stack, a + i);
}
printf("Top: %d ", *(int*)SeqStack_Top(stack));
printf("Capacity: %d ", SeqStack_Capacity(stack));
printf("Length: %d ", SeqStack_Size(stack));
while( SeqStack_Size(stack) > 0 )
{
printf("Pop: %d ", *(int*)SeqStack_Pop(stack));
}
SeqStack_Destroy(stack);
return 0;
}
4. 栈的顺序存储实现
5. 栈的链式存储实现
将上节课的LinkList.h和LinkList.c复制到我们这节课用的文件夹之中。然后建立下面的三个文件。
（1）LinkStack.h
#ifndef _LINKSTACK_H_
#define _LINKSTACK_H_
typedef void LinkStack;
LinkStack* LinkStack_Create();
void LinkStack_Destroy(LinkStack* stack);
void LinkStack_Clear(LinkStack* stack);
int LinkStack_Push(LinkStack* stack, void* item);
void* LinkStack_Pop(LinkStack* stack);
void* LinkStack_Top(LinkStack* stack);
int LinkStack_Size(LinkStack* stack);
#endif
（2）LinkStack.c
#include <malloc.h>
#include "LinkStack.h"
#include "LinkList.h"
typedef struct _tag_LinkStackNode
{
LinkListNode header;
void* item;
} TLinkStackNode;
LinkStack* LinkStack_Create()
{
return LinkList_Create();
}
void LinkStack_Destroy(LinkStack* stack)
{
LinkStack_Clear(stack);
LinkList_Destroy(stack);
}
void LinkStack_Clear(LinkStack* stack)
{
while( LinkStack_Size(stack) > 0 )
{
LinkStack_Pop(stack);
}
}
int LinkStack_Push(LinkStack* stack, void* item)
{
TLinkStackNode* node = (TLinkStackNode*)malloc(sizeof(TLinkStackNode));
int ret = (node != NULL) && (item != NULL);
if( ret )
{
node->item = item;
ret = LinkList_Insert(stack, (LinkListNode*)node, 0);
}
if( !ret )
{
free(node);
}
return ret;
}
void* LinkStack_Pop(LinkStack* stack)
{
TLinkStackNode* node = (TLinkStackNode*)LinkList_Delete(stack, 0);
void* ret = NULL;
if( node != NULL )
{
ret = node->item;
free(node);
}
return ret;
}
void* LinkStack_Top(LinkStack* stack)
{
TLinkStackNode* node = (TLinkStackNode*)LinkList_Get(stack, 0);
void* ret = NULL;
if( node != NULL )
{
ret = node->item;
}
return ret;
}
int LinkStack_Size(LinkStack* stack)
{
return LinkList_Length(stack);
}
（3）main.c
#include <stdio.h>
#include <stdlib.h>
#include "LinkStack.h"
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char *argv[])
{
LinkStack* stack = LinkStack_Create();
int a[10];
int i = 0;
for(i=0; i<10; i++)
{
a[i] = i;
LinkStack_Push(stack, a + i);
}
printf("Top: %d ", *(int*)LinkStack_Top(stack));
printf("Length: %d ", LinkStack_Size(stack));
while( LinkStack_Size(stack) > 0 )
{
printf("Pop: %d ", *(int*)LinkStack_Pop(stack));
}
LinkStack_Destroy(stack);
return 0;
}
小结
l 栈是一种特殊的线性表。
l 栈只允许在线性表的一端进行操作。
l 栈通常有两种实现方式：顺序结构实现，链式结。