顺序栈

栈：

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

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

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

顺序栈的存储

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

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;
} 

 

栈的练习：

通过栈实现进制的转换

迷宫求解——栈的实现

栈实现运算表达式的求解