栈1--介绍

忘是亡心i 2023-07-14 10:35 20阅读 0赞

###     栈是只能在某一端插入和删除的特殊线性表. ###

用桶堆枳物品.先堆进来的压在底下，随后一件一件往上堆。取走时.只能从上面一件一件取,  
堆和取都在顶部进行，底部一般是不动的.  
    栈就是一种类似桶堆积物品的数据结构.进行删除和插入的一端称栈顶.另一堆称桟底.  
插入一般称为进栈(PUSH),删除则称为退栈(POP).栈也称为后进先岀表(LIFO表).  
    一个栈可以用定长为n的数组s来表示，用一个栈指针top指向栈頂.若top=0，表示栈空,  
top=n时桟満.进栈时top加1,退栈时top减1.当top<O时为下溢.栈指针在运算中永远指向栈顶.

###     1.进桟（PUSH）算法 ###

①   若top> = n时，则给岀溢岀信息，作出错处理（进栈前首先检査栈是否已满，満则溢出,不満則作②  
    ②   top+ +（栈指针加1 .指向进栈地址）  
    ③   s\[top\] = x.结東（x为新进栈的元素）.

###        2.退栈（pop）算法 ###

①  若top< = 0.則给岀下溢信息.作出借处理（退栈前先检査是否已为空桟・空則下溢，不空则作②）,  
    ②  x=s\[top\].（退栈后的元素赋给x）,  
    ③  top--，结束（栈指针减1,指向栈頂）.

###     3.进栈、出栈的C+ +实现程序： ###

\# define n 100

void push（int s\[\]，int \* top，int \* x)//入栈  
    \{  
    if ( \*top==n) printf（“overflow”）;  
    else \{ ( \*top) + +, s\[ \*top\]=\*x;\}  
    \}

void pop(int s\[\],int \* y,int \* top)//出栈  
    \{  
    if （\*top= =0) printf(" underflow ") ;  
    else \{\*y=s\[\*top\];(\*top)--i; \}  
    \}

对于出栈运算中的“下溢”，程序中仅给出了一个标志信息，而在实际应用中，下溢可用  
    来作为控制程序转移的判断标志，是十分有用的.对于入栈运算中的"上溢"，则是一种致命  
    的错误，将使程序无法継续运行，所以要设法避免.