栈的定义及基本算法实现

男娘i 2023-07-16 07:59 35阅读 0赞

栈定义：是一种只能在一端进行插入或删除操作的线性表  
1)允许 进行插入、删除操作的一端称为 栈 顶 。  
2)表的另一端称为 栈底 。  
3)当栈中没有数据元素时 ， 称为 空栈 。  
4)栈的插入操作通常称为 进栈 或 入 栈 。  
5)栈的删除操作通常称为 退栈 或 出栈 。

![在这里插入图片描述][20200317221119548.jpg]  
例如:死胡同就是一个栈;洗1叠碗时的取放；  
栈据有先进后出特点可以理解为桶状结构；  
例: 设一个栈的**输入序列**为a,b,c,d， ， 则借助一个栈所得  
到的**输出序列**不可能是 。  
A. c,d,b,a B. d,c,b,a  
C. a,c,d,b D. d,a,b,c  
解答:  
A：a,b,c进栈c出栈，进栈d,d 出栈,后b,a 出栈；A正确  
B: a,b,c,d 出栈,d,c,b,a 出栈; B正确  
C: a进栈a出栈,b,c进栈,c出栈,d进栈d出栈,后b 出栈;C正确  
D:a,b,c,d进栈,应该为d,c,b,a出栈,D错误  
同理  
一个栈的输入序列为1 2 3 4 5,则下列序列中不可能是栈的输出序列的是( )  
A.2 3 4 1 5 B.5 4 1 3 2 C.2 3 1 4 5 D.1 5 4 3 2  
这题就选B  
逻辑结构->存储结构  
栈中元素逻辑关系与线性表的相同，栈可以采用与线性表相  
同的存储结构。  
栈—1.顺序栈 and 2.链栈  
**1.顺序栈**栈的*顺序存储方式就是在顺序表的基础上对插入和删除操作限制它们在顺序表的同一端进行*，所以同顺序表一样也可用一维数组表示。一般地，可以设定一个足够大的一维数组存储栈，数组中下标为0的元素就是栈底，对于栈顶，可以设一个指针top指示它。  
![在mooc)这里插入图片描述][mooc]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dJRklmdw_size_16_color_FFFFFF_t_70]**基本操作算法(这里以top=0为例)  
注意（top=-1时有些步骤不同，应根据定义实现算法）  
（1）初始化栈InitStack(&s)  
（2）销毁栈DestroyStack(&s)释放栈s占用的存储空间。  
（3）判断栈是否为空StackEmpty(s);此时top=0  
（4）进栈Push(&s,e)  
（5）出栈Pop(&s,&e)  
（6）取栈顶元素GetTop(s,&e) 在栈不为空的条件下将栈顶元素赋给e  
实现代码如下，**

#include<stdio.h>
    #include<stdlib.h>
    //栈抽象数据类型＝逻辑结构＋基本运算（运算描述）
    //栈的顺序存储结构的C语言描述如下：
    #define MAXSIZE 100
    typedef int datatype;
    typedef struct{
        
    datatype a[MAXSIZE];
    int top;
    }sequence_stack;
    sequence_stack s；
    //（1）初始化栈InitStack(&s)建立一个新的空栈s，实际上是将栈顶指针指向-1即
    //（2）销毁栈DestroyStack(&s)释放栈s占用的存储空间。
    //（3）判断栈是否为空StackEmpty(s);此时top=0
    //（4）进栈Push(&s,e)
    //（5）出栈Pop(&s)
    //（6）取栈顶元素GetTop(s,&e) 
    //(1)
    void InitStack(sequence_stack*&s){
        			
    	s=(sequence_stack*)malloc(sizeof(sequence_stack));
    	s->top=0;
    }
    //(2)
    void DestroyStack(sequence_stack*&s){
        
    	free(s);
    }
    //(3)是空表就返回1；
    int StackEmpty(sequence_stack s){
        
    	return(s.top? 0:1);
    }
    //(4)
    int push(sequence_stack *&s,datatype e)
    {
        
    if(s->top==MAXSIZE) {
        return 0;}
      s->a[s->top]=e;
      s->top++;
      return 1;
    }
    //(5)出栈Pop(&s)
    int pop(sequence_stack *&s )
    {
        
    if(s->top==0)
    {
        return 0;}
    s->top--;
    return 1;
    }
    //(6)取栈顶元素GetTop(s,&e) 
    bool GetTop(sequence_stack s,datatype *&e)
    {
        
    	if(s.top==0)return false;
    	else *e=s.a[s.top-1];
    	return true;
    }

