第三章栈和队列

1、目录1SandQ1、栈2、栈的应用举例3、队列栈和队列1物料管理1、栈1、定义：特点：先入后出FILO限定仅只能在表尾端进行和删除的线性表。栈顶：表尾端被称之为栈顶。栈底：和表尾相对应的另一端，称之为栈底。2、栈的表示： 顺序表示的堆栈：typedef struct 初态B出栈C进栈SElemType * SElemType * int sqstack;base ;top ;stacksize ;/ 栈底元素的位置/栈顶元素的位置/栈的空间大小或栈最多存放结点个数基本操作：iniStack ( sqstack &s ) ;push( sqstack &s, SElemType e ) ; /

2、将 e 的数据值栈顶，/ 必须判是否上溢。/ 取栈顶元素的数据值至变量 e，/ 执行该操作之前，必须判2 栈空。SandQpop( sqstack &s, SElemType & e ) ;CBAABA2物料管理1、栈2、栈的表示： 顺序表示的堆栈的实现：toptop32toptop1top base0basebasebasebase空栈base = top 是栈空标志stacksize = 43SandQ注意：因为 base = top 是栈空标志，所以top 指针只能指示真正的栈顶元上的数组元素的下标地址。否则造成。栈满时的处理方法：1、报错。返回操作系统。2、分配更大的空间，作为栈的空间

3、。将原栈的内容移入新栈。DCBACBABAA3物料管理1、栈2、栈的表示： 顺序表示的栈的程序实现：STACK_INIT_SIZE-10124数组 s.base0, s.base1, s.baseSTACK_INIT_SIZE-1s.baseSandQIniStack(sqstack &s) s.base = ( SElemType * ) malloc(STACK_INIT_SIZE * sizeof(SElemType) ); if ( !s.base) exit ( OVERFLOW ) ;s.top = s.base ; / null stack flag s.stacksize =

4、STACK_INIT_SIZE; return OK; / initstack;# define STACK_INIT_SIZE100# define STACK_INCREMENT 104物料管理1、栈2、栈的表示： 顺序表示的栈的程序实现 push 操作：realloc(ptr, size): 操作系统先分配大小为size 个字节的内存空间，然后将由ptr 指针指向的过来，随后将 ptr 指针指向的存区存区的内容，该函数最后返回新存区的地址。01297 98 9901298 99107108 109ppptrSandQ5Status push (sqstack &s,SElemType e

5、) if (s.top - s.base = s.stacksize)s.base=(SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT) *sizeof(SElemType);if ( !s.base) exit ( OVERFLOW ) ; s.top = s.base + s.stacksize ; / s.stacksize += STACKINCREMENT; *s.top + = e;/ 相当于： * s.top = e; s.top + 两条指令;return OK; / push;5物料管理1、栈2、栈的表示： 顺序表示

6、的栈的程序实现 pop 操作：表示的栈：参照下图所示的情况： 其中 s 是栈顶指针。栈顶和栈底。datanext栈顶S栈底6SandQStatus pop (sqstack &s,SElemType & e) if (s.top = s.base ) return ERROR;e = * - - s.top ;/ 相当于： s.top- -; e = * s.top 两条指令;return OK ; / pop6物料管理1、栈表示的栈的操作：s 是栈顶指针。栈顶和栈底。datanext栈顶S栈底S7SandQInilinkStack(Stackptr &s) s = NULL / initli

7、nkstack;typedef struct Snode SElemTypedat a; structSnode* next; Snode, * StackPtr;Stackptr s;/ as top pointer7物料管理1、栈表示的栈的操作：s 是栈顶指针。栈顶和栈底。datanext栈顶S栈底datanextdatanextSp8SandQStatus push (Stackptr &s,SElemType e) p = ( Stackptr ) malloc (sizeof(Snode) );if ( !p) exit( OVERFLOW ) ; p - data =e; p- n

