《大话数据结构》栈——仅限定在表尾进行插入和删除操作的线性表。_栈限定仅在表尾

1.定义解读

栈是一个线性表，具有前后驱关系。

在线性表的表尾进行插入和删除操作，这里的表尾指的是栈顶。

2.栈的顺序表结构

#define MAXSIZE 1000
tyoedef struct
{
    int data[MAXSIZE];
    int top;//栈顶
}stack;

注意：

1）进栈操作

/*插入元素e为新的栈顶元素 */
 
#define MAXMIZE 100
 
typedef struct 
{
    int data[MAXMIZE];
    int top;
}stack;
 
int push(stack *s,int e)
{
    s->top++;
    s->data[s->top]=e;
    
    if(s->top==MAXSIZE-1)
            return 0;
    
    return 1;
}

2)出栈操作

/*若栈不空，则删除 S的栈顶元素，用 e 返回其值，并返回 OK ， 否则返回 BRROR */
 
#define MAXMIZE 100
typedef struct
{
    int data[MAXMIZE];
    int top;
}stack;
 
int pop(stack *s,int *e)
{
    *e=s->data[s->top];
    s->top--;
    
    if(s->top==-1)
        return 0;
    
    return 1;
    
    
}

上述的两个均为涉及到任何循环语句，因此时间复杂度是O(1)

 

3.两栈共享空间

前提是：两个具有相同数据类型的栈

对于一个数组而言，他有两个端点，就可以当作是两个栈底，让其中一个栈底为数组的始端，即下标为0处，让另一个栈为栈的末端，即下标为数组长度的n-1处。

形成的操作是：当两个栈增加元素，就会向中间延申

 

如何判断栈满？

//栈共享空间
#define MAXSIZE 100
typedef struct
{
    int data[MAXSIZE];
    int top1;//栈顶指针
    int top2;//栈底指针
}dulstack;
 
//两栈共享空间的push方法，除了要有插入元素的参数外，还需要判断是哪个栈stacknum
 
int push(dulstack *s,int e,int stacknum)
{
    //这个要首先判断是否栈满,就不用担心溢出的问题了
    if(s->top1+1==s->top2)
        return 0;
    
 
    //栈1有元素进栈
    if(stacknum==1)
        s->top1++;
        s->data[s->top1]=e;
        //s->data[++s->top1]=e;
    //栈2有元素进栈
    else if(stacknum==2)
        s->top2--;
        s->data[s->top2]=e;
        //s->data[--s->top2]=e;
                     
    return 1;
}
 
/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回1,否则返回0*/
int pop(dulstack *s,int *e,int stacknum)
{
    if(stacknum==1)
    {
        //栈1是空栈
        if(s->top1==-1)
            return 0;
        s->top1--;
        *e=s->data[s->top1];        
    }
    else if(stacknum==2)
    {    
        //栈2是空栈
        if(s->top2==-1)
            return 0;
        s->top2++;
        *e=s->data[s->top2];
    }
    return 1；
        
}

4.栈的链式存储结构

把栈顶放在单链表的头部，对于栈链来说，是不需要头节点的。

对于空栈来说，链表的头指针是指向为空，那么栈链的空，其实就是top=NULL。

//链栈的结构
 
typedef struct node
{
    int data;
    struct node *next;
}node,*nodeptr;
 
typedef struct stack
{
    nodeptr top;
    int count;
}stack;

1)进栈操作

插入数据域为e的新节点s，top为栈顶指针

tpyedef struct node
{
    int data;
    struct node *next;
}node，*nodeptr；
 
typedef struct stack
{
    nodeptr top;
    int count;
}stack;
 
/*插入元素 e 为新的栈顶元素*/
int push(stack *s,int e)
{
    nodeptr L=(nodeptr)malloc(sizeof(node));//开启了一个新node
    L->data=e;
    L->next=s->top;
    s->top=L;//新节点L赋值给栈顶指针
    s->count++;
    
    return 1;
}

2）出栈

将p用来作为存储要删除的栈顶节点，将栈顶指针下移一位，最后释放p

typedef struct node
{
    int data;
    struct node *next;
}node,*nodeptr
 
 
typedef struct stack
{
    nodeptr top;
    int count;
}stack;
 
/* 若栈不空，则删除s的栈顶元素，并用e返回其值，并返回1，否则返回0*/
 
int pop(stack *s,int *e)
{
    nodeptr p;//定义了一个新节点
    *e=s->top->data;
    p=s->top;//将栈顶节点的值赋值给怕，（3）
    s->top=s->top->next;//将栈顶指针下移一位的关键操作
    free(p);
    s->count--;
    
    if(S->next==NULL)
        return 0;
    return 1;
    
    
}

 

顺序栈与链栈什么时候用？

 

栈的作用：