数据结构学习——顺序栈和链式栈的简单实现和解析（C语言版）

骑猪看日落 2022-12-24 04:59 109阅读 0赞

### 数据结构——栈的简单解析和实现 ###

*  一、概念
 *  二、入栈（push）
 *  三、出栈（pop）
 *  四、顺序栈简单实现
 *   *  （1）进栈操作
     *  （2）出栈操作

# 一、概念 #

> 本篇所讲解的栈和队列属于逻辑结构上的划分。逻辑结构分为线性结构、非线性结构

*  线性结构：有且仅有一个开始节点和一个终端节点，每个节点最多只有一个直接前驱和一个直接后继。代表结构：栈、队列
 *  非线性结构：一个节点可能有多个直接前驱和多个直接后继。代表结构：树、图

> 堆栈（英语：stack）又称为栈或堆叠，是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作。

*  栈的主要特点就是LIFO（Last In First Out，后进先出），并且程序只能操作栈的一端，被操作的一端叫做栈顶（Top）。所以栈的使用非常简单，但是实现的功能却非常强大
 *  栈的主要操作有两个：入栈(push)、出栈(pop)

# 二、入栈（push） #

![在这里插入图片描述][20201126211802459.gif_pic_center]

*  如图所示，栈就像一个瓶子，只有一个口。三个元素A、B、C先后入栈，先入栈的放在底部，后入栈的放在上面

# 三、出栈（pop） #

![在这里插入图片描述][20201126211907198.gif_pic_center]

*  根据图示，栈顶的元素最先出栈。这与入栈的顺序刚好相反，入栈顺序是A->B->C，出栈顺序是C->B->A。也就是说：栈是LIFO（Last In First Out，后进先出的）
 *  看似简单的栈，应用十分广泛。操作系统的函数调用、各类编辑器的撤销操作的实现都离不开栈。

栈有两种实现方式：**顺序栈**、**链式栈**

# 四、顺序栈简单实现 #

> 用数组实现栈，就是将数组的增、删操作限制在头部或者尾部，即只能在数组的一端操作元素，就成了顺序栈

**前提准备：**

typedef char ElementType;			//	进栈数据为字符型
    typedef struct SNode {
        
    	
    	ElementType Data[MAXSIZE];		//	存放数据
    	int Top; // 当前栈存放的数组的最大下标
    	
    }SNode;
    
    typedef struct SNode* Stack;

## （1）进栈操作 ##

void Push(Stack PtrS, ElementType item) {
        	//	进栈 
    
    	// 满的堆栈 Top == MAXSIZE - 1
    	// 判断栈是否满
    	if (PtrS->Top == MAXSIZE - 1) {
        
    		printf("堆栈满\n");
    	//	return Ptrs;
    	}
    	else {
        
    		PtrS->Data[++(PtrS->Top)] = item;
    	//	return;
    	}
    }

## （2）出栈操作 ##

ElementType Pop(Stack PtrS) {
        		//	出栈 
    	
    	// 空的的堆栈 Top == -1
    	// 出栈需要判断 堆栈是否为空
    	if (PtrS->Top == - 1) {
        
    		printf("堆栈空\n");
    		return -1;// ERROR 是 ElementType 的特殊值，标志错误
    	}
    	else {
        
    		return PtrS->Data[(PtrS->Top)--];
    	}
    }

**完整代码：**

