(二)数据结构之线性表的简单实现：堆栈

绝地灬酷狼 2022-06-08 06:13 203阅读 0赞

## 1、堆栈的定义 ##

具有一定操作约束的线性表，只在一端（栈顶，Top）做插入、删除操作。堆栈的基本操作主要有两类：a、插入数据：入栈（Push）；b、删除数据：出栈（Pop）。

## 2、栈的顺序存储实现 ##

### 2.1 栈的基本数据结构 ###

/* 定义堆栈的数据结构 */
    #define MaxSize		10
    typedef int ElementType;
    typedef struct _Stack{
    	ElementType Data[MaxSize];
    	int Top;
    } Stack;

### 2.2 创建一个空栈 ###

/* 创建一个堆栈 */
    Stack *CreateStack()
    {
    	Stack *S = (Stack*)malloc(sizeof(Stack));
    	if(NULL != S) S->Top = -1;
    	return S;
    }

### 2.3 压栈操作 ###

/* 压栈操作，先移动Top，后压入 */
    void Push( Stack *PtrS, ElementType item )
    {
    	if (IsFull(PtrS))	// 判断是否栈满 
    	{
    		printf("Stack is full!\n"); 
    		return;
    	}
    	else 
    	{
    		PtrS->Data[++(PtrS->Top)] = item;
    		return;
    	}
    }

### 2.4 出栈操作 ###

/* 出栈操作，先弹出，后移动Top */
    ElementType Pop( Stack *PtrS )
    {
    	if (IsEmpty(PtrS)) 		// 判断堆栈是否为空
    	{
    		printf("The stack is empty!\n");
    		return -1; 
    	} 
    	else
    		return ( PtrS->Data[(PtrS->Top)--] );
    }

### 2.5 完整示例代码 ###

/* 顺序存储堆栈的实现 */
    #include <stdio.h>
    #include <stdlib.h>
    
    /* 定义堆栈的数据结构 */
    #define MaxSize		10
    typedef int ElementType;
    typedef struct _Stack{
    	ElementType Data[MaxSize];
    	int Top;
    } Stack;
    
    /* 创建一个堆栈 */
    Stack *CreateStack()
    {
    	Stack *S = (Stack*)malloc(sizeof(Stack));
    	if(NULL != S) S->Top = -1;
    	return S;
    }
    
    /* 销毁一个堆栈 */
    void DestroyStack(Stack *PtrS)
    {
    	if(NULL != PtrS)
    	{
    		free(PtrS);
    		PtrS = NULL;
    	}
    }
    
    /* 判断一个堆栈是否为空，为空返回1，否者返回0 */
    int IsEmpty( Stack *S )
    {
    	return (S->Top == -1);
    }
    
    /* 判断一个堆栈是否为满, 为满返回1，否者返回0 */
    int IsFull( Stack *S )
    {
    	return (S->Top == MaxSize - 1);
    }
    
    /* 压栈操作，先移动Top，后压入 */
    void Push( Stack *PtrS, ElementType item )
    {
    	if (IsFull(PtrS))	// 判断是否栈满 
    	{
    		printf("Stack is full!\n"); 
    		return;
    	}
    	else 
    	{
    		PtrS->Data[++(PtrS->Top)] = item;
    		return;
    	}
    }
    
    /* 出栈操作，先弹出，后移动Top */
    ElementType Pop( Stack *PtrS )
    {
    	if (IsEmpty(PtrS)) 		// 判断堆栈是否为空
    	{
    		printf("The stack is empty!\n");
    		return -1; 
    	} 
    	else
    		return ( PtrS->Data[(PtrS->Top)--] );
    }
    
    /* 遍历一个堆栈 */
    void Traversal( Stack *PtrS )
    {
    	int i = 0;
    	if(!IsEmpty(PtrS))
    	{
    		for(i = PtrS->Top; i >= 0; i--)
    			printf("%d ", PtrS->Data[i]);
    		printf("\n");
    	}
    }
    
    /* 程序入口 */
    int main()
    {
    	int i = 0;
    	ElementType temp;
    	Stack *stack = NULL;
    
    	/* 创建一个堆栈 */
    	stack = CreateStack();
    	if(NULL == stack)
    	{
    		printf("Create stack is failed!\n");
    		return -1;
    	}
    
    	/* 向堆栈中压入五个元素 */
    	printf("Input 5 numbers : ");
    	for(i = 0; i < 5; i++)
    	{
    		scanf("%d", &temp);
    		Push(stack, temp);
    	}
    
    	printf("*************************************Traversal********************************\n");
    	Traversal(stack);
    
    	printf("*************************************Push*************************************\n");
    	printf("Input 1 number : ");
    	scanf("%d", &temp);
    	Push(stack, temp);
    	Traversal(stack);
    
    	printf("*************************************Pop twice********************************\n");
    	Pop(stack);
    	Pop(stack);
    	Traversal(stack);
    
    	DestroyStack(stack);	// 销毁一个堆栈
    
    	return 0;
    }

## 3、栈的链式存储实现 ##

### 3.1 基本数据结构 ###

/* 定义堆栈的数据结构 */
    typedef int ElementType;
    typedef struct Node{
    	ElementType Data;
    	struct Node *Next;
    } LinkStack;

### 3.2 创建空栈 ###

