ZJU数据结构2019春堆栈的数组和链表实现

才开始学习数据结构，实现了一个简单的堆栈实例。就是把输出的数字倒序打印。
分别使用数组和链表实现。

类型名称: 堆栈（Stack）
数据对象集：一个有0个或多个元素的有穷线性表。
操作集：长度为MaxSize的堆栈S Stack，堆栈元素item ElementType
1、Stack CreateStack( int MaxSize )：生成空堆栈，其最大长度为MaxSize；
2、int IsFull( Stack S, int MaxSize )：判断堆栈S是否已满；
3、void Push( Stack S, ElementType item )：将元素item压入堆栈；
4、int IsEmpty ( Stack S )：判断堆栈S是否为空；
5、ElementType Pop( Stack S )：删除并返回栈顶元素；

※另外注意Windows下发送EOF是Ctrl+Z，我一直以为是Ctrl+C……

链表型堆栈实现

头结点s数据域不存放数据，只利用其指针域。
原理图：
刚创建时的s：
ZJU数据结构2019春堆栈的数组和链表实现
Push一次（比如一个666）：

再Push一次（比如一个233）：

可以看到，相当于在s和s->next之间插入了一个节点

Pop时：
相当于把s紧邻节点（称为FirstNode）删除，即s继承FirstNode的后继，然后2号节点保存值，之后释放节点，并返回值。
ZJU数据结构2019春堆栈的数组和链表实现

#include <stdio.h>
#include <stdlib.h>
#define ERROR -1//ElementType的特殊返回值，表示不存在
typedef int ElementType;//把int取个别名叫ElementType
//这样以后修改这里的int就可以换成别的数据类型，相当于变相实现了模板类
typedef struct _snode
{
	ElementType data;
	struct _snode* next;
}SNode;//真正的存储结构
typedef SNode* Stack;//只是个指针

Stack createStack();
int isEmpty(Stack s);//链表型的堆栈不存在满一说
void Push(Stack s,ElementType elem);
ElementType Pop(Stack s);

int main(int argc, char const *argv[])
{
	Stack lz=createStack();
	int num;
	while(scanf("%d",&num)!=EOF)
		Push(lz,num);
	while(!isEmpty(lz))
		printf("%d\n",Pop(lz) );
	return 0;
}

Stack createStack()
{
	Stack s=(Stack)malloc(sizeof(SNode));//注意申请的是SNode
	//头结点并不存储数据，只利用其指针域
	s->next=NULL;//指针域置空
	return s;
}

int isEmpty(Stack s)
{
	return (s->next==NULL);
}

void Push(Stack s,ElementType elem)
{
	Stack current=(Stack)malloc(sizeof(SNode));
	current->data=elem;
	//创建操作节点
	current->next=s->next;//头结点的后继后移
	s->next=current;//新节点成为头结点的直接后继
}

ElementType Pop(Stack s)
{
	if(isEmpty(s))
		return ERROR;
	Stack FirstNode=s->next;
	//头结点你不存储数据，真正存储数据的头结点是S->next
	//注意要判空
	ElementType value=FirstNode->data;
	//return和free不可兼得，需要一个临时变量
	s->next=FirstNode->next;
	free(FirstNode);
	//删除FirstNode,接上后面
	return value;
}

数组型堆栈实现

通过调整top游标实现。

注意：
1.别名Stack实际上是struct _stack的指针，在申请内存来放结构体时，应该是sizeof(struct _stack)。
2.数组malloc时是单个元素体积乘以元素数量
3.简单的返回值可以一行实现。

#include <stdio.h>
#include <stdlib.h>
#define ERROR -1
#define MAXSIZE 1000
typedef int ElementType;
struct _stack
{
	int* array;
	int top;
	int maxSize;
};
typedef struct _stack* Stack;

Stack createStack(int size);
int isFull(Stack S);
void Push(Stack S,int elem);
int isEmpty(Stack S);
int Pop(Stack S);

int main(int argc, char const *argv[])
{
	Stack s=createStack(MAXSIZE);
	ElementType num;
	while(scanf("%d",&num)!=EOF)
		Push(s,num);
	while(!isEmpty(s))
		printf("%d\n",Pop(s) );
	return 0;
}

Stack createStack(int size)
{
	Stack currentPtr=(Stack)malloc(sizeof(struct _stack));
	currentPtr->array=(ElementType*)malloc(sizeof(ElementType)*size);
	currentPtr->top=-1;
	currentPtr->maxSize=size;
	return currentPtr;
}

int isFull(Stack S)
{
	return (S->top==S->maxSize-1);
}

void Push(Stack S,ElementType elem)
{
	if(isFull(S))
		printf("The stack is full, the elem cannot join in.\n");
	else
		S->array[++S->top]=elem;
}

int isEmpty(Stack S)
{
	return (S->top==-1);
}

ElementType Pop(Stack S)
{
	if(isEmpty(S))
	{
		printf("Hollow!\n");
		return ERROR;
	}
	return (S->array[(S->top)--]);
}

ZJU数据结构2019春 堆栈的数组和链表实现

链表型堆栈实现

数组型堆栈实现

相关推荐

ZJU数据结构2019春堆栈的数组和链表实现