栈

栈是一种先进后出的线性数据结构，规定只允许在一端进行插入和删除元素的操作。其中进栈操作又叫做压栈（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;
	}
}