Stack 、Queue & String,栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in,栈和队列是两种常用的数据类型,Section 1 Stack,只允许在一端插入和删除的线性表 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) 特点 后进先出 (LIFO),栈 ( Stack ),退栈,进栈,a0,an-1,an-2,top,bottom,栈的抽象数据类型定义,ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。,基本操作：, ADT Stack,InitStack(&S),DestroyStack(&S),ClearStack(&S),StackEmpty(s),StackLength(S),GetTop(S, &x),Push(&S, x),Pop(&S, &x),InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。,StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈， 则返回 TRUE， 否则 FALE。,StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回 S 的元素 个数，即栈的 长度。,GetTop(S, &x) 初始条件：栈 S 已存在且非空。 操作结果：用 x 返回 S 的栈顶 元素。,a1,a2,an, ,ClearStack(&S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。,Push(&S, x) 初始条件：栈 S 已存在。 操作结果：插入元素 x 为新 的栈顶元素。,a1,a2,an,x, ,Pop(&S, &x) 初始条件：栈 S 已存在且非 空。 操作结果：删除 S 的栈顶元 素，并用 x 返回 其值。,a1,a2,an,an-1, ,A stack is a data structure in which all insertions and deletions of entries are made at one end, called the top of the stack. The last entry which is inserted is the first one that will be removed.,DEFINITION A stack of elements of type T is a finite sequence of elements of T , together with the following operations:,1. Create the stack, leaving it empty. 2. Test whether the stack is Empty. 3. Push a new entry onto the top of the stack, provided the stack is not full.,4. Pop the entry off the top of the stack, provided the stack is not empty. 5. Retrieve the Top entry from the stack, provided the stack is not empty.,Stack : Stack( ); Pre: None. Post: The Stack exists and is initialized to be empty.,Error_code Stack : pop( ); Pre: None. Post: If the Stack is not empty, the top of the Stack is removed. If the Stack is empty, an Error_code of underflow is returned and the Stack is left unchanged.,Error_code Stack : push(const Stack_entry Pre: None. Post: If the Stack is not full, item is added to the top of the Stack. If the Stack is full, an Error_code of overflow is returned and the Stack is left unchanged.,Error_code Stack : top(Stack_entry Pre: None. Post: The top of a nonempty Stack is copied to item. A code of fail is returned if the Stack is empty.,bool Stack : empty( ) const; Pre: None. Post: A result of true is returned if the Stack is empty, otherwise false is returned.,栈的数组表示 顺序栈,/- 栈的顺序存储表示 - #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;,类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。,Status InitStack (SqStack ,Status Push (SqStack ,Status Pop (SqStack ,template class Stack private: int top; Type *elements; int maxSize; public: Stack ( int s = 10 ); Stack ( ) delete elements; int Push ( Type x );,int Pop ( Type ,template Stack :Stack ( int s ) top= -1; maxSize = s; elements = new TypemaxSize; ,top,空栈,top,top,top,top,top,a 进栈,b 进栈,a,a,b,a,b,c,d,e,e 进栈,a,b,c,d,e,f 进栈溢出,a,b,d,e,e 退栈,c,top,c 退栈,b 退栈,a,b,a,a 退栈,空栈,top,a,b,d,d 退栈,c,top,a,b,c,top,top,template int Stack:Push( Type x ) if (IsFull( ) return 0; elements+top = x; return 1; ,template int stack:Pop( Type ,template int stack:GetTop( Type ,双栈共享一个栈空间,b0 t0 t1 b1,0 maxSize-1,V,template Error_code Stack : push(const Stack_entry ,template Error_code Stack : pop( ) Error_code outcome = success; if (count = 0) outcome = underflow; else -count; return outcome; ,template Error_code Stack : top(Stack_entry ,template bool Stack : empty( ) const bool outcome = true; if (count 0) outcome = false; return outcome; ,template Stack : Stack( ) count = 0; ,第一个例子：反转表 #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 numbers; / declares a stack of numbers cout n; for (int i = 0; i item; numbers.push(item); cout endl endl; while (!numbers.empty() cout numbers.top() “ “; numbers.pop(); cout endl; ,栈的链接表示 链式栈,链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头,top,链式栈 (Linked Stack) 类的定义,template class Stack; template class StackNode friend class Stack; private: Type data; StackNode *link; public: StackNode ( Type d,StackNode *l = NULL ) data=d;link=l; ;,template class Stack private: StackNode *top; public: Stack ( ) top=NULL Stack ( );,void Push ( Type x ); int Pop ( Type ,template Stack:Stack ( ) StackNode *p; while ( top != NULL ) p = top; top = top-link; delete p; ,templa