**2.链栈**链式栈：采用链接存储的栈结构  
栈的链式存储结构实际上就是**一个单链表**，叫做链栈。插入和删除操作只能在**链栈的栈顶进行**；栈顶指针Top就是链表的头指针。  
**如何改造链表实现栈的链接存储？**  
1.将哪一端作为栈顶？答:将链头作为栈顶，方便操作。  
2.链栈需要加头结点吗?答：链栈不需要附设头结点；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dJRklmdw_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dJRklmdw_size_16_color_FFFFFF_t_70 2]  
**链栈的4 要素：**  
栈空条件：s- ->next=NULL  
栈满条件： 不考虑  
进栈e 操作： 将包含e 的节点插入到头节点之后  
退栈操作： 取出头节点之后节点的元素并删除之

#include<stdio.h>
    #include<stdlib.h>
    typedef int datatype;
    typedef struct node
    {
        
    datatype info;       //数值域
    struct node *next;   //指针域
    }linknode;
    typedef linknode * linkstack;//linknode *<=>linkstack
    linkstack top；
    //(1) 初始化栈initStack(&s)
    //建立 一个空栈s。创建链栈的头节点,并将其next域置为NULL。
    void initStack(linknode *&s)
    {
          
    	s=(linknode*)malloc(sizeof(linknode));     
        s->next=NULL;
    }
    //(2)取得链式栈的栈顶结点
    datatype read(linkstack top)
    {
        
    if(!top) {
        
    printf("\n链式栈是空的!");
    exit(1);}
    return (top->info);
    }
    //(3)向链式栈中插入一个值为x的结点,结点分配一个空间将其链接为top;
    linkstack push(linkstack top,datatype x)
    {
        
     linkstack p;
     p=(linkstack )malloc(sizeof(linknode));
     p->info=x;
     p->next=top;
     top=p; 
     return top;
    }
    //(4)链栈的实现-删除栈顶元素
    linkstack pop (linkstack top)
    {
        
    linkstack p;
    if (top==NULL)
    {
         printf("\n顺序栈是空的!\n");
    return top;
    }
    p=top;
    top=top->next; 
    free(p);
    return top;
    }
    int main()
    {
        }

**总结**  
顺序栈和链栈的比较  
时间性能：相同，都是常数时间O(1)。  
空间性能(储存结构不同)  
➢ 顺序栈：  
(1)有元素个数的限制和空间浪费的问题。  
(2)注意:top=0与top=-1时的不同；原因储存结构与逻辑结构不同  
➢ 链栈：  
（1）没有栈满的问题，只有当内存没有可用空间时才会出现栈  
满，但是每个元素都需要一个指针域，从而产生了**结构性开销**。  
总之，当栈的使用过程中**元素个数变化较大**时，用链栈是适宜的，  
反之，应该采用顺序栈。  
（2）注意:① 读栈顶（链式存储）结点值；② 链式栈的插入及删  
除（即进栈及出栈）；

[20200317221119548.jpg]: /images/20230528/208875c6495d41658fe976bfa424db6c.png
[mooc]: /images/20230528/90b737cd50da4a10923029e666b00583.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dJRklmdw_size_16_color_FFFFFF_t_70]: /images/20230528/469743f1dc894078b16a0ba9b2cc81d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dJRklmdw_size_16_color_FFFFFF_t_70 1]: /images/20230528/837bdd362434491c8d93a1c026e33df9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dJRklmdw_size_16_color_FFFFFF_t_70 2]: /images/20230528/0af59298247d48faab67d4fcee4a9d08.png