栈与一般线性表不同的是，它只能在同一个方向进和出，由实现方法分成顺序栈和链栈，我们首先实现顺序栈。

我们建立一个头文件（zhan.h）用于建立结构体与函数等。

#include<iostream>
#include<string.h>
using namespace std;

在一些教材中length会被换成尾指针，这里的length只是比尾指针的值大了1而已，没有本质区别。

struct Stack  //用顺序存储结构建立栈
{
	char data[50];
	int length;
};

void initStack(Stack*& s)//初始化一个空栈
{
	s = (Stack*)malloc(sizeof(Stack));
	s->length = ;
}

void createStack(Stack*& s, char ass[]) //用ass中的数据给栈赋值，从栈底向栈顶赋值
{
	s = (Stack*)malloc(sizeof(Stack));
	int i, n;
	n = strlen(ass) / sizeof(ass[]);
	s->length = n;
	for (i = ; i < n; i++)
		s->data[i] = ass[i];
}

void destroyStack(Stack*& s) //销毁栈
{
	free(s);
}

bool emptyStack(Stack*& s)  //确定栈是否为空
{
	return (s->length == );
}

void Push(Stack*& s, char e)  //进栈
{
	if (s->length == 50)
		cout << "栈已满" << endl;
	else
	s->data[s->length] = e;
	s->length = s->length + 1;
}

void Pop(Stack*& s, char &e)  //出栈
{
	if (s->length == )
		cout << "栈空" << endl;
	else
	e = s->data[s->length - 1];
	s->data[s->length - 1] = NULL;
	s->length = s->length - 1;
}

char getTop(Stack*& s)  //取栈顶元素
{
	if (s->length == )
	{
		cout << "栈空" << endl;
		return ;
	}
	else
	return s->data[s->length - 1];
}

下面是验证代码。

#include<iostream>
#include<math.h>
#include<string.h>
#include"zhan.h"
using namespace std;
int main()
{
	char x = '5', a[27] = "abcdefghijklmnopqrstuvwxyz";
	Stack *sta;
	initStack(sta);
	createStack(sta, a);
	cout << emptyStack(sta) << endl;
	Push(sta, 'a');
	cout << getTop(sta) << endl;
	int i;
	for (i = ; i < 20; i++)
	{
		Pop(sta, x);
		cout << x;
	}
	cout << endl << sta->length;
}

下面实现链栈，我们用头结点表示栈顶，创建栈只需用头插法就好了。

struct sNode  //用链式存储结构存储栈
{
	char data;
	sNode* next;
};

void initStack2(sNode *&s)  //初始化空栈
{
	s = (sNode*)malloc(sizeof(sNode));
	s->next = NULL;
}

void createStack2(sNode*& s,char ass[])  //头插法用ass创建栈
{
	s = (sNode*)malloc(sizeof(sNode));
	s->next = NULL;
	int i, n;
	n = strlen(ass) / sizeof(ass[]);
	sNode* p;
	for (i = ; i < n; i++)
	{
		p = (sNode*)malloc(sizeof(sNode));
		p->data = ass[i];
		p->next = s->next;
		s->next = p;
	}
}

void destroyStack2(sNode*& s)  //销毁栈
{
	sNode* pre = s, * p = s->next;
	while (p != NULL)
	{
		free(pre);
		pre = p;
		p = p->next;
	}
	free(pre);
}

bool emptyStack2(sNode*& s)  //判断栈是否为空
{
	return s->next == NULL;
}

void Push2(sNode*& s, char e)  //进栈
{
	sNode* p;
	p = (sNode*)malloc(sizeof(sNode));
	p->data = e;
	p->next = s->next;
	s->next = p;
}

void Pop2(sNode*& s, char &e)  //出栈
{
	if (s->next == NULL)
		cout << "栈空";
	else
	{
		sNode* p;
		p = s->next;
		e = p->data;
		s->next = p->next;
		free(p);
	}
}

char getTop(sNode*& s)  //提取栈顶元素
{
	if(s->next == NULL)
		return ;
	else
	return s->next->data;
}

下面是链栈的验证程序

#include<iostream>
#include<math.h>
#include<string.h>
#include"zhan.h"
using namespace std;
int main()
{
	char x = '5', a[27] = "abcdefghijklmnopqrstuvwxyz";
	sNode *sta2;
	initStack2(sta2);
	createStack2(sta2, a);
	cout << emptyStack2(sta2) << endl;
	Push2(sta2, 'a');
	cout << getTop(sta2) << endl;
	int i;
	for (i = ; i < 20; i++)
	{
		Pop2(sta2, x);
		cout << x;
	}
}

ITPub博客

数据结构与算法实现代码（4）——栈

最新文章