【栈和队列】栈

时间 2020-08-17 标签栈和队列栈

栈（stack） ，一种特殊的线性表

栈的定义

栈是一种限制只能在表尾进行插入或删除的线性表。表尾称为栈顶，表头称为栈底。

栈的修改是按后进先出的原则进行。

每次删除（退栈）的老是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最早插入的是被放在栈的底部，要到最后才能删除。

栈的基本运算

（1）InitStack（S）

　构造一个空栈S。

（2）StackEmpty（S）

　判栈空。若S为空栈，则返回TRUE，不然返回FALSE。

（3）StackFull（S）

　判栈满。若S为满栈，则返回TRUE，不然返回FALSE。
注意：

　该运算只适用于栈的顺序存储结构。

（4）Push（S，x）

　进栈。若栈S不满，则将元素x插入S的栈顶。

（5）Pop（S）

　退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。

（6）StackTop（S）

　取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。

栈的分类

顺序栈：

栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。算法

一、顺序栈的类型定义

#define STACK_INIT_SIZE 100;	//存储空间初始化分配量
#define STACKINCREMENT	10;		//存储空间分配的增量
typedef char SElemType;			//假设数据元素师char型
typedef struct
{
	SElemType * base;	//底部指针
	SElemType * top;	//栈顶指针
	int stacksize;		//当前已分配的存储空间，以元素为单位
}SqStack;

注意：
栈底位置是固定不变的，可设置在向量两端的任意一个端点
栈顶位置是随着进栈和退栈操做而变化的，用一个整型量top（一般称top为栈顶指针）来指示当前栈顶位置

二、顺序栈的基本算法实现

（1）初始化一个空栈

bool InitStack(SqStack * S)
{//构造一个空栈S	
	S->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if (!S->base)
	{
		exit(OVERFLOW);	//存储分配失败
	}
	S->top = S->base;	//栈顶位置为栈底位置
	S->stacksize = STACK_INIT_SIZE;
	return true;
}

（2）判断是否空栈

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

（3）取栈顶元素

bool GetTop(SqStack * S, SElemType * e)
{//若栈不空，则用e返回S的栈顶元素，并返回ture,不然返回false

	if (StackEmpty(S))
	{
		return false;
	}
	else
	{
		e = *(S->top - 1);
		return true;
	}
}

（4）进栈

bool Push(SqStack * S, SElemType e)
{//插入元素e为新的栈顶元素

	if (S->top - S->base >= S->stacksize)
	{//若是栈满，追加存储空间
		S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType));
		if (!S->base)
		{//分配失败
			exit(OVERFLOW);
		}
		S->top = S->base + S->stacksize;
		S->stacksize += STACKINCREMENT;
	}
	*S->top++ = e;	//插入元素
	return true;
}

（5）出栈

bool Pop(SqStack * S, SElemType * e)
{//若栈不空，则删除S的栈顶元素，用e返回其值
	if (StackEmpty(S))
	{
		return false;
	}
	else
	{
		S->top--;
		e = *(S->top);
		return true;
	}
}

链栈：

栈的链式存储结构称为链栈。spa

链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。
指针

一、链栈的类型定义

typedef struct stackNode
{
	SElemType data;
	struct stackNode * next;
}stackNode;

typedef struct stackqueue
{
	stackNode * base, *top;
}stackqueue;

2.链栈的基本算法实现

（1）初始化空栈code

bool InitStack(stackqueue * S)
{
	S->base = NULL;//初始化栈底指针
	S->top = NULL;//初始化栈顶指针
}

（2）判断空栈

bool StackEmpty(stackqueue * S)
{
	return S->base == NULL;
}

（3）进栈

void Push(stackqueue * S, SElemType e)
{
	stackNode *p = (stackNode *)malloc(sizeof(stackNode));	//先为新元素分配空间
	p->data = e;
	p->next = NULL;
	if (StackEmpty(S))
	{//若是是空栈
		S->base = p;
		S->top = p;
	}
	else
	{
		S->top->next = p;
		S->top = p;
	}
}

（4）出栈

bool Pop(stackqueue * S, SElemType * e)
{
	stackNode * p;
	if (StackEmpty(S))
	{
		return false;
	}
	else
	{
		*e = S->top->data;
		if (S->base == S->top)
		{//若是只有一个元素，则置为空栈
			S->base = NULL;
			S->top = NULL;
		}
		else
		{//找到指向原先栈顶的指针，将其置为栈顶
			p = S->base;
			while(p->next != S->top)
			{
				p = p->next;
			}
			S->top = p;
			S->top->next = NULL;
		}
	}
	return true;
}