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

本文主要是介绍《大话数据结构》栈——仅限定在表尾进行插入和删除操作的线性表。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.定义解读

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

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

2.栈的顺序表结构

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

注意：

1）进栈操作

/*插入元素e为新的栈顶元素 */#define MAXMIZE 100typedef 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方法，除了要有插入元素的参数外，还需要判断是哪个栈stacknumint 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));//开启了一个新nodeL->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,*nodeptrtypedef 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;}

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