【栈】栈的定义及基本操作

1. 栈的定义和特点

定义：栈是限定尽在表尾进行插入或删除操作的线性表。

表头元素成为栈底，表尾元素成为栈顶。 

特点：后进先出（先进后出）

2. 顺序栈       

顺序栈是利用顺序存储结构实现的栈，即用一组连续的存储单元来依次存储自栈底到栈顶的数据元素。

top 指针指向栈顶元素的指针，base 指针指向栈底元素的指针；

Q.栈不是仅限于栈顶（表尾）进行插入和删除的线性表吗？为何还需要栈底指针？

习惯用 top == 0 表示空栈，鉴于 C/C++语言中数组的下标约定从 0 开始，因此用 C++语言描述是会带来困惑，因此另设指针base 指向栈底元素在顺序表中的位置。

注意点

（1）栈底指针 base，初始化完成之后，始终指向栈底的位置。

         若base == NULL ，则表明栈结构不存在。

（2）栈顶指针 top，其初值为指向栈底。

        栈为空时 top == base，非空时 top 始终指向栈顶元素的上一个位置。

2.1 顺序栈的存储结构

#define MAXSIZE 100
typedef struct{
	SElemType *base;  //利用base 指针指向基地值，即为栈底
	SElemType *top;
	int stackszie; 
}SqStack;

2.2 顺序栈的基本操作

1. 顺序栈的初始化

void InitStack(SqStack &S){
	S.base = new SElemType[MAXSIZE];
	if(!S.base) exit(OVERFLOW);
	S.top = S.base;  //栈顶指针指向base，表示栈空
	S.stacksize = MAXSIZE; 
}

2. 顺序栈的插入

void Push(SqStack &S,SElemType e){
	if(S.top - S.base == S.stacksize){
		cout << "栈已满，无法进行插入操作！" << endl; 
		return;
	}
	*S.top++ = e;
	cout << "成功插入元素！" << endl; 
}

3. 顺序栈的删除

void Pop(SqStack &S,SElemType &e){
	if(S.top == S.base) {
		cout << "栈空，无法进行删除操作！" << endl;
		return;
	}
	e = *--S.top;  //由于栈顶指针始终指向栈顶元素的上一个位置 
	cout << "成功删除元素！" << endl; 
}

4. 顺序栈的取值

SElemType GetTop(SqStack S){
	if(S.base != S.top)
	return *(S.top - 1); 
} 

3. 链栈                                                                                          

链栈是指采用链式存储结构实现的栈。

由于栈的主要操作是在栈顶插入和删除，因此以链表的头部作为栈顶，并且没有必要附加一个头结点。

3.1 链栈的存储结构

typedef struct StackNode{
	SElemType data;
	struct StackNode * next;
}StackNode,*LinkStack;

3.2 链栈的基本操作

1. 链栈的初始化

void InitLinkStack(LinkStack &S){
	S = NULL;    //直接让头指针指向首元结点即可 
	cout << "成功创建链栈！" << endl;
} 

2. 链栈的插入

void Push(LinkStack &S,SElemType e){
	StackNode *p = new StackNode;
	p -> data = e;
	p -> next = S;
	S = p;
	cout << "插入成功！" << endl;
} 

3. 链栈的删除

void Pop(LinkStack &S,SElemType &e){
	if(S == NULL) {
		cout << "栈空，无法进行删除操作" << endl;
		return; 
	}
	StackNode *p = new StackNode;
	p = S;
	S = S -> next;
	e = p -> data;
	delete p; 
}

4. 链栈的取值

SElemType GetTop(LinkStack &S){
	if(S != NULL){
		return S -> data;
	}
}