栈（顺序存储以及链式存储结构）的相关操作及应用

栈的相关操作及应用

栈的定义

栈（stack）：限定在表尾（栈顶）进行插入和删除操作的线性表
栈底是固定的。最先进栈的只能在栈底。

简单来说就是：后进先出

• 栈的插入操作（进栈）
• 栈的删除操作（出栈）
• 顺序栈与链栈
  

栈的顺序存储结构及相关操作

顺序栈的结构

typedef struct {
 int data[SIZE];
 int top;           // 用于栈顶指针 
}SqStack;

顺序栈的初始化与创建

void InitStack(SqStack *S) {                 // 初始化 
 int i;
 for(i = 0; i < SIZE; i++) {
  S->data[i] = 0;
 }
 S->top = -1;
}
void CreatStack(SqStack *S,int n) {        // 创建 
 int i;
 for(i = 0; i < n; i++) {
  scanf("%d",&S->data[i]);
  S->top++;
 }
}

入栈与出栈操作

void Push(SqStack *S,int e) {       // 入栈 
 if(S->top == SIZE - 1) {
  printf("栈已满\n");
  return; 
 }
 S->top++;
 S->data[S->top] = e;
}
void Pop(SqStack *S,int *e) {        // 出栈 
 if(S->top == -1) {
  printf("栈为空\n"); 
  return;
 } 
 *e = S->data[S->top];
 S->top--;
} 

栈的链式存储结构及相关操作

链栈的结构

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

typedef struct StackNode *LinkStackPtr;

typedef struct LinkStack {
	LinkStackPtr top;
	int count;
}LinkStack;

链栈的初始化

void InitStack(LinkStack *S) {
	S->top = (LinkStackPtr)malloc(sizeof(StackNode));
	S->top = NULL;
	S->top = 0;
}

入栈与出栈操作

• 入栈
  

void Push(LinkStack *S,int e) {
	LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
	s->data = e;
	s->next = S->top;    // 图中的1操作。当前栈顶元素赋给新节点后继
	S->top = s;            // 图中2操作  结点s赋给栈顶指针
	S->count++;
}

• 出栈
  

void Pop(LinkStack *S,int *e) {
	LinkStackPtr p;
	if(S->top == NULL) {
		printf("栈为空\n"); 
		return;
	}
	*e = S->top->data;
	p = S->top;   // 将栈顶结点赋给p
	S->top = S->top->next;   // 栈顶指针后移一位
	free(p);                 // 释放结点p
	S->count--;
}

栈的应用——四则运算表达式求值

逆波兰表达式

（一种不需要括号的后缀表达法）

举个例子 9+（3-1） * 3 + 10 / 2 -------> 9 3 1 - 3 * + 10 2 /+

后缀表达式的计算规则规则：    1.从左向右遍历表达式的每个数字和符号
                            2.遇到数字：进栈；遇到符号就将栈顶两个数字出栈，进行运算，运算结果进栈。

后缀表达式： 9 3 1 - 3 * + 10 2 /+
计算过程如下：
9、3、1进栈 || “ -号 ” 3-1=2 || 3进栈 || “ *号 ” 2 * 3 = 6 || “ +号 ” 9+6=15
10、2 进栈 || “ / 号 ” 10 / 2 = 5 || 15 + 5 = 20

中缀表达式 转 后缀表达式

中缀表达式也就是我们平常的四则运算的表达式
我们还是来看上面的例子：
9+（3-1） * 3 + 10 / 2 -------> 9 3 1 - 3 * + 10 2 /+

 规则        1.从左到右遍历每个数字和符号
                  2. 数字直接输出
                  3. 遇到符号，判断其与栈顶符号的优先级（右括号或者优先级不高于栈顶符号（乘除有限加减），将栈顶元素依次出栈并输出，并将当前符号进栈）

最后一个数字2 因此输出为
9 3 1 - 3 * + 10 2 /+

   注：1.  图中 2->3 遇到  ） 。栈中符号出栈，直到匹配到 （ 为止。
       2.       4->5   + 优先级 低于栈顶符号 *  栈中元素出栈 同时 + 进栈