栈

返回“数据结构”目录

逻辑结构

栈(Stack)是一种线性的逻辑结构，但是 - 它的插入运算和删除运算均在同一端进行。 - 进行插入和删除的那一端称为栈顶，另一端称为栈底。栈的插入操作和删除操作也分别简称进栈和出栈。 - 栈具有“先进后出”（FILO:Fisrt In Last Out）、“后进先出”的特性。 实例 一叠饭碗

图示 stack

操作

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

顺序实现（顺序栈）

栈的顺序存储方式实现又称作顺序栈

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

存储结构定义

用数组定义的顺序栈

#define MAXSIZE 100
typedef int elem_type;
struct seq_stack{
    elem_type elem[MAXSIZE]; //栈的存储空间
    int size; //栈中元素的个数
};
typedef struct seq_stack seq_stack;

算法实现

顺序栈初始化

void init ( seq_stack * st )
{
    st->size=0;
}

判断栈是否为空

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

获取顺序栈栈顶元素

elem_type get_top(seq_stack *st)
{
   return st->elem[st->size-1];
}

入栈

void push(seq_stack *st, elem_type x)
{
    if(st->size < MAXSIZE) {
        st->elem[st->size]=x;
        st->size++;
    }
}

出栈

elem_type pop(seq_stack *st)
{
    return st->elem[--st->size];
}

打印栈

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

判断顺序栈是否已满

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

链式实现

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

这里采用带头结点的单链表实现。

存储结构结构定义

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

typedef int elem_type;
struct node {
   elem_type data;
   struct node *next;
};
typedef struct node node;
typedef struct node *link_list

算法实现

初始化 同带头结点的单链表

取栈顶元素

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

入栈

void push(node *head, ElemType x){
   Node*p=(Node*)malloc(sizeof(Node));
   p->data=x;
   p->next=head->next;
   head->next = p;
}

出栈

ElemType pop(node *head) {
   Node *p = head->next;
   ElemType x = p->data;
   head->next = p->next;
   free(p);
   return x;
}

应用

括号匹配

问题描述

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

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

算法思路

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

算法实现

int match_kuohao (char *s) {
    int i;
    seq_stack st;
    init_stack(&st);
    for(i = 0; s[i]!='\0'; i++) {
        switch (s[i]) {
        case '{': case '[': case '(':
            push(&st, s[i]); break;
        case '}':
            if(!is_empty(&st)&&get_top(&st)=='{')
                { pop(&st);break; } else return 0;
        case ']':
            if(!is_empty(&st)&&get_top(&st)=='[')
                { pop(&st);break; } else return 0;
        case ')':
            if(!is_empty(&st)&&get_top(&st)=='(')
                { pop(&st);break; } else return 0;
        }
    }
    return  is_empty(&st);
}

算术表达式求值

对简单的中缀表达式进行求值

从左到右扫描表达式，进行如下处理： 1. 遇到运算数进operand栈 1. 遇到运算符，与operator栈顶运算符比较优先级 - 如果比栈顶运算优先级高，则入栈。 - 否则operator出栈，operand出栈，进行运算，结果入栈。重做2

递归算法改非递归算法