@songpfei 2016-05-28T07:30:27.000000Z 字数 2324 阅读 686

# 栈

数据结构

## 2. 栈的抽象数据类型

ADT 栈（stack)DATA通线性表，元素具有相同的类型，相邻元素具有前驱和后继关系Operation    InitStack(*s):初始化操作，建立一个空栈；    DestroyStack(*s):若栈存在，则销毁它；    ClearStack(*s):将栈清空；    StackEmpty(*S):若栈为空，则返回true,否则返回false;    GetTop(*s,*e):若栈存在且非空，则用e返回s栈顶元素；    Push(*s,e):若栈s存在，插入新元素e到栈s中并成为栈顶元素    Pop(*s,*e):删除栈s中栈元素，并用e返回其值；    StackLength(*s):返回栈s的元素个数end  ADT

### 2.1 栈的顺序存储结构及其实现

#ifndef STACK_H#define STACK_Htypedef int ElemType;#define MAX_SIZE 20typedef struct {    ElemType data[MAX_SIZE];    int top;/*用于栈顶指针*/}SqStack;void InitStack(SqStack*s);bool Push(SqStack*s,ElemType e);bool Pop(SqStack*s,ElemType &e);#endif
#include "stack.h"/*数组存储栈系列操作*//* 栈初始化*/void InitStack(SqStack* s){    s->top = -1;}/*入栈*/bool Push(SqStack*s,ElemType e){    if (s->top == MAX_SIZE - 1)/*栈满*/        return false;    s->top++;    s->data[s->top] = e;    return true;}/*出栈*/bool Pop(SqStack*s,ElemType &e){    if (s->top < 0)/*栈为空*/        return false;    e = s->data[s->top];    s->top--;    return true;}

### 2.2 栈的链式存储结构及实现

#ifndef STACK_H#define STACK_Htypedef int ElemType;typedef struct StackNode{    ElemType data;    struct StackNode* next;}StackNode,*LinkStackPtr;typedef struct {    int count;/*元素个数计数*/    LinkStackPtr top;/*用于栈顶指针*/}LinkStack;void InitStack(LinkStack *s);bool Push(LinkStack*s, ElemType e);bool Pop(LinkStack*s, ElemType &e);#endif
#include "stack.h"#include<cstdlib>/*数组存储栈系列操作*//* 栈初始化*/void InitStack(LinkStack *s){    s->top = NULL;    s->count = 0;}/*入栈*/bool Push(LinkStack*s, ElemType e){    LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode));    if (!temp)/*内存申请失败*/        return false;    temp->data = e;    temp->next = s->top;    s->top = temp;    s->count++;    return true;}/*出栈*/bool Pop(LinkStack*s, ElemType &e){    if (s->count < 0)/*栈为空*/        return false;    e = s->top->data;    LinkStackPtr p = s->top;/*取出栈顶*/    s->top = p->next;//更新栈顶指针    free(p);    p = NULL;    s->count--;    return true;}
#include<cstdio>#include<cstdlib>#include"stack.h"int main(){    LinkStack s;    InitStack(&s);    int e;    for (int i = 0; i < 10; i++)        Push(&s, i);    Pop(&s, e);    printf("%d", e);}

## 3. 栈的应用---四则运算表达式

### 3.1 后缀（逆波兰）表达式求值

eg:中缀表达式：9+(3-1)*3+10/2

### 3.2 中缀表达式转后缀表达式

http://www.cnblogs.com/cj723/archive/2011/02/06/1949498.html

• 私有
• 公开
• 删除