栈

栈的顺序存储结构及其基本运算实现

栈是一种只能在一端进行插入或删除操作的线性表其主要特点是：“后进先出”。

初始化结构体

# define MaxSize 100
typedef struct
{
	int data[MaxSize];    //存放栈中的数据元素
	int top;           //栈顶指针，即存放栈顶元素在data数组中的下标
}SqStack;              //顺序栈类型

四个要素 ：

栈空的条件：s->top---1；
栈满的条件：s->top==MsxSize-1(data数组的最大下标)；
元素e的进栈操作：先将栈顶指针top增1，然后将元素e放在栈顶指针处；
出栈的操作：先将栈顶指针top处的元素取出放在e中，然后将栈顶指针减1 ；

初始化栈

void InitStack(SqStack*& s)
{
	s = (SqStack*)malloc(sizeof(SqStack));
	s->top = -1;
}

销毁栈

void DestoryStack(SqStack*& s)
{
	free(s);
}

判断栈是否为空

bool StackEmpty(SqStack* s)
{
	return (s->top == -1);
}

 进栈

bool Push(SqStack*& s, int e)
{
	if (s->top == MaxSize - 1)
	{
		return false;
	}
	s->top++;
	s->data[s->top] = e;
	return true;
}

出栈

bool Pop(SqStack*& s, int e)
{
	if (s->top == -1)
	{
		return false;
	}
	e = s->data[s->top--];
	return true;
}

 取栈顶元素

bool GetTop(SqStack* s, int& e)
{
	if (s->top == -1)
	{
		return false;
	}
	e = s->data[s->top];
	return true;
}

 栈的应用：

        设计一个算法，利用顺序栈判断一个字符串是否是对称串。所谓对称串指从左向右读和从右向左读的序列相同。

bool symmetry(int str[])
{
	SqStack* s;
	InitStack(s);      //建立并初始化一个栈
	for (int i = 0; str[i] != '\0'; i++)
	{
		Push(s,str[i]);
	}                   //将字符串全部输入到栈中
	for (int i = 0; str[i] != '\0'; i++)
	{
		int e;
		Pop(s, e);
		if (str[i] != e)
		{
			DestoryStack(s);
			return false;
		}
	}                   //将字符串与栈中比较不同直接返回false
	DestoryStack(s);
	return true;
}

共享栈：

四个要素：

栈空条件：栈1空为top1==-1，栈2空为top2==MaxSize。

栈满条件：top1==top2-1。

元素x进栈的操作：进栈1操作为top1++；data[top1]=x；进栈2的操作为top2--；data[top2]=x。

出栈的操作：出栈1操作为x=data[top1--]；出栈2操作为x=data[top2++]; 

栈的链式存储结构及其基本运算实现

 链栈相对于顺序栈的优点是不存在栈满上溢出的情况。

结构体初始化

typedef struct linknode
{
	int data;             //数据域
	struct linknode* next;//指针域
}LinkStNode;

四个要素：

栈空的条件：s->next==NULL。

栈满的条件：不存在栈满。

元素e进栈的操作：新建一个节点存放元素e（由p指向它），将节点p插入到头结点之后。

出栈的操作：去除首节点的data值并将其删除。

初始化栈

void InitStack(LinkStNode*& s)
{
	s = (LinkStNode*)malloc(sizeof(LinkStNode));
	s->next = NULL;
}

销毁栈

void DestoryStack(LinkStNode*& s)
{
	LinkStNode* pre = s, * p = s->next;
	while (p != NULL)
	{
		free(pre);
		pre = p;
		p = pre->next;
	}
	free(pre);
}

判断栈是否为空

bool StackEmpty(LinkStNode* s)
{
	return (s->next == NULL);
}

 进栈

bool Push(LinkStNode*& s, int e)
{
	LinkStNode* p;
	p = (LinkStNode*)malloc(sizeof(LinkStNode));
	p->data = e;
	p->next = s->next;
	s->next = p;
	return true;
}

出栈

bool Pop(LinkStNode*& s, int& e)
{
	LinkStNode* p;
	if (s->next == NULL)
	{
		return false;
	}
	p = s->next;
	e = p->data;
	s->next = p->next;
	free(p);
	return true;
}

取栈顶元素

bool GetTop(LinkStNode* s, int& e)
{
	if (s->next == NULL)
	{
		return false;
	}
	e = s->next->data;
	return true;
}