Stack栈的实现

栈的基本概念及讨论

栈只允许在表固定的一端插入或者删除数据，这一端叫作栈顶，相对的另外一端就是栈底，对栈顶位的插入叫作入栈或压栈，删除叫作出栈。这样的数据结构有一个特点即后进先出LIFO(last in first off），也可以是先进后出，栈可以由数组表或者链表实现，当用数组实现时用数组的尾端作为栈顶，因为在数组尾的插入删除只需要O(1)的时间，同样若用单链表实现时，将链表头部的一端作为栈顶，也是由于O(1)的插入删除操作。栈的应用例子有很多，例如可以用于编译器判断符号是否平衡，函数调用。平衡符号若从左到右一一遍历符号，最后一个左括号一定会最先去匹配右括号，最开始的左括号一定最后才匹配到右括号。一般情况下最后调用的函数会最先释放。

栈的实现

我们这里用数组实现，因为栈是一种快速的结构，需要频繁的入栈和出栈，而链表则需要频繁的申请和释放空间，从性能上来说相对较差。

基本思想

一个变量记录容量，一个变量记录栈顶的位置，还有一个指针指向数组空间。

结构声明与函数声明

#pragma once
#include
#include
#include
#include
#define MINSIZE (4)
typedef char DataType;
typedef struct StackRecord StackRecord;
typedef struct StackRecord* Stack;
struct StackRecord
{
	DataType* data;
	int capacity;
	int top;
};

Stack CreateStack(size_t size);
void StackPush(Stack s, DataType x);
void StackPop(Stack s);
DataType StackTop(Stack s);
size_t StackSize(Stack s);
void StackPrint(Stack s);
int IsEmpty(Stack s);
int IsFull(Stack s);

初始化：

,这里将top初始化为-1，因为一开始没有数据，而一些程序员会将top初始化为0，则要注意这种情况top表示的就是栈顶位置的下一个位置。

Stack CreateStack(size_t size)
{
	Stack s = (Stack)malloc(sizeof(StackRecord));
	if (s == NULL)
	{
		printf("out of spaces!n");
		exit(-1);
	}
	s->top = -1;
	s->capacity = size > MINSIZE ? size : MINSIZE;
	s->data = (DataType*)malloc(sizeof(DataType) * s->capacity);
	if (s->data == NULL)
	{
		printf("out of spaces!n");
		exit(-1);
	}
	return s;
}

入栈与出栈：

void StackPush(Stack s, DataType x)
{
	assert(s);
	if (IsFull(s))
	{
		s->capacity *= 2;
		DataType* tmp = (DataType*)realloc(s->data, sizeof(DataType) * s->capacity);
		if (tmp == NULL)
			printf("push failed!,out of spaces!n");
		else
			s->data = tmp;
	}
	s->data[++s->top] = x;
}
void StackPop(Stack s)
{
	assert(s);
	if (!IsEmpty(s))
		s->top--;
}

判断空和满和返回栈大小：

int IsEmpty(Stack s)
{
	return s->top == -1;
}
int IsFull(Stack s)
{
	return s->top + 1 == s->capacity;
}
size_t StackSize(Stack s)
{
	assert(s);
	return s->top + 1;
}

返回栈顶元素和打印栈顶：

DataType StackTop(Stack s)
{
	assert(s);
	return s->data[s->top];
}
void StackPrint(Stack s)
{
	assert(s);
	while (!IsEmpty(s))
	{
		printf("%d", StackTop(s));
		StackPop(s);
	}
	printf("n");
}

实际上栈要求的基本操作只有入栈出栈，当写其它自己添加的操作时，要遵循栈的基本操作，如上述打印操作，使用者应该只能访问栈顶元素，这是栈数据结构所要求的，当使用者想打印栈时，也只能通过访问栈顶元素和出栈，去一个一个打印。所以要想打印栈是要付出代价的，需要将所有元素都出栈。