[数据结构与算法]栈ADT--链表实现与数组实现

? ? ? ? 栈模型

????????栈是限制插入和删除只能在一个位置上进行的表，该位置为表的末端，叫做栈顶（top）

。对栈的基本操作有 Push（进栈）和Pop（出栈），前者相当于插入后者相当于删除。? ? ??????????

? ? ? ? 栈有时又叫做LIFO（后进先出-last in first out）。普通的清空栈的操作和判断是否空栈的测试都是栈的操作指令系统的一部分，但是对栈能够做的基本上也就是 Push 和 Pop 操作，也就是说清空栈是通过 Pop 操作来完成的，它没有操作栈，只是发出了一个指令让 Pop 来清空栈，而判断是否空栈也不需要操作栈。

? ? ? ? 栈的链表实现

????????第一种实现方法是使用单链表，通过在表前端插入实现 Push，删除表前端元素实现Pop。

? ? ? ? 类型声明：

typedef struct Node* PtrToNode;
typedef PtrToNode Stack;
typedef int ElementType;

struct Node
{
	ElementType element;
	PtrToNode next;
};

? ? ? ? 创建一个栈和创建结点：

? ? ? ??

Stack CreateStack()
{
	Stack stack = (Stack)malloc(sizeof(struct Node));
	if (stack != NULL)
	{
		stack->element = 0;
		stack->next = NULL;
	}
	return stack;
}
PtrToNode CreateNode()
{
	return CreateStack();
}

????????进栈和出栈：

void PushStack(Stack stack, ElementType x)
{
	PtrToNode tmpNode = CreateNode();
	if (tmpNode == NULL)
	{
		printf("out of space!!!\n");
	}
	else
	{
		tmpNode->element = x;
		tmpNode->next = stack->next;
		stack->next = tmpNode;
	}
}
void PopStack(Stack stack)
{
	if (IsEmpty(stack))
	{
		printf("empty stack");
	}
	else
	{
		PtrToNode tmpNode = stack->next;
		stack->next = tmpNode->next;
		free(tmpNode);
	}
}

????????判断是否为空、清空栈和释放栈：

int IsEmpty(Stack stack)
{
	return stack->next == NULL;
}
void MakeEmpty(Stack stack)
{
	if (stack == NULL)
	{
		printf("error stack\n");
		return;
	}
	while (!IsEmpty(stack))
		PopStack(stack);
}
void DisposeStack(Stack stack)
{
	MakeEmpty(stack);
	free(stack);
}

? ? ? ? 返回栈顶元素：

? ? ? ? 如果为空栈，则返回int_max值来表示，不过最好是直接报错

ElementType Top(Stack stack)
{
	if (IsEmpty(stack))
	{
		printf("empty stack");
		return _CRT_INT_MAX;
	}
	else
		return stack->next->element;
}

? 显然所有的操作均花费 常数时间，这种实现方法的确定是对malloc和free的调用的开销是昂贵的，因为栈一般需要频繁的进栈和出栈

? ? ? ? 栈的数组实现

? ? ? ? 这种方法避免了指针并且可能是更流行的解决方案，唯一的潜在危害是我们需要提前声明一个数组的大小，但一般不是问题，因为在典型应用程序种，即使有相当多的栈操作，在任意时刻栈元素的实际个数不会太大。声明一个足够大而不至于浪费太多的空间通常并没有什么困难。如果做不到这点，那么节省的做法是使用链表实现。? ? ? ?

? ? ? ? 用数组实现栈是很简单的。每一个栈有一个 topOfStack 表示它的栈顶，空栈它是-1。将某元素压入该栈，topOfStack 加1 ，stack[topOfStack] = X。其中的stack表示某一个具体栈的数组。为了弹出栈元素，置返回值为 stack[topOfStack]，topOfStack 减1。

? ? ? ? 当然，由于潜在地存在多个栈，因此 stack 数组和 topOfStack 是表示某个具体栈的一部分。使用全局变量和固定名字来表示这种（或任意）数据结构非常不好，在编写程序时我们应该尽可能严格地遵循模型，因为当多数实际情况下总是存在多个栈，这样除一些栈例程外，你的程序的任何部分都没有存取被每个栈蕴含的 数组 和 栈顶 变量的可能，这对所有ADT操作都是成立的。

? ? ? ? 类型声明：

#define EmptyTOS (-1)
#define MinStackSize (5)

typedef struct StackRecord* Stack;
typedef int ElementType;

struct StackRecord
{
	int capacity;
	int topOfStack;
	ElementType* array;
};

????????栈的创建：

Stack CreateStack(int maxElements)
{
	Stack stack = (Stack)malloc(sizeof(struct StackRecord));
	int realSize = maxElements > MinStackSize ? maxElements : MinStackSize;
	if (stack != NULL)
	{
		stack->capacity = realSize;
		stack->topOfStack = EmptyTOS;
		stack->array = (ElementType*)malloc(realSize * sizeof(ElementType));
		if (stack->array == NULL)
		{
			printf("error in creating array\n");
			return NULL;
		}
	}
	return stack;
}

? ? ? ? 判断空栈、满栈：

int IsEmpty(Stack stack)
{
	return stack->topOfStack == EmptyTOS;
}
int IsFull(Stack stack)
{
	return stack->topOfStack == stack->capacity - 1;
}

? ? ? ? 置空栈与释放栈：

void MakeEmpty(Stack stack)
{
	if (stack == NULL)
	{
		printf("error stack\n");
		return;
	}
	stack->topOfStack = EmptyTOS;
}
void DisposeStack(Stack stack)
{
	if (stack != NULL)
	{
		free(stack->array);
		free(stack);
	}
}

? ? ? ? 返回栈顶元素、出栈以及它们合二为一的操作：

void PopStack(Stack stack)
{
	if (IsEmpty(stack))
		printf("empty stack\n");
	else
		stack->topOfStack--;
}
ElementType TopStack(Stack stack)
{
	if (IsEmpty(stack))
	{
		printf("empty stack\n");
		return _CRT_INT_MAX;
	}
	else
		return stack->array[stack->topOfStack];
}
ElementType TopAndPop(Stack stack)
{
	if (IsEmpty(stack))
	{
		printf("empty stack\n");
		return _CRT_INT_MAX;
	}
	else 
		return stack->array[stack->topOfStack--];
}

? ? ? ? 入栈：

void PushStack(Stack stack, ElementType x)
{
	if (IsFull(stack))
		printf("Full stack\n");
	else
		stack->array[++stack->topOfStack] = x;
}

这就是栈的两种实现