【2012四川大学,数据结构与算法设计】第3讲 堆栈、队列和字符串

void Push ( Type x ); int Pop ( Type & x ); int GetTop ( Type & x ); void MakeEmpty();//实现与~Stack()同 int IsEmpty (){ return top == NULL; }
}
template <class Type> Stack<Type>::~Stack ( ) { StackNode<Type> *p; while ( top != NULL ) { p = top; top = top->link; delete p; } }
<操作数> <操作符> <操作数>，如 A+B；

前缀(prefix)表示
<操作符> <操作数> <操作数>，如 +AB；

后缀(postfix)表示
<操作数> <操作数> <操作符>，如 AB+；
表达式的中缀表示

表达式中相邻两个操作符的计算次序为： 优先级高的先计算； 优先级相同的自左向右计算； 当使用括号时从最内层括号开始计算。
template <class Type> int stack<Type>::Pop( Type & x ) { if (IsEmpty( )) return 0; x=elements[top--]; return 1; }
template <class Type> int stack<Type>::GetTop( Type & x ) { if (IsEmpty( )) return 0; x=elements[top]; return 1; }
DestroyStack(&S) StackLength(S) StackEmpty(s) GetTop(S, &x) ClearStack(&S) Push(&S, x) Pop(&S, &x)
InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。
第一个例子：反转表
#include "sq_stack.h " void main() /* Pre: The user supplies an integer n and n decimal numbers. Post:The numbers are printed in reverse order. Uses:The STL class stack and its methods*/ { int n; double item; stack<double> numbers; // declares a stack of numbers cout << " Type in an integer n followed n numbers." << endl << " The numbers will be printed in reverse order." << endl; cin >> n; for (int i = 0; i < n; i++) { cin >> item; numbers.push(item); } cout << endl << endl; while (!numbers.empty()) { cout << numbers.top() << " "; numbers.pop(); } cout << endl; }
template <class Type> class Stack { private: int top; Type *elements; int maxSize; public: Stack ( int s = 10 ); ~Stack ( ) { delete [ ]elements; } int Push ( Type x );
中缀表达式中各个算术操作符的优先级
操作符 ch = isp (栈内) 0 icp (栈外ቤተ መጻሕፍቲ ባይዱ 0

中缀算术表达式求值
( 1 8
^ *, /, % +, 7 5 3 6 4 2
) 8 1


isp叫做栈内(in stack priority)优先数 icp叫做栈外(in coming priority)优先数。 操作符优先数相等的情况只出现在括号配对或栈底 的‘=‟号与输入流最后的‘=‟号配对时。 上面讨论的+、-为双目运算符，如为单目运算符， 编程实现时，可在前面加上0而转化为双目运算符。 如在+、-的前一个字符(跳过空格,当前一个字符不是 运算符时用‘0‟表示)为‘=‟或‘(‟，则为单目运算 符。
Stack 、Queue & String
栈和队列是限定插入和删除只能在表 的“端点”进行的线性表。 线性表 栈 队列
Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1≤i≤n+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1≤i≤n
ADT Stack { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n } 约定an 端为栈顶，a1 端为栈底。 基本操作： } ADT Stack
InitStack(&S)
template <class Type> int Stack<Type>::GetTop ( Type & x ) { if ( IsEmpty ( ) ) return 0; x = top->data; return 1; }
表达式求值


一个表达式由操作数(亦称运算对象)、操 作符 (亦称运算符) 和分界符组成。 算术表达式有三种表示： 中缀(infix)表示
}
Status Push (SqStack &S, SElemType e) { if (S.top - S.base >= S.stacksize) {//栈满，追加存储空间 S.base = (ElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (ElemType)); if (!S.base) exit (OVERFLOW); //存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; return OK; }
栈的链接表示 — 链式栈
top



链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头
链式栈 (Linked Stack) 类的定义
template <class Type> class Stack; template <class Type> class StackNode { friend class Stack<Type>; private: Type data; StackNode<Type> *link; public:
top
b a
b 进栈
top
e d c b a e 退栈
d top c b a d 退栈
top
c b a c 退栈
top
b a
b 退栈
a top a 退栈 top
空栈
template <class Type> int Stack<Type>::Push( Type x ) { if (IsFull( )) return 0; elements[++top] = x; return 1; }
a1 a2 … … an-1 an
栈的数组表示 — 顺序栈
类似于线性表的顺序映象实现， 指向表尾的指针可以作为栈顶指针。 //----- 栈的顺序存储表示 ----#define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack;
int Pop ( Type &x ); int GetTop ( Type &x ); void MakeEmpty ( ) { top = -1; } int IsEmpty ( ) const { return top == -1; } int IsFull ( ) const { return top == maxSize-1; }
C++中操作符的优先级
优先级 操作符 1 单目+ 、 -、！ 2 *、/、% 3 +、4 <、<=、>、>= 5 ==、!= 6 && 7 ||

一般表达式的操作符有4种类型： 1 算术操作符 如双目操作符（+、-、*、 / 和%）以及单目操作符（ +、 -）。 2 关系操作符 包括<、<=、==、!=、>=、 >。这些操作符主要用于比较。 3 逻辑操作符 如与(&&)、或(||)、非(!)。 4 括号‘(‟和‘)‟ 它们的作用是改变运算 顺序。