栈的基本操作

一、顺序栈的基本操作

顺序栈的特点:

顺序存储,使用数组实现,并需记录栈顶指针;

基本操作:创增删改 都是O(1)时间复杂度

存储结构:

#include <stdio.h>
#include <stdlib.h>
#define Stack_Init_Size 10		//顺序表初始化的长度(宏定义后面不要加;加了就连;也会替换)
#define StackIncrement 10		//顺序表满后开辟空间的长度
typedef int ElemType;
typedef int Status;

typedef struct {
	ElemType *base;		//栈底指针
	ElemType *top;		//栈顶指针
	int stacksize;		//栈的最大容量
} Stack, *SqStack;

函数列表:

  • Status InitStack(SqStack *S) 初始化栈
  • Status GetTopStack(SqStack *S, ElemType *e) 获取栈顶元素,参数e存放栈顶元素的值
  • Status PushStack(SqStack *S, ElemType e) 进栈,将元素e入栈
  • Status PopStack(SqStack *S, ElemType *e) 出栈,出栈的元素存放在参数e中
  • Status EmptyStack(SqStack *S) 判断栈是否为空
  • Status LengthStack(SqStack *S) 获取栈的实际长度
  • Status DestroyStack(SqStack *S) 销毁栈
  • Status StackTraverse(SqStack *S) 遍历栈,打印每个元素

完整代码

#include <stdio.h>
#include <stdlib.h>
#define Stack_Init_Size 10		//顺序表初始化的长度(宏定义后面不要加;加了就连;也会替换)
#define StackIncrement 10		//顺序表满后开辟空间的长度
typedef int ElemType;
typedef int Status;

typedef struct {
	ElemType *base;		//栈底指针
	ElemType *top;		//栈顶指针
	int stacksize;		//栈的最大容量
} Stack, *SqStack;

//初始化栈
Status InitStack(SqStack S) {
	S->base = (ElemType *) malloc(10 * sizeof(ElemType));
	if (!S->base) {
		return 0;
	}
	S->top = S->base;
	S->stacksize = Stack_Init_Size;
	return 1;
}

//获取栈顶的元素,参数e存放栈顶元素的值
Status GetTopStack(SqStack S, ElemType *e) {
	if (S->top == S->base) {
		return 0;
	}
	*e = *(S->top - 1);
	return 1;
}

//进栈,将元素e入栈
Status PushStack(SqStack S, ElemType e) {
	if (S->top - S->base >= S->stacksize) {
		//如果栈满了,用realloc函数重新分配空间大小
		S->base = (ElemType *)realloc(S->base, (S->stacksize + StackIncrement) * sizeof(ElemType));
		if (!S->base) {
			return 0;
		}
		S->top = S->base + S->stacksize;	//栈顶指针为栈底指针加上未重新分配内存前的最大长度
		S->stacksize += StackIncrement;		//栈的最大容量+10
	}
	*S->top++ = e;							//元素进栈,栈顶指针后移
	return 1;
}

//出栈,出栈的元素存放在参数e中
Status PopStack(SqStack S, ElemType *e) {
	if (S->base == S->top) {				//判断栈是否为空
		return 0;
	}
	S->top--;								//栈顶指针前移
	*e = *S->top;							//栈顶指针指向的元素返回
	return 1;
}

//判断栈是否为空
Status EmptyStack(SqStack S) {
	return S->base == S->top ? 1 : 0;
}

//获取栈的实际长度
Status LengthStack(SqStack S) {
	return S->top - S->base;
}

//销毁栈
Status DestroyStack(SqStack S) {
	free(S->base);					//free函数释放base指针指向的内存
	S->base = S->top = NULL;		//将base和top指向NULL
	S->stacksize = 0;
	return 1;
}

//遍历栈,采用先进后出的方式
Status StackTraverse(SqStack S) {
	if (S->base == S->top) {
		printf("这是空栈。");
		return 0;
	}
	ElemType *p = S->top;			//由于top和base指针遍历都不能移动,所以需要一个新的指针作为游标
	while (p > S->base) {
		p--;
		printf("%d ", *p);
	}
}

void main() {
	Stack q, *S;
	S = &q;
	int i, n, e;
	printf("创建一个空栈....\n");
	InitStack(S);
	printf("请输入栈的长度:\n");
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		printf("请输入第%d个元素:", i + 1);
		scanf("%d", &e);
		PushStack(S, e);
	}
	printf("栈满后再进栈:\n");
	PushStack(S, 100);
	printf("这个栈是否为空?");
	if (EmptyStack(S)) {
		printf("  是");
	} else {
		printf("  否\n");
	}
	printf("栈的长度为%d\n", LengthStack(S));
	printf("遍历栈的元素:\n");
	StackTraverse(S);
	printf("销毁栈\n");
	DestroyStack(S);
	StackTraverse(S);
}

