栈
栈是一种先进后出的线性数据结构,规定只允许在一端进行插入和删除元素的操作。其中进栈操作又叫做压栈(Push),出栈操作又叫做弹出(Pop)。允许进行操作的一端叫做栈顶(top),另一端叫做栈底(base)。
¶ 分类
- 顺序栈:数组实现
- 链式栈:链表实现
¶ 代码实现
¶ 顺序栈
1. 构建栈的结构
#define MAXSIZE 1024 //定义栈的空间大小
typedef struct stack{
int data[MAXSIZE];
int top;
}Stack;
2. 初始化
Stack *Init(){
Stack stack;
stack = (Stack*)malloc(sizeof(Stack));
if(!stack){
printf("Memory allocation failed!");
return NULL;
}
else{
stack->top = -1; //C语言数组下标从0开始
printf("Init successfully!");
return stack;
}
}
3. 判断栈是否为空
int isEmpty(Stack* stack){
if(stack->top == -1){
printf("The stack is empty!");
return 1;
}
return 0;
}
4. 判断栈是否满
int isFull(Stack* stack){
if(stack->top == MAXSIZE-1){
printf("The satck is full!");
return 1;
}
return 0;
}
5. 进栈操作(Push)
void Push(Stack* stack,int item){
if(isFull(stack)){
return;
}
stack->data[++stack->top] = item;
}
入站操作先移动 Top,再压入元素
6. 出栈操作(Pop)
int Pop(Stack* stack){
if(isEmpty(stack)){
return -99;
}
return stack->data[stack->top--]; //返回被弹出的元素
}
7. 遍历操作
void Traverse(Stack* satck){
printf("The items in the stack are:\n");
for (int i=stack->top;i >= 0;i--){
printf ("%d\n",stack->data[i]);
}
}
¶ 链式栈
1. 构建栈的结构
typedef struct node{
int data;
struct node* next;
}Node;
2. 初始化栈
Node* Init(){
Node* s;
s = (Node*)malloc(sizeof(Node));
if(!s){
printf("Memory allocation failed!");
return NULL;
}
else{
printf("Init successfully!");
s->next = NULL;
return s;
}
}
3. 判断栈是否为空
int isEmpty(Node* s){
return (s->next == NULL);
}
4. 进栈操作
void Push(Node* s,int item){
Node* node; //为插入的元素构建一个节点
node = (Node*)malloc(sizeof(Node));
if(!node){
printf("Memory allocation failed!");
return NULL;
}
node->data = item;
node->next = s->next; //这里写成node->next = NULL应该也可以吧
s->next = node;
}
5. 出栈操作
int Pop(Node* s){
Node* Top;
int data;
if(isEmpty(s)){
printf("The stack is empty!");
return -99;
}
Top = s->next;
s->next = Top->next;
data = Top->data;
free(Top);
return data;
}
6. 遍历操作
void Traverse(Node* s){
printf("The items in the stack are:\n");
Node* p;
p = s;
while (p->next != NULL){
printf("%d\n",p->data);
p = p->next;
}
}