栈

概念

• 栈：
  • 一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
  • 进行数据插入和删除操作的一端。称为栈顶，另一端称为栈底。
  • 栈中的数据元素遵守后进先出LIFO（Lastin FirstOut）的原则。
  • 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶
  • 出栈：栈的删除操作叫做出栈。出数据也在栈顶
  • 可通过顺序表或者链表实现。
    

顺序栈

有关top指针的位置·设定

• 如果初始化时，top指向的是0【数组的首地址】，意味着top指向栈顶数据的下一个。
• 如果初始化时，top指向的是-1【数组的首地址的前一个地址】，意味着top指向栈顶数据。
• 当然，top还有第三种的设定，使用两个指针base、top同时指向数组的首地址。
  

常见操作

• 定义的结构体

typedef int STDataType;
typedef struct  Stack
{
	STDataType* a;
	int top;
	int capacity;
} ST;

初始化

• 初识的top设定：top指向栈顶数据的下一个

void StachInit(ST* ps);

void StachInit(ST* ps) {
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

销毁

void StackDestroy(ST* ps);

void StackDestroy(ST* ps) {
	assert(ps);
	free(ps->a);
	ps->a = NULL;
}

入栈

void StackPush(ST* ps,STDataType x);

void StackPush(ST* ps, STDataType x) {
	assert(ps);
	//判断是否为空
	if (ps->top == ps->capacity) {
		//设置初始的长度为4，否则长度变原来的2倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		//开辟空间
		STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType)*newCapacity);
		if (tmp == NULL) {
			cout << "realloc fail\n" ;
		}
		//更新数组的地址、容量
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//入栈 先入数据，后改变指针
	ps->a[ps->top] = x;
	ps->top++;
}

出栈

void StackPop(ST* ps);

void StackPop(ST* ps) {
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

获取栈顶

STDataType StackTop(ST* ps);

STDataType StackTop(ST* ps) {
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

求栈的长度

int StackSize(ST* ps);

int StackSize(ST* ps) {
	assert(ps);
	return ps->top;
}

判空

bool StackEmpty(ST* ps);

bool StackEmpty(ST* ps) {
	assert(ps);
	return ps->top == 0;
}

链栈【具体操作先省略】

设定

说明

① 链栈不必设头结点，因为栈顶（表头）操作频繁，只在栈顶插入和删除，不在其他位置插入和删除，代码统一；
② 采用链栈存储方式，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。

顺序栈和链栈的比较。

• 总结：当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。