#define _CRT_SECURE_NO_WARNINGS 1
    
    #include<stdio.h>
    #include<stdlib.h>
    
    #define MAXSIZE 10				//	设定栈的大小，以10个为例
    #define ERROR NULL;	
    
    //typedef int ElementType;
    typedef char ElementType;			//	进栈数据为字符型
    typedef struct SNode {
        
    	
    	ElementType Data[MAXSIZE];		//	存放数据
    	int Top; // 当前栈存放的数组的最大下标
    	
    }SNode;
    
    typedef struct SNode* Stack;
    
    void Push(Stack PtrS, ElementType item);// 压栈
    ElementType Pop(Stack PtrS);// 出栈
    
    void Init_Memu()			//	功能菜单 
    {
        
    	printf("******************************\n");
    	printf("*        1.入栈              *\n");
    	printf("*        2.出栈              *\n");
    	printf("*        3.取栈顶元素        *\n");
    	printf("*        4.判断是否栈空      *\n");
    	printf("*        5.退出系统         *\n");
    	printf("******************************\n");
    	
    } 
    
    int Chose_GongNeng()		//	选择功能 
    {
        
    	int i;
    	printf("请选择你要实现的功能 : \n"); 
    	scanf("%d",&i);
    	return i;
    	
    } 
    
    int main() {
        
    	
    	struct SNode ptr;		//	创建个结构体对象 
    	int num;
    	ptr.Top = -1;			//	栈空的标记符 为 -1
    	while(1)
    	{
        	
    		Init_Memu();
    		num = Chose_GongNeng();
    		
    		switch(num)
    		{
        
    			case 1:			//	入栈功能 
    				{
        	
    				//	int data;
    					char data;
    					ptr.Top = -1;
    					while( ptr.Top != MAXSIZE-1 )
    					{
        	
    						printf("请输入数据 :\n");
    						getchar();
    						scanf("%c",&data);
    					
    					//	printf("count = %d\n",count);
    						
    						Push(&ptr,data);
    						printf(" Top = %d\n",ptr.Top);
    					} 
    					
    				}
    				break;
    				
    			case 2:			//	出栈功能 
    				{
        	
    				//	int Pop_Data = 0;
    					char Pop_Data = '0';	
    					while(1){
        
    						Pop_Data = Pop(&ptr);
    						if(ptr.Top == -1){
        
    							printf("出栈完毕，现在栈为空栈\n");
    							break;
    						}else{
        
    							printf("出栈数据为 : %c \n",Pop_Data);
    						}
    						
    					}
    					
    					
    				}
    				break;
    				
    			case 3:			//	取栈顶元素 
    				{
        	if(ptr.Top == -1){
        
    						printf("出栈完毕，没有数据\n"); 
    					}else{
        
    						printf("栈顶的数据为: %c \n",ptr.Data[ptr.Top]);
    					}
    					
    					 
    				}
    				break;
    				
    			case 4:			//	判断栈是否为空 
    				{
        
    					if(ptr.Top == -1){
        
    						printf("此栈为空栈\n"); 
    					}else{
        
    						printf("此栈已经插入数据\n");
    					}
    				}
    				break;
    			
    			case 5:			//	退出系统 
    				printf("\n谢谢你的使用\n");
    				exit(-1);
    					
    			default:
    				printf("没有这个功能，请重新选择\n");
    			 	break; 
    		}
    	}
    
    	return 0;
    }
    
    void Push(Stack PtrS, ElementType item) {
        	//	进栈 
    
    	// 满的堆栈 Top == MAXSIZE - 1
    	// 判断栈是否满
    	if (PtrS->Top == MAXSIZE - 1) {
        
    		printf("堆栈满\n");
    	//	return Ptrs;
    	}
    	else {
        
    		PtrS->Data[++(PtrS->Top)] = item;	//	进栈数据，记录并改变标记符Top
    	//	return;
    	}
    }
    
    ElementType Pop(Stack PtrS) {
        		//	出栈 
    	
    	// 空的的堆栈 Top == -1
    	// 出栈需要判断 堆栈是否为空
    	if (PtrS->Top == - 1) {
        
    		printf("堆栈空\n");
    		return -1;// ERROR 是 ElementType 的特殊值，标志错误
    	}
    	else {
        
    		return PtrS->Data[(PtrS->Top)--];	//	出栈数据，记录并改变标记符Top
    	}
    }

[20201126211802459.gif_pic_center]: /images/20221120/2583f86e48ec48bba8907e867cfb54b2.png
[20201126211907198.gif_pic_center]: https://img-blog.csdnimg.cn/20201126211907198.gif#pic_center