顺序栈与链栈

简介

栈和队列是两种重要的线性结构。从数据结构的角度来看，栈和队列也是线性表。它们的特殊性在于堆栈和队列的基本操作是线性表操作的子集。它们是操作有限的线性表。

堆栈是一个线性列表，它将插入或删除操作仅限于列表的末尾。因此，对于栈来说，表尾有特殊的意义，称为栈顶，相应的，表头也称为栈底。没有元素的空列表称为空堆栈。

顺序栈

顺序栈是指采用顺序存储结构实现的栈，即用一组地址连续的存储单元从栈底到栈顶依次存储数据元素，并有一个指针top附加指示堆栈顶部元素在顺序堆栈中的位置。

基本实现是：

• 序列栈

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100

typedef struct{
    
	int *base;      //栈顶指针
	int *top;      //栈底指针
	int StackSize;
}SqStack;

//初始化
SqStack InitStack(){
    
	SqStack S;
	int a [MAXSIZE];
	S.base =  a;
	S.top = S.base;
	S.StackSize = MAXSIZE;
	return S;
}

//入栈
int Push(SqStack *S, int e){
    
	if(S->top-S->base ==S->StackSize) return 0;   //栈满
	S->top = e;
	(*S).top++;             //S->top ++
	return 1;
}

//出栈
int Pop(SqStack *S){
    
	if(S->base == S->top) return 0;    //栈空
	(*S).top--;              //S->top--
	int e;
	e= S->top;
	return e;
}

int main(){
    
	SqStack  S = InitStack();
	Push(&S,1);
	int e = Pop(&S);
	printf("%d\n",e);
	Push(&S,2);
	int e1 = Pop(&S);
	printf("%d\n",e1);
	Push(&S,3);
	int e3 = Pop(&S);
	printf("%d\n",e3);
	return 0;

}

代码上容易出错的地方是(*S).top++，在使用指针操作时，很多时候可能会写成S->top++。注意后者是指针取值，前者是指针运算，在每次入栈和出栈会进行指针运算，所以是前者。

链栈

链式堆栈是指采用链式存储结构实现的堆栈。链接栈是一个受限制的链表，只能从链表的头部开始操作。

链表中有前向插值法和后向插值法。前者以头节点为基础，在头节点之后插入新节点，每次插入都插入到链表的头部；后者使用尾指针作为光标，每次存储新的节点地址信息后，与新的等级点地址交换以存储下一个新的节点信息。

#include<stdio.h>
#include<stdlib.h>

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

LinkStack* InitStack(){
    
	LinkStack* L = (LinkStack*)malloc(sizeof(LinkStack));
	L->next = NULL;
	return L;
}

//入栈-----栈的特点显示链栈只能使用前插法
int Push(LinkStack *L,int e){
    
	StackNode* node = (StackNode*)malloc(sizeof(StackNode));
	node->data = e;
	node->next = L->next;
	L->next = node;
	return 1;
}

//出栈 (后进先出)
int Pop(LinkStack* L){
    
	if(L->next ==NULL) return 0;
	int e;
	e= L->next->data;
	L->next=L->next->next;
	return e;
}


int main(){
    
	LinkStack* L = InitStack();
	Push(L,2);
	Push(L,3);
	int e = Pop(L);
	printf("%d",e);
	int e1 = Pop(L);
	printf("%d",e1);
	return 0;
}

栈与递归

堆栈的一个重要应用是在编程语言中实现递归。由于栈的后进先出特性，在处理某些具有连续特性的数据结构时，上一步的计算结构会影响下一步，因此可以采用程序的递归算法。

程序调用自身的编程技术称为递归。

构成递归所需的条件：

1. 子问题必须与原问题相同，但更简单；

2. 它不能无限制地调用自身，必须有出口，并且可以简化为非递归情况处理。

例如${\Sigma }_{r=1}^n$的求和中，循环是常用的求值方法，但是也是可以使用递归运算的。

int Fn(int x){
    
	if(x==1) return 1;
	else return Fn(x-1)+x;
}

#include<stdio.h>

int Fn(int x){
    
	if(x==1) return 1;
	else return Fn(x-1)+x;
}


int main(){
    
	int e = Fn(5);
	printf("%d",e);
}