[数据结构与算法]数据结构与算法

栈

什么是栈？

栈：限定仅在一端进行插入或删除操作的线性表

栈的特点

根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最后放入的元素最后删除。

特点：后进先出(先进后出)

也就是说，栈是一种后进先出的线性表，简称LIFO（Last In First Out）表。

什么是链栈？

栈的链式存储结构简称链栈。

注意链表中指针的方向是从栈顶到栈底

因为栈的所有操作在栈顶进行，所以可以不需要头节点，栈顶指针就相当于链表的头指针。

链栈的结构类型

typedef ?? SElemType //由实际需要决定

typedef struct SNode
{
	SElmType data;//数据域
	struct SNode *next;//指针域
}SNode,*LStack;

LSatck S;//定义指向结点的指针s

/*------链栈的基本操作------*/

Status InitStack(LStack &S);
Status GetTop(LStack &S,SElemType  e);
Status Push(LStack &S,SElemType  e);
Status Pop(LStack &S,SElemType  e);

初始化栈
Status InitStack(LStack &S)
{
	 S = NULL；
	 return OK;
}



获取栈顶元素


Status GetTop(LStack S,SElemType  &e)
{
	if(!S )
		return ERROR;
			
		e = S->data;
		return OK;
}


入栈


Status Push(LStack &S,SElemType  e)
{
		LStack  p;
		p = (LStack )malloc(sizeof(SNode));
		if(p == NULL)
		{
				perror("malloc error");
				exit(-1);	
		}
		p->next = S;
		S = p;		
		return OK;	
}


出栈

Status Pop(LStack &S,SElemType &e)
{
	LStack p = S;
	if(!S)
	{
		printf("空栈/n");
		return ERROR;
	}
	e = S->data;
	S = p->next;
	free(p);
	p = NULL;
	return OK;
	
}

顺序栈的实现

typedef int SElemType

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SQSTACK_SIZE 100
#define SQSTACK_ADD_SIZE 20;

typedef int SElemType ;
typedef struct Sqstack
{
	SElemType *data;
	SElemType *top;
	SElemType sqstacksize;
} Sqstack,*pSqstack;

//顺序栈初始化
SElemType Sqstack_Init(pSqstack &S)
{
	S.data = (SElemType *)malloc(sizeof(Sqstack)* SQSTACK_SIZE );
	if(!S.data)
	{
			perror("malloc error");
			exit(-1);	
	}
	S.top = S.data;
	S.sqstacksize = SQSTACK_SIZE ;
	return OK;
}

//顺序入栈
SElemType Sqstack_Push(pSqstack &S,SElemType e)
{	
	if(S.top - S.base >= SQSTACK_SIZE )
	{
		S.data = (SElemType *)remalloc(S.data,sizeof(Sqstack)* SQSTACK_SIZE + SQSTACK_ADD_SIZE);
		if(!S.data)
		{
			perror("remalloc error");
			exit(-1);	
		}
		S.sqstacksize += SQSTACK_ADD_SIZE;
	}
	*S.top++ = e;
	return OK;
}
//顺序出栈
SElemType Sqstack_Pop(pSqstack &S,SElemType &e)
{
	if(S.top == S.base)
	{
		printf("空栈\n");
		return ERROR;
	}
	e = *--S.top;
	return OK;
}
//清空顺序栈
SElemType Sqstack_Clear(pSqstack &S)
{
	SElemType e;
	S.top = S.base;
	return OK;
}