數據結構與算法：4棧的鏈式存儲

上一章我們講了棧的線性存儲這裡我們將會講解棧的鏈式存儲，和線性表的順序存儲和鏈式存儲一樣。棧的鏈式存儲也解決了棧的順序存儲需要事先分配整塊存儲空間的問題。

棧的結構

typedef struct stack
{
 struct sStackNode *top;
 int len;
}sStack,*psStack;

下面來介紹一下棧的操作：

1.初始化棧

sStack * StackInit()

創建棧的頭指針，返回棧的頭指針的地址。

2.銷燬創建的棧

void StackDestory(sStack *stack)

銷燬當前棧中所有創建的內存空間。

3.棧的復位

void StackClear(sStack *stack)

將棧初始化為空棧。

4.獲取棧的元素個數

int StackLength(sStack *stack)

返回當前棧中元素的個數。

5.判斷當前棧是否為空棧

bool StackEmpty(sStack *stack)

如果當前棧為空棧返回真，反之返回假。

6.判斷房錢棧是否為滿棧

bool StackFull(sStack *stack)

如果當前棧為滿棧返回真，反之返回假。

7.向棧中壓入元素

bool Push(sStack *stack,void * value)

向棧中壓入元素，返回操作是否成功，成功返回真，反之返回假。

8.從棧中彈出元素

void * Pop(sStack *stack)

從棧中彈出一個元素。改變棧的長度。

9.獲取棧頂元素的值

void * GetTop(sStack *stack)

獲取棧頂的元素，但是不改變棧的長度。

10.遍歷輸出棧的元素

void StackDisplay(sStack *stack)

遍歷輸出棧中的所有的元素。

stack.h

#ifndef _STACK_H
#define _STACK_H
#define MAX 4
#define STACK_OK 0
#define STACK_ERR -1
#define TRUE 1
#define FALSE 0
typedef int bool;
typedef struct stack
{
 struct sStackNode *top;
 int len;
}sStack,*psStack;
typedef struct stacknode
{
 void *data;
 struct sStackNode *pre;
}sStackNode,psStackNode;
sStack * StackInit();
void StackDestory(sStack *stack);
void StackClear(sStack *stack);
int StackLength(sStack *stack);
bool StackEmpty(sStack *stack);
bool StackFull(sStack *stack);
bool Push(sStack *stack,void * value);
void * Pop(sStack *stack);
void * GetTop(sStack *stack);
void StackDisplay(sStack *stack);
#endif

stack.c

#include 
#include 
#include "stack.h"
static const int StackMask=MAX;
sStack * StackInit()
{
 sStack *stack=NULL;
 stack=(psStack)malloc(sizeof(sStack));
 if(stack)
 {
 printf("棧創建成功\n");
 stack->top=NULL;
 stack->len=0;
 }
 return stack;
}
void StackDestory(sStack *stack)
{
 if(stack)
 {
 StackClear(stack);
 free(stack);
 stack=NULL;
 printf("釋放棧成功\n");
 }
}
void StackClear(sStack *stack)
{
 if(stack)
 {
 int len;
 sStackNode *current,*pre;
 current=stack->top;
 len=stack->len;
 while ((len--)&¤t)
 {
 pre=current->pre;
 free(current);
 current=pre;
 }
 stack->len=0;
 }
}
int StackLength(sStack *stack)
{
 if(stack)
 {
 return stack->len;
 }
 return STACK_ERR;
}
bool StackEmpty(sStack *stack)
{
 if(stack&&(!stack->len))
 {
 return TRUE;
 }
 return FALSE;
 
}
bool StackFull(sStack *stack)
{
 if(stack&&(stack->len==StackMask))
 {
 return TRUE;
 }
 return FALSE;
}
bool Push(sStack *stack,void * value)
{
 if(stack&&stack->lendata=value;
 node->pre=stack->top;
 stack->top=node;
 stack->len++;
 return TRUE;
 }
 return FALSE;
}
void * Pop(sStack *stack)
{
 if(stack&&stack->top>0)
 {
 void * data;
 sStackNode *current;
 current=stack->top;
 stack->len--;
 data=current->data;
 stack->top=current->pre;
 free(current);
 return data;
 }
 return STACK_ERR;
}
void * GetTop(sStack *stack)
{
 if(stack&&stack->top>0)
 {
 return (void *)((sStackNode *)(stack->top))->data;
 }
 return STACK_ERR;
}
void StackDisplay(sStack *stack)
{
 if(stack&&stack->top>0)
 {
 sStackNode *node=stack->top;
 int len=stack->len;
 int i=0;
 while (len--&&node)
 {
 printf("The %d is %d\n",i,node->data);
 node=node->pre;
 i++;
 } 
 }
}

main.c

#include 
#include "stack.h"
int main()
{
 sStack *stack=NULL;
 int status=0;
 stack=StackInit();
 if(!stack)
 {
 printf("初始化棧失敗\n");
 }
 status=StackEmpty(stack);
 if(status)
 {
 printf("棧為空\n");
 }
 else
 {
 printf("棧不為空\n");
 }
 status=Push(stack,11);
 if(status)
 {
 printf("壓棧成功\n");
 }
 else
 {
 printf("壓棧失敗\n");
 }
 status=StackEmpty(stack);
 if(status)
 {
 printf("棧為空\n");
 }
 else
 {
 printf("棧不為空\n");
 }
 status=Push(stack,22);
 if(status)
 {
 printf("壓棧成功\n");
 }
 else
 {
 printf("壓棧失敗\n");
 }
 status=StackLength(stack);
 printf("當前棧的長度為%d\n",status);
 status=Push(stack,33);
 if(status)
 {
 printf("壓棧成功\n");
 }
 else
 {
 printf("壓棧失敗\n");
 }
 status=StackFull(stack);
 if(status)
 {
 printf("棧為滿\n");
 }
 else
 {
 printf("棧不為滿\n");
 }
 status=StackLength(stack);
 printf("當前棧的長度為%d\n",status);
 status=GetTop(stack);
 printf("當前棧的棧頂的值為%d\n",status);
 status=Push(stack,44);
 if(status)
 {
 printf("壓棧成功\n");
 }
 else
 {
 printf("壓棧失敗\n");
 }
 status=StackFull(stack);
 if(status)
 {
 printf("棧為滿\n");
 }
 else
 {
 printf("棧不為滿\n");
 }
 StackDisplay(stack);
 status=Push(stack,55);
 if(status)
 {
 printf("壓棧成功\n");
 }
 else
 {
 printf("壓棧失敗\n");
 }
 status=StackFull(stack);
 if(status)
 {
 printf("棧為滿\n");
 }
 else
 {
 printf("棧不為滿\n");
 }
 status=StackLength(stack);
 printf("當前棧的長度為%d\n",status);
 status=GetTop(stack);
 printf("當前棧的棧頂的值為%d\n",status);
 status=Pop(stack);
 printf("當前取棧的棧頂的值為%d\n",status);
 status=StackFull(stack);
 if(status)
 {
 printf("棧為滿\n");
 }
 else
 {
 printf("棧不為滿\n");
 }
 status=StackLength(stack);
 printf("當前棧的長度為%d\n",status);
 status=GetTop(stack);
 printf("當前棧的棧頂的值為%d\n",status);
 StackClear(stack);
 status=StackEmpty(stack);
 if(status)
 {
 printf("棧為空\n");
 }
 else
 {
 printf("棧不為空\n");
 }
 status=StackLength(stack);
 printf("當前棧的長度為%d\n",status);
 StackDestory(stack);
 return 0;
}