栈：Linux内存中的栈空间就是基于此设计的，栈遵循“后进先出”的原则。也被成为“LIFO”结构，意思是“last input first output”。进栈（PUSH）、出栈（POP）。
1.顺序栈
顺序栈：一般是把数组头作为栈底，数组头部到数组尾部作为栈的增长方向bottom为首元素地址，top为最后元素下标。
- 结构体
typedef struct {DataType_t *bottom; //栈底，数组的指针unsigned int size;int top; //当前已使用的元素个数（索引）
} Sqstack_t;
- 创建一个顺序栈
Sqstack_t* SqStack_create(unsigned int size)
{Sqstack_t *manage=(Sqstack_t *)calloc(1,sizeof(Sqstack_t));if(!manage){perror("calloc manage failed");return NULL;}manage->bottom=(DataType_t *)calloc(size,sizeof(DataType_t));if(!manage->bottom){ //给数组分配空间perror("calloc bottom failed");free(manage);return NULL;}manage->size=size; //容量manage->top=-1; //-1表示栈空return manage;
}
- 入栈
bool SqStack_Push(Sqstack_t *list,DataType_t value)
{if(list->top+1>=list->size){printf("stack is full\n");return false;}list->bottom[++list->top]=value; //入栈return true;
}
- 出栈
DataType_t SqStack_Pop(Sqstack_t *list)
{if(list->top==-1){printf("stack is empty\n");return -1;}return list->bottom[list->top--]; //出栈
}
- 遍历顺序栈
void SqStack_Print(Sqstack_t *list)
{if(list->top == -1){printf("list is empty\n");return;}for(int i=0;i<=list->top;i++){ //遍历栈printf("%d ",list->bottom[i]);}
}
2.链式栈
链式栈：一般是把链表头部作为栈顶，方便数据的插入和删除（头插+头删），top为头结点，top->next为首结点，top->next为空时，栈空。
- 结构体
typedef int DataType_t;
typedef struct Node{DataType_t data;struct Node* next;
}Node_t;
- 创建一个链式栈
Node_t* CreateLinkStack()
{Node_t* top = (Node_t*)malloc(sizeof(Node_t));if(top == NULL){printf("内存分配失败\n");exit(-1);}top->next = NULL;return top;
}
- 新建一个节点
Node_t* CreateNode(DataType_t value)
{Node_t* newNode = (Node_t*)malloc(sizeof(Node_t));if(newNode == NULL){printf("内存分配失败\n");exit(-1);}newNode->data = value;newNode->next = NULL;return newNode;
}
- 入栈
bool LinkStack_Push(Node_t* top, DataType_t value)
{Node_t* newNode = CreateNode(value);if(newNode == NULL){return false;}newNode->next = top->next;top->next = newNode;return true;
}
- 出栈
DataType_t LinkStack_Pop(Node_t* top)
{if(top->next == NULL){ // 链式栈为空printf("链式栈为空，无法删除节点\n");return; }Node_t* temp = top->next;DataType_t poppedValue = temp->data;top->next = temp->next;free(temp);return poppedValue;
}
- 遍历顺序栈
bool Print_LinkStack(Node_t* top)
{if(top->next == NULL){ // 链式栈为空printf("链式栈为空\n");return false;}Node_t* current = top->next;while(current){printf("%d -> ", current->data); current = current->next; }printf("NULL\n");return true;
}