/** 创建一个空堆栈
      *		给它分配一个头结点，这样做的目的是为了更好的操作这个堆栈更方面找到堆栈的栈顶
      */
    LinkStack *CreateStack()
    { 
    	/* 构建一个堆栈的头结点，返回指针 */
    	LinkStack *S;
    	S = malloc( sizeof(struct Node ));
    	if(NULL != S)
    		S->Next = NULL;
    	return S;
    }

### 3.3 压栈操作 ###

/* 压栈操作，进行结点插入 */
    void Push( ElementType item, LinkStack *S )
    { 
    	/* 将元素item压入堆栈S */
    	struct Node *TmpCell;
    	TmpCell = malloc( sizeof( struct Node ) );
    	TmpCell->Data = item;
    	TmpCell->Next = S->Next;
    	S->Next = TmpCell;
    }

### 3.4 出栈操作 ###

/* 出栈操作，删除结点 */
    ElementType Pop( LinkStack *S )
    { 
    	/* 删除并返回堆栈S的栈顶元素 */
    	struct Node *FirstCell;
    	ElementType TopElem;
    	if( IsEmpty( S ) ) 
    	{
    		printf("The link stack is empty!\n"); return -1;
    	}
    	else 
    	{
    		FirstCell = S->Next;
    		S->Next = FirstCell->Next;
    		TopElem = FirstCell->Data;
    		free(FirstCell);
    		FirstCell = NULL;	/* 防止野指针 */
    		return TopElem;
    	}
    }

### 3.5 完整代码实现 ###

/* 链式存储的堆栈的实现 */
    #include <stdio.h>
    #include <stdlib.h>
    
    /* 定义堆栈的数据结构 */
    typedef int ElementType;
    typedef struct Node{
    	ElementType Data;
    	struct Node *Next;
    } LinkStack;
    
    /** 创建一个空堆栈
      *		给它分配一个头结点，这样做的目的是为了更好的操作这个堆栈更方面找到堆栈的栈顶
      */
    LinkStack *CreateStack()
    { 
    	/* 构建一个堆栈的头结点，返回指针 */
    	LinkStack *S;
    	S = malloc( sizeof(struct Node ));
    	if(NULL != S)
    		S->Next = NULL;
    	return S;
    }
    
    /* 销毁一个堆栈 */
    void DestroyStack(LinkStack *S)
    {	
    	LinkStack *Temp = S->Next;	// 先释放栈内结点
    	LinkStack *Next;
    	while(Temp)
    	{
    		Next = Temp->Next;
    		free(Temp);
    		Temp = Next;
    	}
    	S->Next = NULL;
    }
    
    /* 销毁一个堆栈 */
    void DestroyStackHead(LinkStack *S)
    {
    	if(NULL != S)
    	{
    		free(S);
    		S = NULL;
    	}
    }
     
    /* 判断堆栈S是否为空，若为空函数返回整数1，否则返回0 */
    int IsEmpty( LinkStack *S )
    { 
    	return ( S->Next == NULL );
    }
    
    /* 压栈操作，进行结点插入 */
    void Push( ElementType item, LinkStack *S )
    { 
    	/* 将元素item压入堆栈S */
    	struct Node *TmpCell;
    	TmpCell = malloc( sizeof( struct Node ) );
    	TmpCell->Data = item;
    	TmpCell->Next = S->Next;
    	S->Next = TmpCell;
    }
    
    /* 出栈操作，删除结点 */
    ElementType Pop( LinkStack *S )
    { 
    	/* 删除并返回堆栈S的栈顶元素 */
    	struct Node *FirstCell;
    	ElementType TopElem;
    	if( IsEmpty( S ) ) 
    	{
    		printf("The link stack is empty!\n"); return -1;
    	}
    	else 
    	{
    		FirstCell = S->Next;
    		S->Next = FirstCell->Next;
    		TopElem = FirstCell->Data;
    		free(FirstCell);
    		FirstCell = NULL;	/* 防止野指针 */
    		return TopElem;
    	}
    }
    
    /* 遍历一个堆栈 */
    void Traversal( LinkStack *S )
    {
    	struct Node *TmpCell;
    	if(!IsEmpty( S ))
    	{
    		TmpCell = S->Next;
    		while(TmpCell)
    		{
    			printf("%d ", TmpCell->Data);
    			TmpCell = TmpCell->Next;
    		}
    		printf("\n");
    	}
    }
    
    
    /* 程序的入口 */
    int main()
    {
    	int i = 0;
    	ElementType temp;
    	LinkStack *stack = NULL;
    
    	/* 创建一个堆栈 */
    	stack = CreateStack();
    	if(NULL == stack)
    	{
    		printf("Create link stack is failed!\n");
    		return -1;
    	}
    
    	/* 向堆栈中压入五个元素 */
    	printf("Input 5 numbers : ");
    	for(i = 0; i < 5; i++)
    	{
    		scanf("%d", &temp);
    		Push(temp, stack);
    	}
    
    	printf("*************************************Traversal********************************\n");
    	Traversal(stack);
    
    	printf("*************************************Push*************************************\n");
    	printf("Input 1 number : ");
    	scanf("%d", &temp);
    	Push(temp, stack);
    	Traversal(stack);
    
    	printf("*************************************Pop twice********************************\n");
    	Pop(stack);
    	Pop(stack);
    	Traversal(stack);
    
    	DestroyStack(stack);		// 销毁一个堆栈
    	DestroyStackHead(stack);	// 销毁链表头
    
    	return 0;	
    }