详解数据结构之顺序栈的基本操作（C语言描述）

r囧r小猫 2022-03-22 03:05 224阅读 0赞

1.栈是线性表的特例，因此栈的顺序存储其实也就是线性表顺序存储的简化，我们称之为顺序栈，线性表是采用数组来实现的，因此顺序栈也采用数组来实现。  
2.栈的结构定义：elementype类型根据实际情况而定，这里假设为int类型，栈的结构体定义为一个用来储存数据的数组和一个用来表示栈顶位置的栈顶指针，用typedef将整个结构体命名为myStack。  
![在这里插入图片描述][20190125150034385.png]  
顺序栈中top的指示情况以及栈的各种操作时栈顶指针top的变化情况  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]  
3.初始化栈：将栈顶指针置为-1即可。  
![在这里插入图片描述][20190125152004855.png]  
4.置空栈：与初始化栈一样，直接将栈顶指针置为-1即可。  
![在这里插入图片描述][20190125152225706.png]  
5.入栈操作：先判断是否栈满，如果栈已经满了直接返回false(bool类型)；如果栈没有满的话将栈顶指针加一，并把要入栈的元素赋值给栈顶空间，然后返回true。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 1]  
6.出栈操作：先判断栈是否为空，如果是空栈的话向用户返回false，否则将要删除的元素赋值给临时变量e，然后将栈顶指针减一并返回true。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 2]  
7.对栈中某个元素进行访问并打印：直接调用printf函数对元素进行打印即可。  
![在这里插入图片描述][20190125153111686.png]  
8.遍历并将栈中所有元素进行打印（当然也可以对栈中元素进行其他操作），在for循环中调用访问函数。  
![在这里插入图片描述][20190125153016488.png]9.计算栈中元素的个数：因为栈顶指针为top，栈中元素的个数就是栈顶指针top加一之后的值。  
![在这里插入图片描述][20190125153347627.png]  
10.获得栈顶元素的值：当栈为空时直接返回false，否则就将栈顶元素交给临时变量并返回临时变量的值即可，**由于主函数中要得到临时变量的值，因此在传参的时候要将临时变量的地址传进去（即传递指针）**  
![在这里插入图片描述][2019012515400969.png]11.*整体代码及测试结果*

#include<stdio.h>
    #include<stdbool.h>					//bool（布尔类型的头文件） 
    #include<string.h>
    #define maxsize 20				//定义数组大小为20
    
    typedef int elementype;		//int类型别名
    
    typedef struct node{
    	elementype data[maxsize];			//数据域 
    	elementype top;						//栈顶指针 
    }myStack;				
    
    void visit(elementype c)			//访问栈中的元素 
    {
    	printf("%d ", c);
    }
    
    bool initstack(myStack *s)			//初始化栈 
    {
    	//这里没有给data申请空间建应该是因为数组的大小已经定义完成 
    	s -> top = -1;	
    	return true;
    }
    
    bool stackempty(myStack s)			//判断栈是否为空 
    {
    	if(s.top == -1)
    		return true;
    	else 
    		return false;
    } 
    
    bool ClearStack(myStack *s) 		//将栈清空 
    { 
            s -> top = -1;
            return true;
    }
    
    elementype length(myStack s)		//计算栈中元素的个数 
    {
    	return s.top + 1;
    }
    
    bool getTop(myStack s, elementype *e)	//获得栈顶元素 
    {
    	if(s.top == -1)
    		return false;
    	else
    		*e = s.data[s.top];
    	return true;
    }
    
    bool push(myStack *s, elementype e)			//元素e入栈 
    {
    	if(s -> top == maxsize - 1)
    		return false;
    	else
    	{
    		s -> top++;				//栈顶指针加一 
    		s -> data[s -> top] = e;		//新插入的元素进栈 
    		return true;
    	 } 
    }
    
    void traverse(myStack s)		//遍历栈中元素并进行打印 
    {
    	int i = 0;
    	while(i <= s.top)			 
    		visit(s.data[i++]);
    	printf("\n");
    } 
    
    bool pop(myStack *s, elementype *e)		//栈顶元素出栈 
    {
    	if(s -> top == -1)
    		return false;
    	else
    	{
    		*e = s -> data[s -> top];
    		s -> top--;			//栈顶指针减一 
    		return true;
    	}
    }
    
    int main()
    {
    	myStack s;				
    	int j, e;
    	if(initstack(&s) == 1)
    	{
    		for(j = 1;j <= 10;j++)
    			push(&s, j);
    	}
    	puts("进栈之后的元素依次为： ");
    	traverse(s);
    	
    	pop(&s, &e);
    	printf("弹出的栈顶元素为 %d \n", e);
    	printf("弹出栈顶元素之后的栈是否为空(1:空 0:否)%d\n", stackempty(s));
        getTop(s, &e);
        printf("栈顶元素 e=%d 栈的长度为%d\n", e, length(s));
    	ClearStack(&s);
    	printf("清空栈后，栈空否：%d(1:空 0:否)\n",stackempty(s));
    	return 0;
    }

*测试结果代码*![在这里插入图片描述][20190125154326251.png]

[20190125150034385.png]: /images/20220322/0f35317b81474e6d81f7a982649f48dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]: /images/20220322/be3c4ebadbda4489a6f3ccefeeac8e9b.png
[20190125152004855.png]: /images/20220322/bd8fb9f2ee5446a0a60dec908256a3ed.png
[20190125152225706.png]: /images/20220322/aa3d7bf1ad1842898d02498ee4392357.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 1]: /images/20220322/ac9edb70308740edb0f32aadda3eb008.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 2]: /images/20220322/7cf8761088bb4269bbb7883446e3d125.png
[20190125153111686.png]: /images/20220322/72a199eecb4e4a74850d38204c4e2d82.png
[20190125153016488.png]: /images/20220322/541bc14f49f6484b9722dbf88852e219.png
[20190125153347627.png]: /images/20220322/e89e84b0fe364bd0828d740efa761c84.png
[2019012515400969.png]: /images/20220322/edf52491c92d4406a66cddd3886eea7c.png
[20190125154326251.png]: /images/20220322/e354c02b34a44c17b5e90918defccb8c.png