数据结构:栈和队列

一.栈

栈是一种特殊的线性表,它只允许在固定的一端进行插入或删除,进行插入或删除的一段叫栈顶,另一端叫栈底,栈中的元素遵循"后进先出"的原则

1.压栈

栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶

2.出栈

栈的删除操作叫出栈,出数据也在栈顶

栈的实现

栈可以通过数组和链表两种方式实现

如果使用单链表实现栈,在尾节点方便插入数据,但想要删除数据,就需要遍历链表,因此需要在单链表中将头节点作为栈顶

使用数组实现栈的插入删除更为方便,且效率更高,不过需要扩容(扩容的消耗不大)

typedef int STDataType;

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

void STInit(Stack* ps);
void STDestory(Stack* ps);
//栈顶
void STPush(Stack* ps,STDataType x);
void STPop(Stack* ps);
STDataType STTop(Stack* ps);
int STSize(Stack* ps);
bool STEmpty(Stack* ps);

void STInit(Stack* ps)//栈的初始化
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	//top=0,则top指向栈顶元素的下一个
	ps->capacity = 0;
}

void STDestory(Stack* ps)//销毁栈
{
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void STPush(Stack* ps, STDataType x)//入栈(栈顶插入)
{
	assert(ps);
	//扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* temp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (temp == NULL)
		{
			perror("realloc fail");
			return;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void STPop(Stack* ps)//出栈(栈顶删除)
{
	assert(ps);
	assert(!STEmpty(ps));//判断top是不是NULL
	ps->top--;
}

STDataType STTop(Stack* ps)//取栈顶的值
{
	assert(ps);
	assert(!STEmpty(ps));
	return ps->a[ps->top - 1];
}

int STSize(Stack* ps)//栈的大小
{
	assert(ps);
	return ps->top;
}

bool STEmpty(Stack* ps)//判断栈是否为空
{
	assert(ps);

	return ps->top == 0;
}

栈的打印

	Stack s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);	
	STPush(&s, 4);

	while (!STEmpty(&s))
	{
		int top = STTop(&s);
		printf("%d", top);
		STPop(&s);
	}