女性内衣内裤选择技巧

栈与队列西安交通大学计教中心栈的定义

栈是限制在表的一端进行插入和删除操作的线性表。允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。 如果多个元素依次进栈，则后进栈的元素必然先出栈，所以堆栈又称为后进先出（LIFO）表。堆栈设有一个栈顶指针标志栈顶位置。

栈示意图a1a3a2进栈出栈top堆栈的主要操作有：•创建空栈。•进栈(push)操作:在栈顶插入元素。•出栈(pop)操作:在栈顶删除元素。•读栈顶元素:只是读出栈顶元素，并不改变栈内元素。

顺序栈#defineSTACKSIZE100 //堆栈最大可分配空间数量classSqStack{public: ElemTypedata[STACKSIZE]; //存储元素的数组 inttop; //栈顶指针，存储栈顶元素的下标 SqStack(){top=-1;} //构造函数 voidPush(ElemTypex); //入栈操作 voidPop(ElemType&result); //出栈操作voidGetTop(ElemType&result); //取栈顶元素};

一般将数组的0下标单元作为栈底，将栈顶元素的下标存储在栈顶指针top中，它随着元素进栈出栈而变化。top为-1表示空栈，top等于stacksize-1则表示栈满。（1）进栈操作若栈不满，则在栈顶插入元素x作为新的栈顶。voidSqStack::Push(ElemTypex){ if(top<stacksize-1) { top++; data[top]=x; } elsecout<<”栈满”;}（2）出栈操作若栈不空，则删除栈顶元素，用result返回其值。voidSqStack::Pop(ElemType&result){ if(top>-1){ result=data[top]; top--; }elsecout<<"栈空";}（3）取栈顶元素若栈不空，则用result返回栈顶元素。voidSqStack::GetTop(ElemType&result){ if(top>-1){ result=data[top]; } elsecout<<"栈空";}链式栈

