數據結構與算法：3棧的順序存儲

棧是線性表的一種特例，它使得數據先入後出，就行壘磚似的最先壘的磚在最下面但是取的時候需要最後才能取到，最後壘的磚在最上面，但是取的時候是第一個取走。

棧的結構：

typedef struct stack
{
 int data[MAX];
 int top;
}sStack,*psStack;

這裡是使用的int型的數據，data數組為棧空間，最多數據元素為MAX個，top指向棧的棧頂。

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

1.初始化棧

sStack * StackInit()

用於創建棧申請棧空間，返回非0值表示初始化棧成功返回值為棧地址，返回0表示失敗。

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,int value)

將數據壓入棧，需要傳入創建棧時返回的地址和要壓入的數據的值，返回將數據壓入棧的結果。

8.出棧

int Pop(sStack *stack)

彈出棧頂的元素，需要傳入創建棧時返回的地址，返回棧頂的元素的值。

9.獲取棧頂元素

int 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
{
 int data[MAX];
 int top;
}sStack,*psStack;
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,int value);
int Pop(sStack *stack);
int GetTop(sStack *stack);
void StackDisplay(sStack *stack);
#endif

stack.c

#include 
#include 
#include "stack.h"
static const int StackMask=MAX-1;
sStack * StackInit()
{
 sStack *stack=NULL;
 stack=(psStack)malloc(sizeof(sStack));
 if(stack)
 {
 printf("棧創建成功\n");
 stack->top=-1;
 }
 return stack;
}
void StackDestory(sStack *stack)
{
 if(stack)
 {
 free(stack);
 stack=NULL;
 printf("釋放棧成功\n");
 }
}
void StackClear(sStack *stack)
{
 if(stack)
 {
 stack->top=-1;
 }
}
int StackLength(sStack *stack)
{
 if(stack)
 {
 return stack->top+1;
 }
 return STACK_ERR;
}
bool StackEmpty(sStack *stack)
{
 if(stack&&(stack->top==-1))
 {
 return TRUE;
 }
 return FALSE;
 
}
bool StackFull(sStack *stack)
{
 if(stack&&(stack->top==StackMask))
 {
 return TRUE;
 }
 return FALSE;
}
bool Push(sStack *stack,int value)
{
 if(stack&&(StackMask>stack->top))
 {
 stack->data[++stack->top]=value;
 return TRUE;
 }
 return FALSE;
}
int Pop(sStack *stack)
{
 if(stack&&stack->top>=0)
 {
 return stack->data[stack->top--];
 }
 return STACK_ERR;
}
int GetTop(sStack *stack)
{
 if(stack&&stack->top>=0)
 {
 return stack->data[stack->top];
 }
 return STACK_ERR;
}
void StackDisplay(sStack *stack)
{
 if(stack&&stack->top>=0)
 {
 int i;
 for(i=0;i<=stack->top;i++)
 {
 printf("The %d is %d\n",i,stack->data[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;
}