8、ext = s; s = p;return OK; / push;8物料管理1、栈表示的栈的操作：s 是栈顶指针。栈顶和栈底。datanext栈顶S栈底datanextdatanextSp9SandQeStatus push (Stackptr &s,SElemType e) p = ( Stackptr ) malloc (sizeof(Snode) );if ( !p) exit( OVERFLOW ) ; p - data =e; p- next = s; s = p;return OK; / push;9物料管理1、栈表示的栈的操作：s 是栈顶指针。栈顶和栈底。datanext栈顶S栈

9、底datanextdatanextSp10SandQeStatus push (Stackptr &s,SElemType e) p = ( Stackptr ) malloc (sizeof(Snode) );if ( !p) exit( OVERFLOW ) ; p - data =e; p- next = s; s = p;return OK; / push;10物料管理1、栈表示的栈的操作：s 是栈顶指针。栈顶和栈底。datanext栈顶S栈底datanextdatanextSp11SandQeStatus push (Stackptr &s,SElemType e) p = ( St

10、ackptr ) malloc (sizeof(Snode) );if ( !p) exit( OVERFLOW ) ; p - data =e; p- next = s; s = p;return OK; / push;11物料管理1、栈表示的栈的操作：s 是栈顶指针。栈顶和栈底。datanext栈顶S栈底datanexte = AS12SandQAStatus pop (Stackptr &s, SElemType & e) if ( ! s) exit( UNDERFLOW ) ;e = s- data; p = s; s = s- next; free(p);return OK; /

11、push;12物料管理1、栈表示的栈的操作：s 是栈顶指针。栈顶和栈底。datanext栈顶S栈底datanextSe = Ap13SandQAStatus pop (Stackptr &s,SElemType & e) if ( ! s) exit( UNDERFLOW ) ;e = s- data; p = s; s = s- next; free(p);return OK; / push;13物料管理1、栈表示的栈的操作：s 是栈顶指针。栈顶和栈底。datanext栈顶S栈底datanextpS14SandQStatus pop (Stackptr &s,SElemType & e) i

12、f ( ! s) exit( UNDERFLOW ) ;e = s- data; p = s; s = s- next; free(p);return OK; / push;14物料管理1、栈表示的栈的操作：s 是栈顶指针。栈顶和栈底。其它操作类似。datanext栈顶S栈底datanextS15SandQStatus pop (Stackptr &s,SElemType & e) if ( ! s) exit( UNDERFLOW ) ;e = s- data; p = s; s = s- next; free(p);return OK; / push;15物料管理1、栈2、栈的应用： 数制

13、转换：例如：10 进制和 8 进制之间的数的转换。(1348)10168 余 4= 83 * a3 + 82 * a2 + 8 * a1 + 80 * a0= ( 82 * a3 + 81 * a2 + a1 ) 余 4 即 a0 4/ 两边同除以 816821=82 * a3 + 81 * a2 + a1/ 两边同除以 8余 0= ( 8 * a3 + a2) 余 0即 a1 0/ 两边同除以 8212=8 * a3 + a2余 5= ( a3)余 5即 a2 a3 5216SandQ250416物料管理1、栈2、栈的应用： 数制转换：10 进制和 8 进制之间的数的转换程序。17SandQ

14、2504void conversion ( ) iInitStack( S ); scanf( %d, N ); while ( N ) Push(S, N % 8); N = N/8;while ( ! Stackempty ) Pop(S, e);printf (“%d” , e );17物料管理1、栈2、栈的应用： 数制转换：顺便提一句， 10 进制小数如何变成 2 进制小数：例如： (0.4)100.4 8= ( ? )2=3.2( 0.3 )2( 0.011 )2 其余应用，如：括号匹配、表达式求值等，请自看。18SandQ18物料管理1、栈2、栈的应用： 数制转换：顺便提一句， 1

15、0 进制小数如何变成 2 进制小数：例如： (0.4)10= ( ? )20.4 8=3.2( 0.3 )2( 0.31 )2( 0.011 )2( 0.011001 )20.2 8=1.6 其余应用，如：括号匹配、表达式求值等，请自看。19SandQ19物料管理1、栈2、栈的应用： 数制转换：顺便提一句， 10 进制小数如何变成 2 进制小数：例如： (0.4)10= ( ? )20.4 8=3.2( 0.3 )2( 0.31 )2( 0.314 )2( 0.011 )2( 0.011001 )2( 0.011001100 )20.2 8=1.60.6 8=4.8 其余应用，如：括号匹配、表

