栈

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 526 阅读时长 ≈ 2 分钟

栈是一种先进后出的线性数据结构，规定只允许在一端进行插入和删除元素的操作。其中进栈操作又叫做压栈（Push），出栈操作又叫做弹出（Pop）。允许进行操作的一端叫做栈顶（top），另一端叫做栈底（base）。

分类

  • 顺序栈：数组实现
  • 链式栈：链表实现

代码实现

顺序栈

stack
1.构建栈的结构

1
2
3
4
5
#define MAXSIZE 1024		//定义栈的空间大小
typedef struct stack{
  int data[MAXSIZE];	
  int top;
}Stack;

2.初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
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.判断栈是否为空

1
2
3
4
5
6
7
int isEmpty(Stack* stack){
  	if(stack->top == -1){
  		printf("The stack is empty!");
      	return 1;
	}
  	return 0;
}

4.判断栈是否满

1
2
3
4
5
6
7
int isFull(Stack* stack){
  	if(stack->top == MAXSIZE-1){
  		printf("The satck is full!");
      	return 1;
	}
  	return 0;
}

5.进栈操作（Push）

1
2
3
4
5
6
void Push(Stack* stack,int item){
  	if(isFull(stack)){
  		return;
	}
  	stack->data[++stack->top] = item;
}

入站操作先移动Top，再压入元素

6.出栈操作（Pop）

1
2
3
4
5
6
int Pop(Stack* stack){
  	if(isEmpty(stack)){
  		return -99;
	}
  	return stack->data[stack->top--];	//返回被弹出的元素
}

7.遍历操作

1
2
3
4
5
6
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]);
	}
}
链式栈

stack1
1.构建栈的结构

1
2
3
4
typedef struct node{
  	int data;
  	struct node* next;
}Node;

2.初始化栈

1
2
3
4
5
6
7
8
9
10
11
12
13
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.判断栈是否为空

1
2
3
int isEmpty(Node* s){
  	return (s->next == NULL);
}

4.进栈操作

1
2
3
4
5
6
7
8
9
10
11
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.出栈操作

1
2
3
4
5
6
7
8
9
10
11
12
13
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.遍历操作

1
2
3
4
5
6
7
8
9
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;
	}
}