二、链栈的基本操作

链栈的特点

它能够克服用数组实现的顺序栈空间利用率不高的特点,但是需要为每个栈元素分配额外的指针空间用来存放指针域

顺序栈和链栈的比较

二者的时间复杂度都为O[1],对于空间性能,顺序栈需要事先确定一个固定大小的数组空间,可能会存在内存空间浪费的问题,但是存取时定位很方便。链栈则要求每个元素都有指针域,增加了内存空间,但对于栈的长度没有限制。
如果数据元素变化不太大,那么使用顺序栈比较好,如果使用过程中数据元素变化很大,使用链栈比较好。

函数列表

  • void init(PSTACK); //初始化栈
  • void push(PSTACK, int ); //进栈
  • void traverse(PSTACK); //遍历栈
  • bool pop(PSTACK, int *); //出栈
  • bool empty(PSTACK pS);//判空
  • void clear(PSTACK pS); //销毁栈

完整代码

# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>
# include <stdbool.h>		//这里引入stdbool头文件是为了可以使用bool

typedef struct Node {		//这个是节点的存储结构
	int data;				//data存储数据
	struct Node *pNext;		//pNext指向下一个节点,和链表一样
} NODE, * PNODE;

typedef struct Stack {		//这是栈的存储结构
	PNODE pTop;				//栈顶指针
	PNODE pBottom;			//栈底指针
} STACK, * PSTACK; //PSTACK 等价于 struct STACK *


//初始化栈,先为栈顶或栈底指针分配一个节点的内存,再让两者相等,最后两者的pNext=NULL;
void init(PSTACK pS) {
	pS->pTop = (PNODE)malloc(sizeof(NODE));
	if (NULL == pS->pTop) {
		printf("动态内存分配失败!\n");
		exit(-1);						//相当于Java的异常,参数为零正常终止程序,不为0则表示非正常运行导致终止程序;
	} else {
		pS->pBottom = pS->pTop;
		pS->pTop->pNext = NULL; //pS->Bottom->pNext = NULL;
	}
}

//进栈,先创建一个新节点保存数据,再让新节点pNext指向栈顶指针,最后将栈顶指针指向新节点
//相当于链表的尾插法
//牺牲一个头节点
void push(PSTACK pS, int val) {
	PNODE pNew = (PNODE)malloc(sizeof(NODE));

	pNew->data = val;
	pNew->pNext = pS->pTop; //pS->Top不能改成pS->Bottom
	pS->pTop = pNew;

	return;
}

//遍历栈,将一个节点指针指向栈顶指针,从栈顶往栈底遍历(先进后出)
//每次遍历检查p是否等于栈底指针,等于则遍历结束,否则输出数据并更新节点指针的位置p = p->pNext;
void traverse(PSTACK pS) {
	PNODE p = pS->pTop;

	while (p != pS->pBottom) {
		printf("%d  ", p->data);
		p = p->pNext;
	}
	printf("\n");

	return;
}

//判断栈是否为空
bool empty(PSTACK pS) {
	if (pS->pTop == pS->pBottom)
		return true;
	else
		return false;
}

//出栈,先将一个节点指针作为游标指针指向栈顶,再保存栈顶的数据,然后栈顶指针下移指向自己的pNext,最后释放游标指针
bool pop(PSTACK pS, int *pVal) {
	if ( empty(pS) ) {
		return false;
	} else {
		PNODE r = pS->pTop;
		*pVal = r->data;
		pS->pTop = r->pNext;
		free(r);
		r = NULL;

		return true;
	}
}

//clear清空,而不是销毁
void clear(PSTACK pS) {
	if (empty(pS)) {
		return;
	} else {
		PNODE p = pS->pTop;
		PNODE q = NULL;

		while (p != pS->pBottom) {
			q = p->pNext;
			free(p);
			p = q;
		}
		pS->pTop = pS->pBottom;
	}
}

int main(void) {
	STACK S;  //STACK 等价于 struct Stack
	int val;

	init(&S);  //目的是造出一个空栈
	push(&S, 1); //压栈
	push(&S, 2);
	push(&S, 3);
	push(&S, 4);
	push(&S, 5);
	push(&S, 6);
	traverse(&S); //遍历输出
	printf("链表是否为空: ");
	empty(&S) ? printf("是\n") : printf("否\n");
	clear(&S);
	printf("链表是否为空: ");
	empty(&S) ? printf("是\n") : printf("否\n");
	//traverse(&S); //遍历输出

	if ( pop(&S, &val) ) {
		printf("出栈成功,出栈的元素是%d\n", val);
	} else {
		printf("出栈失败!\n");
	}

	traverse(&S); //遍历输出

	return 0;
}

点赞

发表回复

电子邮件地址不会被公开。必填项已用 * 标注