第11节 栈的定义及实现

-------------------------------------资源来源于网络,仅供自学使用,如有侵权,联系我必删.

第一:

栈的定义

? 栈是一种特殊的线性表
? 栈仅能在线性表的一端进行操作
?  栈顶(Top) ： 允许操作的一端
?  栈底(Bottom) ： ：不允许操作的一端

? 性质 ： 后进先出(  LIFO )

第二:

? 栈的一些常用操作
?  创建栈
?  销毁栈
?  清空栈
?  进栈
?  出栈
?  获取栈顶元素
? 获取栈的大小

 

第三:

栈的顺序实现:

基于SeqList.c和SeqList.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* item);//进栈

void* SeqStack_Pop(SeqStack* stack);//出栈

void* SeqStack_Top(SeqStack* stack);//获取栈顶元素

int SeqStack_Size(SeqStack* stack);//获取栈的大小

int SeqStack_Capacity(SeqStack* stack);//顺序栈的容量

#endif

#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);
}

#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\n", *(int*)SeqStack_Top(stack));   //用指针取出栈顶元素  9
    printf("Capacity: %d\n", SeqStack_Capacity(stack));//容量   20
    printf("Length: %d\n", SeqStack_Size(stack));      //大小   10
    
    while( SeqStack_Size(stack) > 0 )
    {
        printf("Pop: %d\n", *(int*)SeqStack_Pop(stack));
    }
    
    SeqStack_Destroy(stack);
    
	return 0;
}

第四:

栈的链式实现

基于LinkList.c和LinkList.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

#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;//保存传入的item
        
        ret  = LinkList_Insert(stack, (LinkListNode*)node, 0);//将node存入链表里面
    }
    
    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;//将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);
}

 

#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\n", *(int*)LinkStack_Top(stack));
    printf("Length: %d\n", LinkStack_Size(stack));
    
    while( LinkStack_Size(stack) > 0 )
    {
        printf("Pop: %d\n", *(int*)LinkStack_Pop(stack));
    }
    
    LinkStack_Destroy(stack);
    
	return 0;
}

 

 

小结

? 栈是一种特殊的线性表
? 栈只允许在线性表的一端进行操作
? 栈通常有两种实现方式

     顺序结构实现
     链式结构实现