数据结构——堆栈和队列

女爷i 2022-07-26 00:06 198阅读 0赞

堆栈和队列都是特殊的线性表，线性表、堆栈和队列三者的数据元素以及数据元素之间的逻辑关系完全相同。  
**差别：**线性表的插入和删除操作不受任何限制，**而堆栈只能在栈顶插入和删除，队列只能在队尾插入，在对头删除。**

--------------------

### 1.堆栈（先进后出，或后进先出线性表） ###

*  几个专业术语解释：  
    **栈顶**：堆栈中允许进行插入和删除数据元素操作的一端称为栈顶  
    **栈底**：栈顶的另外一端  
    **栈顶指示器（或栈顶指针）**：栈顶的当前位置是动态的，用于标记栈顶当前位置的变量称为指示器；
 *  堆栈的抽象数据类型：  
    1.数据集合：  
    堆栈的数据集合表示为a0,a1,a2……，每个数据类型为DataType.  
    2.操作集合：
    
    **(顺序堆栈的存储结构)**  
    顺序堆栈和顺序表的数据成员是相同的，不同之处是，顺序堆栈的入栈和出栈操作只能对当前栈顶元素进行。  
    定义结构体：
    
        typedef struct
        {
            DataType stack[MaxStackSize];
            int top;       //top表示顺序堆栈数组stack的当前栈顶位置
        }SeqStack;
    
    与顺序表相比较可知，顺序堆栈和顺序表两者除数据域名和结构体名不同外，其他结构完全相同。  
    （1.）初始化StackInitiate(\*S)
    
        void StaticInitiate(*S)
        {
            S->top=0;    //初始化栈顶下标值
        }
    
    （2.）非空否StackNotEmpty(S)
    
        int StackNotEmpty(S)  //判断顺序堆栈S是否为空，非空返回1，否则返回0
        {
            if(S.top<=0)return 0;
            else return 1;
        }
    
    （3.）入栈StackPush(SeqStack \*S,DataType x)
    
        int StackPush(SeqStack *S,DataType x)//把数据元素x存入顺序堆栈S中，入栈成功返回1，否则返回0
        {
            if(S->top>=MaxStackSize)
            {
                printf("堆栈已满，无法插入！\n")
                return 0;
            }
            else
            {
                S->Stack[S->top]=x; S->top++; return 1; } }
    
    （4.）出栈StackPop(SeqStack \*S,DataType \*d)
    
        int StackPop(SeqStack *S,DataType) //取出顺序堆栈S的栈顶元素值由参数d带回，出栈成功则返回1，否则返回0
        {
            if(S->top<=0)
            {
                printf("堆栈已空无数据元素出栈！\n");
                return 0;
            }
            else
            {
                S->top--;        //得注意top--，--top的差别
                *d=S->stack[S->top]; return 1; } }
    
    （5.）取栈顶数据元素StackTop(SeqStack S,DataType \*d) **与出栈相比较，不需要top–**
    
        int StackTop(SeqStack S,DataType *d) //取栈顶数据元素值由参数d带回，成功返回1，不成功返回0
            {
                if(S.top<=0)
                {
                    printf("堆栈已空！\n");
                    return 0;
                }
                else
                {
                    *d=S.stack[S.top-1];  
                    return 1;
                }
            }
    
    以上实现顺序堆栈操作的所有函数中，都没有循环语句，所以**顺序堆栈所有操作时间复杂度均为O(1)**

（**顺序表的链式表示**）  
堆栈有两端，插入元素和删除元素的一端为栈顶，另一端为栈底。对于链式堆栈来说，显然，吧靠近头指针的一端定义为栈顶，则插入元素和删除元素时不需要遍历整个链，其时间复杂度为O(1);否则，若把远离头指针的一端定义为栈顶，则每次插入元素和删除元素都需要遍历整条链，其时间复杂度为O(n).  
**因此，链式堆栈一般设计把靠近头指针的一端为栈顶**  
虽然链式堆栈的插入和删除都是在链表的表头进行的，但是若把链式堆栈设计成带头结点的结构，，则插入和删除改变的只是头指针所指向结点的Next域的值（即head->next值），而不是头指针的值，因此可以把**链式堆栈设计成带头结点的结构**。

链式堆栈结点的结构体定义：

typedef struct snode
    {
        DataType data;
        struct snode *next;
    }LSNode;

(1.)初始化StackInitiate(LSNode \*\*head)

void SatckInitiate(LSNode **head) //初始化带头结点的链式堆栈
    {
        *head=(LSNode *)malloc(sizeof(LSNode));
        (*head)->next=NULL;
    }

(2.)非空否StackNotEmpty(LSNode \*head)

int StackNotEmtpty(LSNode *head)  //判断堆栈是否为空，如果为空，返回1，否则返回0
    {
        if(head->next==NULL)return 0;
        else return 1;
    }

(3.)入栈StackPush(LSNode \*head,DataType x)

void StackPush(LSNode *head,DataType x)  //把数据元素x插入链式堆栈head的栈顶作为新的栈顶
    {
        LSNode *p;
        p=(LSNode*)malloc(sizeof(LSNode));
        p->data=x;       
        p->next=head->next;     //新结点链入栈顶
        head->next=p;           //新节点称为新的栈顶
    }

(4.)出栈StackPop(LSNode \*head,DataType \*d)

int StackPop(LSNode *head,DataType *d)   //出栈并把栈顶元素由参数d带回，出栈成功返回1，否则返回0
    {
        LSNode *p=head->next;
        if(p==NULL)
        {
            printf("堆栈已空出错！");
            return 0;
        }
        head->next=p->next;        //删除原栈顶结点
        *d=p->data;               //原栈顶结点元素赋予d
        free(p);                  //释放原栈顶结点内存空间
        return 1;
    }

(5.)取栈顶数据元素StackTop(LSNode \*head,DataType \*d)

int StackTop(LSNode *head,DataType *d)   //取栈顶元素并把栈顶元素由参数d带回
    {
        LSNode *p=head->next;
        if(p==NULL)
        {
            printf("堆栈已空出错！");
            return 0;
        }
        *d=p->data;
        return 1;
    }

(6.)撤销动态申请空间Destory(SLNode \*head)

void Destory(SLNode *head)
    {
        LSNode *p,*p1;
        p=head;
        while(p!=NULL)
        {
            p1=p;
            p=p->next;
            free(p);
        }
    }

上述实现链式堆栈的所有函数中，没有循环语句，所以链式堆栈所有操作的时间复杂度均为O(1)  
上述链式堆栈结点的结构体定义和操作的实现函数都写在头文件LinStack.h中