16、达式求值等，请自看。20SandQ20物料管理4、队列1、定义：在表的一端进行，而在另一端进行删除的线性表。队尾：进行的一端。队首：进行删除的一端。出队进队队首队尾2、队列的表示： 顺序表示的队列(循环队列)：#define MaxQsize 4;typedef struct QElemTypeintint*base ;front ;rear;/队列的队首指针队尾指针空间21 Sueue ;SandQa1， a2， a3， a4， a5， a6， a7， a8， a9， a1021物料管理4、队列2、队列的表示： 顺序表示的队列(循环队列)：#define MaxQsize 4;typedef

17、 structQElemType intintueue ;*base ;front ; rear;/队列的队首指针队尾指针空间 S基本操作：iniQueue (S EnQueue(S DeQueue(Sueue &Q ) ;/ 以数组形式分配空间给队列ueue &Q, QElemType e ) ; / 将数据场之值 e 的结点进队ueue &Q, QElemType & e ) ; / 将队首结点的数据场之值放入/ e , 并将该结点从队列中删除22SandQ22物料管理4、队列基本操作的实现：iniQueue (SEnQueue(SDeQueue(Sueue &Q ) ;ueue &Q,

18、QElemType e ) ;ueue &Q, QElemType &e ) ;3rear2rearrear1rear0rear frontfrontfrontfrontfront当 A 进队时，如仍设队首指针 front 和队尾指针 rear 指向真正的队首和队尾，则front = rear空队Queuesize = 4 front = rear是队空标志和队空标志。因此，使 front 指向真正的队首而 rear指向真正队尾的后一结点(其它方案？)。23SandQCBABAAA23物料管理4、队列基本操作的实现：iniQueue (SEnQueue(SDeQueue(Sueue &Q )

19、;ueue &Q, QElemType e ) ;ueue &Q, QElemType &e ) ;3rear2rearrear1frontrear0rear frontfrontfrontfront当 A 进队时，如仍设队首指针 front 和队尾指针 rear 指向真正的队首和队尾，则front = rear空队Queuesize = 4 front = rear是队空标志和队空标志。因此，使 front 指向真正的队首而 rear指向真正队尾的后一结点(其它方案？)。24SandQCBBAAA24物料管理4、队列基本操作的实现：iniQueue (SEnQueue(SDeQueue(Su

20、eue &Q ) ;ueue &Q, QElemType e ) ;ueue &Q, QElemType &e ) ;3rear2rearfrontrear1rear0rear frontfrontfrontfront当 A 进队时，如仍设队首指针 front 和队尾指针 rear 指向真正的队首和队尾，则front = rear空队Queuesize = 4 front = rear是队空标志和队空标志。因此，使 front 指向真正的队首而 rear指向真正队尾的后一结点(其它方案？)。25SandQCBAAA25物料管理4、队列基本操作的实现：iniQueue (SEnQueue(SDe

21、Queue(Sueue &Q ) ;ueue &Q, QElemType e ) ;ueue &Q, QElemType &e ) ;rear32rearfrontrear1rear0rear frontfrontfrontfront当 A 进队时，如仍设队首指针 front 和队尾指针 rear 指向真正的队首和队尾，则front = rear当 D 进队时，队尾指针rear 指向真正的队尾的后一单元，由于此时 0 号单元已可以使用，所以rear = 0这就是所谓循环队列。认为具有最大下标的单元后面是26最小下标的单元。空队Queuesize = 4 front = rear是队空标志和队空

