栈Stack

1. 定义

栈是一种特殊的线性表。对于这种线性表规定它的插入运算和删除运算均在线性表的同一端进行。进行插入和删除的那一端称为栈顶，另一端称为栈底。栈的插入操作和删除操作也分别简称进栈和出栈。
栈具有“先进后出”（FILO:Fisrt In Last Out）、“后进先出”的特性。

2. 实例

一叠饭碗

3. 图示

attachment:stack.jpg

4. 操作

init_stack(st) 初始化
is_empty(st)判断栈是否为空
get_top(st) 取得栈顶结点值
push(st, x) 栈的插入操作
pop(st) 栈的删除操作

5. 顺序实现

栈的顺序存储方式实现又称作顺序栈栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制它们在顺序表的同一端进行，所以同顺序表一样也可用一维数组表示。

5.1. 数据结构定义

   1 #define MAXSIZE 100
   2 typedef int ElemType;
   3 typedef struct{
   4     ElemType elem[MAXSIZE];
   5     int size;
   6 }seq_stack;

5.2. 顺序栈初始化

   1 void init_stack ( seq_stack * st )
   2 {
   3     st->size=0;
   4 }

5.3. 判断栈是否为空

   1 int is_empty(seq_stack *st)
   2 {
   3     return st->size==0;
   4 }

5.4. 获取顺序栈栈顶元素

   1 ElemType get_top(seq_stack *st)
   2 {
   3    return st->elem[st->size-1];
   4 }

5.5. 入栈

   1 void push(seq_stack *st, ElemType x)
   2 {
   3     if(st->size < MAXSIZE) {
   4         st->elem[st->size]=x;
   5         st->size++;
   6     }
   7 }

5.6. 出栈

   1 ElemType pop(seq_stack *st)
   2 {
   3     return st->elem[--st->size];
   4 }

5.7. 打印栈

   1 void print_stack (seq_stack *st)
   2 {
   3    int i;
   4    for(i = 0; i < st->size; i++) 
   5        printf("%5d", st->elem[i]);
   6 }

5.8. 判断顺序栈是否已满

   1 int is_full(seq_stack *st) {
   2    return st->size == MAXSIZE;
   3 }

6. 链式实现

栈的链式存储称为链式栈。链式栈就是一个特殊的单链表，对于这特殊的单链表，它的插入和删除只在单链表的头部进行。这里采用带头结点的单链表实现。

6.1. 数据结构定义

数据结构定义同带头结点的单链表。

6.2. 初始化

同带头结点的单链表

6.3. 取栈顶元素

   1 ElemType get_top(node *head) {
   2    return head->next->data;
   3 }

6.4. 入栈

   1 void push(node *head, ElemType x){
   2    Node*p=(Node*)malloc(sizeof(Node));
   3    p->data=x;
   4    p->next=head->next;
   5    head->next = p;
   6 }

6.5. 出栈

   1 ElemType pop(node *head) {
   2    Node *p = head->next;
   3    ElemType x = p->data;
   4    head->next = p->next;
   5    free(p);
   6    return x;
   7 }

7. 应用

7.1. 括号匹配

7.1.1. 问题描述

设一个表达式中可以包含三种括号：小括号、中括号和大括号，各种括号之间允许任意嵌套，如小括号内可以嵌套中括号、大括号，但是不能交叉。举例如下：

  ([]{})  正确的
  ([()])  正确的
  {([])}  正确的
  {[(])}  不正确的
  {(}[])  不正确的

7.1.2. 算法思路

自左向右扫描一个表达式，当遇到的左括号，都期待后面有一个和它对应的右括号与之匹配。我们将所遇到的开括号存放入一个栈中，等待匹配。
当遇到一个右括号时，就查看这个栈的栈顶结点，如果它们匹配，则删除栈顶结点，如果不匹配，则说明表达式中括号是不匹配的。
如果扫描它整个表达式后，这个栈是空的，则说明表达式中的括号是匹配的，否则表达式的括号是不匹配的。

7.1.3. 算法实现

   1 int match_kuohao (char *s) {
   2     int i;
   3     seq_stack st;
   4     init_stack(&st);
   5     for(i = 0; s[i]!='\0'; i++) {
   6         switch (s[i]) {
   7         case '{': case '[': case '(':
   8             push(&st, s[i]); break;
   9         case '}':
  10             if(!is_empty(&st)&&get_top(&st)=='{')
  11                 { pop(&st);break; } else return 0;
  12         case ']':
  13             if(!is_empty(&st)&&get_top(&st)=='[')
  14                 { pop(&st);break; } else return 0;
  15         case ')':
  16             if(!is_empty(&st)&&get_top(&st)=='(')
  17                 { pop(&st);break; } else return 0;
  18         }
  19     }
  20     return  is_empty(&st);
  21 }

}

栈

栈Stack

1. 定义

2. 实例

3. 图示

4. 操作

5. 顺序实现

5.1. 数据结构定义

5.2. 顺序栈初始化

5.3. 判断栈是否为空

5.4. 获取顺序栈栈顶元素

5.5. 入栈

5.6. 出栈

5.7. 打印栈

5.8. 判断顺序栈是否已满

6. 链式实现

6.1. 数据结构定义

6.2. 初始化

6.3. 取栈顶元素

6.4. 入栈

6.5. 出栈

7. 应用

7.1. 括号匹配

7.1.1. 问题描述

7.1.2. 算法思路

7.1.3. 算法实现

7.2. 算术表达式求值

7.3. 递归算法改非递归算法

队列Queue