数据结构个人笔记 第9课 栈

• 栈
• • 进栈和出栈
  • 栈的具体实现
  • 栈的应用
• 顺序栈及基本操作（包含入栈和出栈）
• • 顺序栈元素“入栈”
  • 顺序栈元素“出栈”
  • 总结代码
• 链栈及基本操作
• • 链栈元素入栈
  • 链栈元素出栈
  • 总结代码

栈的要求：

1. 栈只能从表的一端存取数据，另一端是封闭的
2. 在栈中，无论是存数据还是取数据，都必须遵循“先进后出”的原则，即最先进栈的元素最后出栈。

终上所述，可以给栈一个定义，即栈是一种只能从表的一端存取数据且遵循“先进后出”原则的线性存取结构

通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素，在图中所示就是4；同理，栈底元素就是指位于栈最底部的元素，在图中所示就是元素1

基于栈结构的特点，在实际应用中，通常只会对栈执行以下两种操作：

• 向栈中添加元素，此过程被称为“进栈”（入栈或压栈）
• 从栈中提取指定元素，此过程被称为“出栈”（或弹栈）

栈是一种“特殊”的线性存储结构，因此栈 的具体实现有以下两种方式：

• 顺序栈：采用顺序存储结构可以模拟存储数据的特点，从而实现栈存储结构
• 链栈：采用链式存储结构实现栈结构

两种实现方式的区别，仅限于数据元素在实际物理空间上存放的相对位置，顺序栈底层采用的是数组，链栈底层采用的是链表。

基于栈结构对数据存取采用“先进后出”原则的特点，它可以用于实现很多功能

例如，我们经常使用浏览器的回退功能，在写代码时检测代码中的括号匹配问题，实现数值进制转换功能等。。

顺序表和栈结构的存储数据的方式高度相似，只不过栈对数据的存取过程有特殊的限制，而顺序表没有

使用顺序表模拟栈结构很简单，只需要将数据从a数组下标为0的位置依次存储即可。
由于栈对存储元素出栈的次序有“先进后出”的要求，如果想将图1中存储的元素1从栈中取出，需先将元素4、3、2依次从栈中取出

使用顺序表模拟栈存储结构常用的实现思路，即在顺序表中设定一个实时指向栈顶元素的变量（一般命名为top），top初始值为-1，表示栈中没有存储任何数据元素，即栈是“空栈”。一旦有数据元素进栈，则top就做+1操作，反之，如果数据元素出栈top就做-1操作

由上可知，最初，栈是“空栈”，即数组是空的，top值为初始值-1。添加一个元素后，默认数组下标为0一端表示栈底，因此，第一元素被存储在数组a[1]处，同时top值+1

//元素elem进栈，a为数组，top值为当前栈的栈顶位置
int push(int* a,int top,int elem){
    a[++top]=elem;
    return top;
}

这里的a[++top] = elem; 会先执行++top，再执行a[top] = elem;

其实，top变量的设置对模拟数据的“入栈”操作没有实际帮助，它是为实现数据的“出栈”操作做准备的

只有靠近栈顶一侧的数据都出栈后，想要出栈的数据才能出

//数据元素出栈
int pop(int * a,int top){
    if (top==-1) {
        printf("空栈");
        return -1;
    }
    printf("弹栈元素：%dn",a[top]);
    top--;
    return top;
}

这里的if是为了防止用户做“栈中已无数据却还要数据出栈”的错误操作。

#include
#include

int push (int *a,int top,int elem){
	a[++top] = elem;
	return top;
}

int pop (int * a,int top){
	if(top == -1){
		printf("空栈n");
		return -1;
	}
	printf("出栈元素：%dn",a[top]);
	top --;
	return top;
}

int main(){
	int a[100];
	int top = -1;
	top = push(a,top,1);
	top = push(a,top,2);
	top = push(a,top,3);
	top = push(a,top,4);
	top = push(a,top,5);
	top = push(a,top,6);
	top = pop(a,top);
	top = pop(a,top);
	top = pop(a,top);
	top = pop(a,top);
	top = pop(a,top);
	return 0;
}

链栈，即用链表实现栈存储结构

将链表头部作为栈顶的一端，可以避免在实现数据“入栈”和“出栈”操作时做大量遍历链表的耗时操作
链表的头部作为栈顶，意味着：

• 在实现数据“入栈”操作时，需要将数据从链表的头部插入
• 在实现数据“出栈”操作时，需要删除链表头部的首元结点

因此链栈实际上就是一个只能采用头插法插入或删除数据的链表

采用头插法插入元素

lineStack * push(lineStack * stack,int a){
	lineStack * line = (lineStack*)malloc(sizeof(lineStack));
	line -> data = a;
	line -> next = stack;
	stack = line;
	return stack;
}

从头开始出栈

lineStack * pop(lineStack * stack){
	if(stack){
		lineStack * p = stack;
		stack = stack -> next;
		printf("出栈元素为：%dn",p->data);
		if(stack){
			printf("新栈顶元素为：%dn",stack -> data);
		}
		else{
			printf("栈内已无元素n");
			return stack;
		}
		return stack;
	}
	else
		printf("栈内已无元素n"); 
}

#include 
#include 

typedef struct lineStack{
	int data;
	struct lineStack * next;
}lineStack; 

lineStack * push(lineStack * stack,int a){
	lineStack * line = (lineStack*)malloc(sizeof(lineStack));
	line -> data = a;
	line -> next = stack;
	stack = line;
	return stack;
}

lineStack * pop(lineStack * stack){
	if(stack){
		lineStack * p = stack;
		stack = stack -> next;
		printf("出栈元素为：%dn",p->data);
		if(stack){
			printf("新栈顶元素为：%dn",stack -> data);
		}
		else{
			printf("栈内已无元素n");
			return stack;
		}
		return stack;
	}
	else
		printf("栈内已无元素n"); 
}

int main(){
	lineStack * stack = NULL;
	stack = push(stack,1);
	stack = push(stack,2);
	stack = push(stack,3);
	stack = push(stack,4);
	stack = push(stack,5);
	stack = pop(stack);
	stack = pop(stack);
	stack = pop(stack);
	stack = pop(stack);
	stack = pop(stack);
}