C语言数据结构(4)——栈

• 1.栈的基本概念
• 2.栈的基本操作
• • 2.1基本数据类型
  • 2.2 初始化
  • 2.3 判断栈是否为空
  • 2.4 压栈
  • 2.5 弹栈
  • 2.6 获取栈顶元素
  • 2.7 获取当前栈的大小
  • 2.8 销毁栈
• 3.代码实操

栈是一种线性表，但限定这种线性表只能在一端进行插入和删除操作。

栈顶（Top）：线性表允许进行插入和删除的一端。

栈底（Bottom）：该端不允许进行插入和删除。

空栈：不含任何元素，top==bottom 。

如上图：a0为栈底元素，an为栈顶元素。由于栈只能在栈顶进行插入和删除操作，故进栈次序依次为a1=0，a2，… ,an 而出栈次序为an，…，a2，a1=0。栈的操作特征体现为后进先出（Last In First Out，LIFO）,或者先进后出（First In Last Out，LIFO），可以理解为手枪弹匣，最先压入弹匣的子弹将会最后被射出。

1). 初始化栈

void StackInit(ST* ps);

2). 判断栈是否为空

bool StackEmpty(ST* ps);

3). 压栈

void StackPush(ST*ps,STDataType x);

4). 弹栈

void StackPop(ST*ps)

5). 获取栈顶元素

STDataType StackTop(ST* ps);

6). 获取当前栈的大小

int StackSize(ST* ps);

7). 销毁栈

void StackDestroy(ST* ps);

由于线性表即可实现栈的结构，故单链表和顺序表皆可。本文将实现顺序表结构的栈。

#include 
#include 
#include 
#include 


typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;//栈顶位置
	int capacity;//容量
}ST;

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

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

void StackPush(ST* ps, STDataType x)//压栈
{
	if (ps->capacity == ps->top)
	{
		int newcapacity = (ps->capacity == 0) ? 4 : 2 * ps->capacity;
		STDataType* newspace = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		assert(newspace);
		ps->a = newspace;
		ps->capacity=newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

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

STDataType StackTop(ST* ps)
{
	assert(ps);

	return ps->a[ps->top-1];
}

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

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

teststack();
int main()
{
	teststack();
	return 0;
}

void teststack()
{
	ST st;
	StackInit(&st);
	
	//1 2 3 4 5 压栈
	printf(""1 2 3 4 5 压栈"n");
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);

	//打印栈 栈顶->栈底
	int Top = st.top;
	while (Top--)
	{
		printf("%d ", st.a[Top]);
	}
	printf("n");
	//获取栈顶元素+弹栈
	printf(""获取栈顶元素+弹栈"n");
	while (!StackEmpty(&st))
	{
		printf("%dn", StackTop(&st));
		StackPop(&st);
	}
	StackDestroy(&st);
}

青山不改 绿水长流