顺序栈

系统管理员 2022-04-22 03:06 200阅读 0赞

## 栈： ##

限定仅在表尾进行插入和删除操作的线性表。因此，对于栈来说，表尾有其特殊含义，称为栈顶，相应地，表头称为栈底。不含元素的空表称为空栈。

栈是一种“后进先出”的线性表，有压栈出栈两种操作方式。如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70][]

栈的表现形式有链栈和顺序栈。这里只提及顺序栈。

### **顺序栈的存储** ###

需要注意：非空栈中的栈顶指针始终在栈顶元素的下一个位置。

typedef struct
    {
        SElemType *base;
        SElemType *top;
        int stacksize;
    }SqStack;

## ##

### 栈的初始化 ###

bool InitStack(SqStack *S)
    {
        S->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
        if(!S->base)
        {
            printf("Storage allocation failure");
            exit(0);
        }
        S->top=S->base;
        return true;
    }

## ##

### 获得栈顶元素 ###

SElemType GetTop(SqStack *S)
    {
        return *(S->top-1);//top总是指向空，top-1指向栈顶元素
    }

### 入栈 ###

bool Push(SqStack *S,SElemType e)
    {
        if(S->top-S->base>=S->stacksize)
        {
            S->base=(SElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));
            if(!S->base)
            {
                printf("Storage allocation failure");
                exit(0);
            }
            S->top=S->base+S->stacksize;
            S->stacksize+=STACKINCREMENT;
        }
        *S->top++=e;
        return true;
    }

### 出栈 ###

bool Pop(SqStack *S)
    {
    	if(S->top==S->base)
    		return false;
    	--S->top;
    	return true; 
    }

### 判断栈是否为空 ###

bool Empty(SqStack *S)
    {
    	if(S->top==S->base)
    		return true;
    	else
    		return false;
    }

### 销毁栈 ###

void Del(SqStack *S)
    {
    	free(S->base);
    }

为了使用的方便，将上述函数封装成头文件，代码合成如下

//栈
    //dacao
    //2018/10/31
    
    #ifndef _STACK_H_
    #define _STACK_H_
    
    #include<stdio.h>
    #include<stdbool.h>//bool型头文件 
    #include<stdlib.h> 
    
    #define STACK_INIT_SIZE 100
    #define STACKINCREMENT 10
    
    #define SElemType int 
    
    typedef struct
    {
    	SElemType *base;
    	SElemType *top;
    	int stacksize; 
    }SqStack;
    
    
    /*初始化栈*/ 
    bool InitStack(SqStack *S)
    {
    	S->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    	if(!S->base)
    	{
    		printf("Storage allocation failure");
    		exit(0);
    	}
    	S->top=S->base;
    	return true;
    } 
    
    
    //获得栈顶元素 
    SElemType GetTop(SqStack *S)
    {
    	return *(S->top-1);//top总是指向空，top-1指向栈顶元素 
    }
    
    
    //入栈
    bool Push(SqStack *S,SElemType e) 
    {
    	if(S->top-S->base>=S->stacksize)
    	{
    		S->base=(SElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));
    		if(!S->base)
    		{
    			printf("Storage allocation failure");
    			exit(0);
    		}
    		S->top=S->base+S->stacksize;
    		S->stacksize+=STACKINCREMENT; 
    	}
    	*S->top++=e;
    	return true; 
    }
    
    
    bool Pop(SqStack *S)
    {
    	if(S->top==S->base)
    		return false;
    	--S->top;
    	return true; 
    }
    
    bool Empty(SqStack *S)
    {
    	if(S->top==S->base)
    		return true;
    	else
    		return false;
    }
    
    void Del(SqStack *S)
    {
    	free(S->base);
    }
    
    #endif

下面代码简单将其应用于十进制转化成八进制：

#include"stdio.h"
    #include"stack.h"
    
    
    //十进制转换成八进制
    void conversion(SqStack *S,int N)
    {
    	InitStack(S);
    	while(N)
    	{
    		Push(S,N%8);
    		N=N/8;
    	}
    	while(!Empty(S))
    	{
    		printf("%d",GetTop(S));
    		Pop(S);
    	}
    	Del(S);
    } 
    
    int main()
    {
    	SqStack S;
    	int N=15;
    	conversion(&S,N);
    	return 0;
    }

栈的练习：

[通过栈实现进制的转换][Link 1]

[迷宫求解——栈的实现][Link 2]

[栈实现运算表达式的求解][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70]: /images/20220422/e20af3c27060418fa7fd264e0d544075.png
[Link 1]: https://blog.csdn.net/sinat_38816924/article/details/79235032
[Link 2]: https://blog.csdn.net/sinat_38816924/article/details/79235640