栈学习笔记

顺序栈

arrayStack.h

#pragma once

typedef int Element_t;
#define MaxStackSize	5

// 顺序栈的数据结构定义
typedef struct {
	Element_t data[MaxStackSize];
	int top;
} ArrayStack;

ArrayStack *createArrayStack();		// 为其他模块提供操作栈结构的接口
void releaseArrayStack(ArrayStack *stack);

// 满递增栈
int pushArrayStack(ArrayStack *stack, Element_t e);
/* 弹栈：
 * V1: 把栈数据空间的内容更新，top改变，Element_t getTop();
		void popArrayStack(ArrayStack *stack);
 * V2: 弹栈的时候，先把栈顶元素的值更新给调用者，然后再更新top值
 */
int popArrayStack(ArrayStack *stack, Element_t *e);

arrayStack.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "arrayStack.h"

ArrayStack *createArrayStack() {
	// 1. 堆空间申请
	ArrayStack *stack = malloc(sizeof(ArrayStack));
	if (stack == NULL) {
		printf("malloc failed!\n");
		return NULL;
	}
	// 2. 初始化这个堆空间
	stack->top = -1;
	memset(stack->data, 0, sizeof(stack->data));
	// for (int i = 0; i < MaxStackSize; ++i) {
	// 	stack->data[i] = 0;
	// }
	// 3. 返回首地址
	return stack;
}

void releaseArrayStack(ArrayStack *stack) {
	if (stack) {
		free(stack);
	}
}

int pushArrayStack(ArrayStack *stack, Element_t e) {
	// 1. 考虑该栈可能出现OverFlow
	if (stack->top >= MaxStackSize - 1) {
		printf("OverFlow!\n");
		return -1;
	}
	// 2. 更新栈内空间的值
	++stack->top;
	stack->data[stack->top] = e;
	return 0;
}

int popArrayStack(ArrayStack *stack, Element_t *e) {
	// 1. 考虑栈会出现UnderFlow
	if (stack->top < 0) {
		printf("UnderFlow!\n");
		return -1;
	}
	// 2. 出栈，栈顶元素备份，更新top值
	Element_t x1 = stack->data[stack->top];
	--stack->top;
	// 3. 同时，调用者希望接收到弹出来的元素，将弹出来的栈顶元素更新给调用者
	if (e) {
		*e = x1;
	}
	return 0;
}

链式栈

LinkStack.h

#pragma once

typedef int value_t;
// 链式栈的节点结构
typedef struct _node {
	value_t data;
	struct _node *next;
} node_t;

typedef struct {
	node_t *top;
	int count;
} LinkStack;

LinkStack *createLinkStack();
void releaseLinkStack(LinkStack *stack);

int pushLinkStack(LinkStack *stack, value_t e);
int popLinkStack(LinkStack *stack, value_t *e);

LinkStack.c

#include <stdio.h>
#include <stdlib.h>
#include "linkStack.h"

LinkStack *createLinkStack() {
	LinkStack *stack = malloc(sizeof(LinkStack));
	if (stack == NULL) {
		return NULL;
	}
	stack->count = 0;
	stack->top = NULL;
	return stack;
}

void releaseLinkStack(LinkStack *stack) {
	node_t *tmp;
	if (stack) {
		while (stack->top) {
			tmp = stack->top;
			stack->top = tmp->next;
			free(tmp);
			--stack->count;
		}
		printf("stack count: %d\n", stack->count);
		free(stack);
	}
}

int pushLinkStack(LinkStack *stack, value_t e) {
	node_t *node = malloc(sizeof(node_t));
	if (node == NULL) {
		return -1;
	}

	node->data = e;
	node->next = stack->top;
	stack->top = node;
	++stack->count;
	return 0;
}

int popLinkStack(LinkStack *stack, value_t *e) {
	if (stack->top == NULL) {
		return -1;
	}
	value_t x1 = stack->top->data;
	node_t *tmp = stack->top;
	stack->top = tmp->next;
	free(tmp);
	--stack->count;
	if (e) {
		*e = x1;
	}
	return 0;
}

main.c

#include <stdio.h>
#include "arrayStack.h"
#include "linkStack.h"

void test01() {
	ArrayStack *stack1 = createArrayStack();
	if (stack1 == NULL) {
		return;
	}
	for (int i = 0; i < MaxStackSize; ++i) {
		pushArrayStack(stack1, i + 10);
	}
	printf("push 5 element!\n");
	pushArrayStack(stack1, 300);
	// 弹栈
	Element_t x1;
	for (int i = 0; i < MaxStackSize; ++i) {
		popArrayStack(stack1, &x1);		// scanf("%d", &x1);
		printf("%d\t", x1);
	}
	printf("\npop 5 element!\n");
	popArrayStack(stack1, NULL);

	releaseArrayStack(stack1);
}

void test02() {
	LinkStack *stack2 = createLinkStack();
	if (stack2 == NULL) {
		return;
	}
	for (int i = 0; i < MaxStackSize; ++i) {
		pushLinkStack(stack2, i + 10);
	}
	printf("push 5 element!\n");
	pushLinkStack(stack2, 300);

	value_t x1 = 0;
	int ret = 0;
	// while (popLinkStack(stack2, &x1) != -1) {
	// 	printf("%d\t", x1);
	// }
	// printf("\n");
	releaseLinkStack(stack2);
}

int main() {
	test02();

	return 0;
}