数据结构之栈
2018 algorithm栈是一个抽象的线性数据结构，遵循后进先出 LIFO(Last In First Out)的原则，也就是说只能通过一端来实现数据存储和检索。在栈中进行插入和删除操作的一端称为栈顶(top)，另一端称为栈底(bottom)。
不含有数据元素的栈称为空栈。可以通过数据(Array)，链表(Linked List)实现栈。
栈的操作
- 入栈：添加一个数据元素到集合中
- 出栈：移除最近添加尚未移除的数据元素
栈的实现
栈可以通过数组和链表实现。
数组实现栈
// 栈的结构体
struct Stack {
int top;
unsigned capacity;
int* array;
}
// 创建给定大小的栈，并初始化栈的大小为0
struct Stack* createStack(unsigned capacity) {
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = 0;
stack->array = (int*) malloc(stack->capacity * sizeof(int));
return stack;
}
// 判断是否为满栈
int isFull(struct Stack* stack) {
return stack->top == stack->capacity;
}
// 判断是否为空栈
int isEmpty(struct Stack* stack) {
return stack->top == 0;
}
// 入栈操作，顶部+1
void push(struct Stack* stack, int item) {
if (isFull(stack)) return;
stack->array[stack->top] == item;
stack->top++;
}
// 出栈操作，返回数据项，顶部-1
int pop(struct Stack* stack) {
if (isEmpty(stack)) return;
stack->top--;
return stack->array[stack->top];
}
链表实现栈
// 栈的结构体
struct stackNode {
int data;
struct StackNode* next;
}
// 初始化一个栈
struct StackNode* newNode(int data) {
struct StackNode* stackNode = (struct StackNode*) malloc(sizeof(struct StackNode));
stackNode->data = data;
stackNode->next = NULL;
return stackNode;
}
// 判断是否为空栈
int isEmpty(struct StackNode *stack) {
return !stack;
}
// 入栈操作
void push(struct StackNode** stack, int data) {
struct StackNode* stackNode = newNode(data);
stackNode->next = *stack;
*stack = stackNode;
}
// 出栈操作，返回出栈的数据项
int pop(struct StackNode** stack) {
if (isEmpty(*stack)) return Error;
struct StackNode* temp = *stack;
*stack = (*stack)->next;
int result = temp->data;
free(temp);
return result;
}
// 查看栈顶部数据项
int peek(struct StackNode* stack) {
if (isEmpty(stack)) return Error;
return stack->data;
}
操作系统里的堆栈
操作系统里面的堆和栈都是内存中的一部分。
栈(Stack)：
- 栈是作为执行线程的临时空间留出的内存。
- 由编译器自动申请，自动释放。
- 栈的变量分配比堆的变量分配快。
- 操作方式使用数据结构中的栈实现。
- 用于存储本地变量，返回地址，传递参数。
- 栈的存储地址是连续且有限，申请过多时会出现栈溢出。(例如：无限的递归，申请空间过大)
- 可以在没有指针的情况下,可以创建栈的数据。
- 栈的大小在程序编译期间已经确定大小。
堆(Heap):
- 堆是动态分配的内存。
- 变量是手工申请，销毁，而且不会越界。
- 堆的变量分配比栈的变量分配慢。
- 根据用户程序按需分配数据块。
- 大量的分配和撤销容易产生碎片。
- 在 C++或者 C，堆上创建的数据由指针指向，并且分别由
new和malloc分配。 - 如果请求分配的缓存过大，可能出现分配实拍的情况。
- 如果你不能确切地知道你运行时需要多大的数据或者你需要分配大量的数据，应该使用堆。
- 负责内存泄漏。