22、标志。因此，使 front 指向真正的队首而 rear指向真正队尾的后一结点(其它方案？)。SandQDCBAAA26物料管理4、队列基本操作的实现：iniQueue (SEnQueue(SDeQueue(Sueue &Q ) ;ueue &Q, QElemType e ) ;ueue &Q, QElemType &e ) ;32rearfrontrear1rear0rear frontfrontfrontfrontrear当 A 进队时，如仍设队首指针 front 和队尾指针 rear 指向真正的队首和队尾，则front = rear当 D 进队时，队尾指针rear 指向真正的队尾的后一单元

23、，由于此时 0 号单元已可以使用，所以rear = 0这就是所谓循环队列。认为具有最大下标的单元后面是27最小下标的单元。空队Queuesize = 4 front = rear是队空标志和队空标志。因此，使 front 指向真正的队首而 rear指向真正队尾的后一结点(其它方案？)。SandQDCBAAA27物料管理4、队列基本操作的实现：iniQueue (SEnQueue(SDeQueue(Sueue &Q ) ;ueue &Q, QElemType e ) ;ueue &Q, QElemType &e ) ;32rearfrontrear1rearrear0rear frontfron

24、tfrontfront当 A 进队时，如仍设队首指针 front 和队尾指针 rear 指向真正的队首和队尾，则front = rear空队Queuesize = 4 front = rear是队空标志和队空标志。因此，使 front 指向真正的队首而 rear指向真正队尾的后一结点(其它方案？)。28SandQ当 E 进队时，队尾指针rear 指向真正的队尾的后一单元，所以rear = 1DCEBAAA28物料管理4、队列基本操作的实现：iniQueue (SEnQueue(SDeQueue(Sueue &Q ) ;ueue &Q, QElemType e ) ;ueue &Q, QElem

25、Type &e ) ;32rearfrontrearrear1rear0rear frontfrontfrontfront当 F 进队时，队尾指针rear 指向真正的队尾的后一单元，这样就造成了如下情况： front = rear当 A 进队时，如仍设队首指针 front 和队尾指针 rear 指向真正的队首和队尾，则front = rear空队Queuesize = 4 front = rear是队空标志和队空标志。解决：和队空标志。rear 的下一单元的下标 = front 就认为队列已满。注意：4 单元后是单元 1。单元未用足，29少用一个因此，使 front 指向真正的队首而 rear

26、指向真正队尾的后一结点(其它方案？)。单元。SandQDCFEBAAA29物料管理4、队列基本操作的实现：iniQueue (SEnQueue(SDeQueue(Sueue &Q ) ;ueue &Q, QElemType e ) ;ueue &Q, QElemType &e ) ;32rearfrontrearrear1Frear0rear frontfrontfrontfront当 A 进队时，如仍设队首指针 front 和队尾指针 rear 指向真正的队首和队尾，则front = rear空队Queuesize = 4 front = rear是队空标志和队空标志。因此，使 front