栈的链式存储结构实质上就是一个无头结点、只能在头部插入、删除元素的单链表。typedefstructnode{ ElemTypedata; //数据域 structnode*next; //指针域}SNode; classLinkStack{ public: SNode*top; //栈顶指针 LinkStack(){top=NULL;} //构造函数 voidPush(ElemTypex); //入栈操作 voidPop(ElemType&result); //出栈操作};

（1）进栈操作若栈不满，则在栈顶插入元素x作为新的栈顶。voidLinkStack::Push(ElemTypex){ SNode*p=newSNode; if(p!=NULL){ p->data=x; p->next=top; top=p; }}（2）出栈操作若栈不空，则删除栈顶元素，用result返回其值。voidLinkStack::Pop(ElemType&result);{ SNode*p; if(top!=NULL){ result=top->data; p=top; top=top->next; deletep; }}举例:后后缀表达达式求值假定表达式式是由加减减乘除和数数字构成。。最简单的的表达式为为下列形式式：(操作数S1)(运算符符OP)(操作数数S2)三种不同的的表示方法法：前缀表示法法OPS1S2例如6+3写写成+63中缀表示法OPS1S2例如6+3写写成63+后缀表示法S1S2OP例如6+3写写成63+同时，任何表表达式都可分分解为下列形形式：(子表达式E1)(运算符OP)(子表达式式E2)它的后缀表示示法应写成：：(E1的后缀表示)(E2的后缀表示)OP只要不断对子子表达式进一一步分解，总总能将子表达达式分解为最最简单形式，，因此任何四四则运算表达达式都可写成成前缀式或后后缀式。例如：2*(6+3)2(6+3)*263+*。(注意：转化化为后缀式后后括号去掉)中缀式虽然容容易理解，但但在求值的时时候利用前缀缀式或后缀式式更为简单。。用后缀式求求值的算法为为：首先设立一个个堆栈，依此此读取后缀式式中的字符，，若字符是数数字，则进栈栈并继续读取取，若字符是是运算符（记记为OP），则连续出出栈两次得到到数字S1和S2，计算表达式式S1OPS2并将结果入栈栈，继续读取取后缀式。当当读到结束符符时停止读操操作，这时堆堆栈中只应该该有一个数据据，即结果数数据。例如后缀式263+*的的计算过程为为2、6、3依次入栈，，读+号则令令3和6依次次出栈，计算算6+3后将将结果9入栈栈，读*号则则令9和2依依次出栈，计计算2*9后后将结果18入栈。这时时18就是最最终结果。【例2-3】假定表达式是是由不超过四个实数进行行四则运算构成的算算式，要编写一个程序来求解该该算式的结果果。中缀表达式变变成等价的后后缀表达式将中缀表达式式变成等价的的后缀表达式式，表达式中中操作数次序序不变，运算算符次序发生生变化，同时时去掉了圆括括号。转换规规则是：设立一个栈，，存放运算符符，首先栈为为空，编译程程序从左到右右扫描中缀表表达式，若遇遇到操作数，，直接输出，，并输出一个个空格作为两两个操作数的的分隔符；若若遇到运算符符，则必须与与栈顶比较，，运算符级别别比栈顶级别别高则进栈，，否则退出栈栈顶元素并输输出，然后输输出一个空格格作分隔符；；若遇到左括括号，进栈；；若遇到右括括号，则一直直退栈输出，，直到退到左左括号止。当当栈变成空时时，输出的结结果即为后缀缀表达式。步骤栈中元素

输出结果

说明1(

（进栈2(1输出13(+1+进栈4(+12输出25

12++退栈输出，退栈到（止6*12+*进栈7*(12+（进栈8*((12+（进栈9*((12+8输出810*((-12+8

-进栈将中缀表达式式(1+2)*((8-2)/(7-4))变变成等价的后后缀表达式。。

现在用栈栈来实现该运运算，栈的变变化及输出结结果如下：11*((-12+82输出212*(12+82--退栈输出，退栈到（止13*(/12+82-/进栈14*(/(12+82-（进栈15*(/(12+82-7输出716*(/(-12+82-7-进栈17*(/(-12+82-74输出418*(/12+82-74--退栈输出，退栈到（止19*12+82-74-//退栈输出，退栈到（止20

12+82-74-/*

*退栈并输出队列定义队列是只能在在表的一端进进行插入、在在另一端进行行删除操作的的线性表。允允许删除元素素的一端称为为队头，允许许插入元素的的一端称为队队尾。显然不论元素素按何种顺序序进入队列，，也必然按这这种顺序出队队列，所以队队列又称为先先进先出（FIFO）表表。队列有两两个活动端，，所以设置了了对头和队尾尾两个位置指指针。一般队队头指针记作作front，队尾指针针记作rear。abcfrontrear入队出队队列示意图循环队列—队队列顺序存储储顺序存储的队队列中，每次次出队列的元元素必定是队队头元素，因因此如果采取取与普通顺序序表同样的操操作方式，则则每次出队操操作必然将整整个队列向前前移动，这使使得效率大大大降低。因此在顺序存储的的队列中，出出队和入队操操作都不移动动元素而是移移动指针。为方便起见，，这里规定队队头指针front指向队头元素素的前一个位位置，队尾指指针rear指向队尾元素素所在位置。。这样，入队队和出队操作作的执行步骤骤都是首先执执行指针移动，再再进行元素读读写。对空队列而言言，可假定front和和rear的的值为-1假溢出ABCfrontrearfrontrear(a)

A‚B‚C入队

(b)

A‚B出队,D‚E入队

(c)队列假溢出队列假溢出示意图CDEfrontrear随着元素不断断入队列、出出队列，rear和front指针针会不断向后后移动（如图图(b)所示示），最终会会指向数组的的最大下标位位置（如图(c)所示））。由于rear和front指针针只能单方向向移动，这时时元素无法入入队列，但是是队列中仍有有大量空闲位位置。这种情情况称为假溢溢出。循环队列解决队列假溢溢出的办法是是将存放队列列元素的数组组首尾相接，，形成循环队队列。循环队列的基基本操作方式式为：入队列时先执执行rear=(rear+1)%M，再将新新元素在rear指示位位置加入；出队列时先执执行front=(front+1)%M，再再将下标为front的的元素取出。。为了将队空和和对满的条件件加以区分，，一般不使用用front指针所指的的位置。队空条件为front=rear队满条件为(rear+1)%M=front30124567frontrearABCD30124567frontrear30124567frontrearABCDFGE(a)循环队队列空(b)非空循循环队列(c)循环环队列满循环队列示意意图循环队列描述述如下：#defineMAXSIZE100//队列最大大可分配空间间数量classSqQueue{public:ElemTypedata[MAXSIZE]; //存放元素素的数组intfront;//队队头头指指针针intrear;//队队尾尾指指针针voidEnQueue(ElemTypex);//入入队队操操作作voidDeQueue(ElemType&e);//出出队队操操作作voidGetHead(ElemType&e);//取取队队头头元元素素};front和和rear指指针针取取值值均均为为所所指指数数组组单单元元的的下下标标。。由于于队队头头指指针针所所指指单单元元总总是是空空的的，，length比比实实际际能能存存储储的的元元素素多多一一。。（1））入入队队操操作作若队队列列不不满满，，则则在在队队尾尾插插入入元元素素x作为为新新的的队队尾尾。。voidSqQueue::EnQueue(ElemTypex){if((rear+1)%MAXSIZE==front)cout<<"队队列列已已满满";else{rear=(rear+1)%MAXSIZE;data[rear]=x;}}常用算算法（2））出队队操作作若队列列不空空，则则删除除队头头元素素并用用e取回该该元素素的值值。voidSqQueue::DeQueue(ElemType&e){if(rear==front)cout<<"队队列已已空";else{front=(front+1)%MAXSIZE;e=data[front];}}（3））取队队头元元素若队列不空空，则用e取回队头元元素的值。。voidSqQueue::GetHead(ElemType&e){if(rear==front)cout<<"队队列已空";else{inti=(front+1)%MAXSIZE;e=data[i];}}链队列—队队列链式存存储链队列实质质上就是只只能在头部部删除元素素、只能在在尾部插入入元素的单单链表。队头指针front就是单链链表的头指指针，队尾尾指针rear则是是指向单链链表最后一一个结点的的指针。Qa1an∧frontrear非空链队列

链队列的结结点可定义义如下：structQNode{ElemTypedata;structQNode*next;};链队列有两两个指针，，因此可采采用下面定定义:classLinkQueue{public:QNode*front;//队队头指针针QNode*rear;//队队尾指针针(下页页继续………)(接接上页)LinkQueue(){front=newQNode;//建建立头结结点front->next=NULL;rear=front;//尾指指针也指指向头结结点}intLength();//求队队列长度度voidEnQueue(ElemTypex);//入队操操作voidDeQueue(ElemType&e);//出队队操作voidGetHead(ElemType&e);//求队队头元素素};（1）求求队列的的长度返回队列列的元素素个数，，即队列列的长度度。intLinkQueue::Length(){QNode*p=front;intlen=0;while(p!=rear){len++;p=p->next;}returnlen;}（2）入队列列操作插入元素x为为队列新的队队尾元素。voidLinkQueue::EnQueue(ElemTypex){QNode*s=newQNode;//建立新结结点ss->data=x;s->next=NULL;rear->next=s;//在队队尾插插入结结点srear=s;//修修改队队尾指指针}（3））出队队列操操作若队列列不空空，则则删除除队头头元素素，用用e返返回其其值。。voidLinkQueue::DeQueue(ElemType&e){QNode*p;if(front==rear)cout<<"队列列已空空";else{