27、指向真正的队首而 rear指向真正队尾的后一结点(其它方案？)。30SandQ当 F 进队之前，由于rear 的下一单元的下标 = front队满。不可继续进行操作，错。DCEBAAA30物料管理4、队列基本操作的实现程序：iniQueue (Sueue &Q ) ;31SandQStatus iniQueue (Sueue &Q ) Q.base = ( QElemType * ) malloc(MAXSIZE * sizeof(QElemType);if ( ! Q.base) exit( OVERFLOW ) ;Q.front = Q.rear = 0; return OK; / 分配队

28、列的空间; 出队时应先判队是否空：条件 Q.rear = Q.front不空则出队，注意 Q.front 是否会由最高下标跳至最低下标(循环)。 进队时应先判队是否满：条件 ( ( Q.rear + 1) % MAXQSIZE ) = Q.front不满则进队，注意 Q.rear 是否会由最高下标跳至最低下标(循环)。 。31物料管理4、队列基本操作的实现程序：EnQueue (Sueue &Q, QElemType e )3 rearrear2frontrearfront10 front32再进队循环、满再进队循环、不满再进队满SandQCDCEDCEStatus EnQueue (Sueu

29、e &Q, QElemType e ) if ( ( ( Q.rear + 1) % MAXQSIZE ) = Q. front ) return( ERROR ) ;Q.base Q.rear = e;Q.rear = ( ( Q.rear + 1) % MAXQSIZE );return OK; / EnQueue ;32物料管理4、队列基本操作的实现程序：EnQueue (Sueue &Q, QElemType e )3 rear2frontrearfront1rear0 front33再进队循环、满再进队循环、不满再进队满SandQDCDCEDCEStatus EnQueue (Sue

30、ue &Q, QElemType e ) if ( ( ( Q.rear + 1) % MAXQSIZE ) = Q. front ) return( ERROR ) ;Q.base Q.rear = e;Q.rear = ( ( Q.rear + 1) % MAXQSIZE );return OK; / EnQueue ;33物料管理4、队列基本操作的实现程序：EnQueue (Sueue &Q, QElemType e )3 rear2rearfrontrear10 frontfront34再进队循环、满再进队满再进队不循环、不满SandQCEDCEDCEStatus EnQueue (S

31、ueue &Q, QElemType e ) if ( ( ( Q.rear + 1) % MAXQSIZE ) = Q. front ) return( ERROR ) ;Q.base Q.rear = e;Q.rear = ( ( Q.rear + 1) % MAXQSIZE );return OK; / EnQueue ;34物料管理4、队列基本操作的实现程序：EnQueue (Sueue &Q, QElemType e )3 rearrear2frontrear10 frontfront35再进队循环、满再进队满再进队不循环、不满SandQDCEDCEDCEStatus EnQueue

32、 (Sueue &Q, QElemType e ) if ( ( ( Q.rear + 1) % MAXQSIZE ) = Q. front ) return( ERROR ) ;Q.base Q.rear = e;Q.rear = ( ( Q.rear + 1) % MAXQSIZE );return OK; / EnQueue ;35物料管理4、队列基本操作的实现程序：DeQueue (Sueue &Q, QElemType &e )3rearrearfront rear2front1frontrear0 front36出队不循环出队不循环SandQEECStatus DeQueue (S

33、ueue &Q, QElemType & e ) if ( Q.rear = Q.front) return( ERROR ) ;e = Q.base Q.front ;Q.front = ( Q.front + 1) % MAXQSIZE ;return OK; / DeQueue ;36物料管理4、队列基本操作的实现程序：DeQueue (Sueue &Q, QElemType &e )3frontfront rear2rearrear1rearfront0 front37出队循环出队循环SandQCEDCEStatus DeQueue (Sueue &Q, QElemType &e )

34、if ( Q.rear = Q.front) return( ERROR ) ;e = Q.base Q.front ;Q.front = ( Q.front + 1) % MAXQSIZE ;return OK; / DeQueue ;37物料管理4、队列 求队中结点的个数：( Q.rear - Q.front + MAXSIZE ) % MAXSIZE 循环队列的应用实例：打印缓冲区的安排。front rearfrontrearrearfrontrearfrontI、J、K 要进队不行，必须等待！38rearfrontSandQCDEFGHCDEFGHCDEFGHABC38物料管理4、队列

35、表示的队列：参照下图所示。其中Q.front 和 Q.rear 分别是队首和队尾指针。它们指示着真正的队首的前一结点和真正的队尾结点。datanextQ.front队首结点Q.rear队尾结点队列的操作：39SandQtypedef struct Qnode QElemTypedat a; structQnode * next; Qnode, * QueuePtr;typedef struct QueuePtrfront; QueuePtrrear; LinkQueue;39物料管理4、队列队列的操作：datanextQ.front Q.reardatanext队尾结点(队首结点)Q.fron

36、tQ.reardatanext队首结点队尾结点Q.frontQ.rea4r0SandQ40物料管理习题3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序进行出栈，请回答下述问题：n(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?n(2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。(3) 请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操

37、作得到的。3.2 链栈中为何不设置头结点?3.2 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如 果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所 以只要有链表的头指针就可以了。3.3 循环队列的优点是什么? 如何判别它的空和满?答：循环队列的优点是：它可以克服顺序队列的“假上溢”现象，能够使队列的向量空间得到充分的利用。判别循环队列的“空”或“满”不能以头尾 指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别 队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是nnnnnn否会重合，如果会重合就认为队列已满。三是设置一计数

38、器数，不仅可判别空或满，还可以得到队列中元素的个数。队列中元素总41SandQ41物料管理习题n 3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?n 答：当只设头指针时，出队的时间需要n ，而入队的时间也需要n，因为每次出队均需从头指针开始查找，找到最后一个结点时，才能将其指针场的内容改 为被删队首结点的直接后继结点的地址；而入队时同样需要队尾结点。若只设 尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。front7rearn 3.5 指出下述程序段的功能是什么?(1) voi

39、d Demo1(SeqStackS)int i; arr64 ; n=0 ; while ( !StackEmpty(S)arrn+=Pop(S);for (i=0; i n; i+) Push(S, arri); /Demo142SandQtypedef struct SElemType * base ; SElemType * top ;intstacksize; SqStack;1 0872342物料管理习题n (2) SeqStack S1, S2, tmp;DataType x;./假设栈tmp和S2已做过初始化while ( ! StackEmpty (S1) x=Pop(S1)

40、;Push(tmp,x);while ( ! StackEmpty (tmp) )x=Pop( tmp);Push( S1,x);Push( S2, x);43SandQtypedef struct SElemType * base ; SElemType * top ;intstacksize; SqStack;43物料管理习题(3) void Demo2( SeqStack S, int m)/ 设DataType 为int 型SeqStack T; int i; InitStack ( T ); while (! StackEmpty( S ) )if( i=Pop(S) != m) P

41、ush( T,i); while (! StackEmpty( T) i=Pop(T); Push(S,i); (4)void Demo3( CirQueue Q)/ 设DataType 为int 型int x; SeqStack S; InitStack( S);while (! QueueEmpty( Q ) x=DeQueue( Q); Push( S,x);while (! StackEmpty( s) x=Pop(S); EnQueue( Q,x );/ Demo344SandQ44物料管理习题(5) CirQueue Q1, Q2; / 设DataType 为int 型int x,

42、 i , m = 0;./ 设Q1已有内容， Q2已初始化过while ( !QueueEmpty( Q1) ) x=DeQueue( Q1 ) ; EnQueue(Q2, x); m+; for (i=0; i n; i+) x=DeQueue(Q2) ;EnQueue( Q1, x) ; EnQueue( Q2, x);45SandQ45物料管理习题答：(1) 程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。(2) 程序段的功能是利用tmp栈将一个非空栈的所有元素按原样到一个空栈当中去。(3)程序段的功能是将一

43、个非空栈中值等于m的元素全部删去。(4)程序段的功能是将一个循环队列反向排列，原来的队头变成队尾，原来的队尾变成队头。(5)首先指出程序可能有印刷错误，for语句中的n应为m才对。这段程序的功能是将队列1的所有元素到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素到队列1中。46SandQ46物料管理习题3.6 回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符 入栈)n3.7 设计算法一个算术表达式的圆括号是否正确配对。 (注：对表达式进行扫描，凡n

44、遇到(就进栈，遇)就退掉栈顶的(，表达式被扫描完毕，栈应为空。解：根据提示，可以设计算法如下：#include #include stack.hint PairBracket( char * S) /检查表达式中括号是否配对nnnnint i;SeqStack T; / 定义一个栈nInitStack ( T );for (i=0; itop0 = -1;S-top1 = StackSize; /这里的top1也指出了空间大小，但由/ 于是作为栈底，因此出错int EmptyStack( DblStack &S, int i )/判栈空(栈号 i)return( (i = = 0& S.top0 = = -1)|(i= =1&S.top1= = StackSize) ) ;49SandQ49物料管理习题int FullStack( DblStack & S)/判栈满,满时肯定两头相遇return ( S.top0 = = S.top1-1);void Push(DblStack *S, int i, Datatype x)/进栈(栈号i)if (FullStack( S ) Error(Stack overflow); exit /上溢、if ( i = = 0) S.Data + S.top0= x;