用带头节点的链式存储实现栈的操作-程序员充电站

1.栈是一种只能在一端进行插入和删除的线性表

2.先构建一个数据类型，里面有next,data,top(可有可无）

typedef struct LNode { int top;//初始化的时候top等于-1，只有有数据就让top=1,这个数据项可有可无 struct LNode* next;//和单链表一样 int data;//数据域 }LNode,*LinkStack;//重命名

3.链栈的初始化

void InitStack(LinkStack* Ps) { (*Ps) = (LinkStack)malloc(sizeof(LNode));//创建头节点，不存放数据 if ((*Ps) == NULL) return; (*Ps)->next = NULL;//养成良好的习惯表尾置为空 (*Ps)->top = -1;//说明此时是没有元素的 }

4.从头节点进栈，这种时间复杂度比较高效，每次进栈时间复杂度为O（1）

int HeadPush(LinkStack* Ps, int elem)//前插 { LNode* s = (LNode*)malloc(sizeof(LNode));//和单链表一样 if (s == NULL) return 1; s->data = elem;//把数据赋值给新开辟的节点 s->next=(*Ps)->next;//把头节点的下一个元素赋值给s节点，就是把s的后驱链接到头节点的后驱 (*Ps)->next = s;//把头节点的后驱改为s,这样就把s节点给插入到表头的后面 s->top = 1;//可有可无 return 0; }

5.从头节点出栈，这种时间复杂度比较高效，每次出栈时间复杂度为O（1）

int HeadPop(LinkStack* Ps)//前删 { if ((*Ps)->next == NULL) { return 1; } LNode*temp=(*Ps)->next;//删除头节点的下一个节点 (*Ps)->next = temp->next;//把头节点的下一个节点指向下下个节点，跳过一个节点 if (temp->next = NULL) { (*Ps)->top = -1;//说明此时没有元素，可有可无 } free(temp);//因为是动态内存开辟的，是放在栈区的，需要手动释放 return 0; }

6.尾节点的进栈，可以一次性进栈也可以每次进栈一个元素。只需要找到最后一个非空的节点，在后面插入一个元素就可以了。

int TailPush(LinkStack* Ps)//这是一次性全部个建立好 { LNode* tail = (*Ps); int x = 0; scanf("%d", &x); while (x != 99)//等于99就不在建立 { LNode* s = (LNode*)malloc(sizeof(LNode)); if (s == NULL) return 1; s->next = tail->next; s->data = x; s->top = 1; tail->next = s; tail = s; scanf("%d", &x); } tail->next = NULL; return 0; }

int TailPush(LinkStack* Ps,int elem)//尾插法，这种办法有点笨，需要每次找到倒数第一个节点 { LNode* p = GetTail(Ps);//找到倒数第一个非空节点，然后在后面插入一个数据 LNode* s = (LNode*)malloc(sizeof(LNode)); if (s == NULL) { return 1; } s->next = p->next; p->next = s; s->top = 1; s->data = elem; return 0; }

7.尾节点出栈。需要找到倒数第二个元素，然后进行删除，当链表只有一个元素这种情况要考虑一下

int TailPop(LinkStack* Ps) { if (NULL == (*Ps)->next) return -1; if ((*Ps)->next->next == NULL)//如果这个链表只有一个元素 { LNode* ptr = (*Ps)->next; (*Ps)->next = ptr->next; free(ptr); return 0; } LNode* ptr = (*Ps); while (ptr->next->next)//链表有两个以上的元素 { ptr = ptr->next; } LNode* temp = ptr->next; ptr->next = temp->next; free(temp);//需要释放 }

8.得到栈顶元素，由于可以通过尾插法和头插法两种方式，所以分别对应一种方式

int Gettop(LinkStack* Ps)//头插法找top { if ((*Ps)->next == NULL) { return -1; } return (*Ps)->next->data;//既可以返回数据也可以判断是不是空链表 }//链式存储没有存满的

LNode* GetTail(LinkStack* Ps)//尾插法找top { LNode* p = (*Ps); while (p->next) { p = p->next; } return p;//是倒数最后一个指针 }

9.打印链表元素的函数

void Destory(LinkStack* Ps) { int ret = 0; while (ret!=1) { ret = HeadPop(Ps);//HeadPop出栈成功会返回0，空栈会返回1 } free(*Ps); }

10.整体函数

typedef struct LNode { int top;//初始化的时候top等于-1，只有有数据就让top=1,这个数据项可有可无 struct LNode* next;//和单链表一样 int data;//数据域 }LNode,*LinkStack;//重命名 void InitStack(LinkStack* Ps) { (*Ps) = (LinkStack)malloc(sizeof(LNode));//创建头节点，不存放数据 if ((*Ps) == NULL) return; (*Ps)->next = NULL;//养成良好的习惯表尾置为空 (*Ps)->top = -1;//说明此时是没有元素的 } int HeadPush(LinkStack* Ps, int elem)//前插 { LNode* s = (LNode*)malloc(sizeof(LNode));//和单链表一样 if (s == NULL) return 1; s->data = elem;//把数据赋值给新开辟的节点 s->next=(*Ps)->next;//把头节点的下一个元素赋值给s节点，就是把s的后驱链接到头节点的后驱 (*Ps)->next = s;//把头节点的后驱改为s,这样就把s节点给插入到表头的后面 s->top = 1;//可有可无 return 0; } int HeadPop(LinkStack* Ps)//前删 { if ((*Ps)->next == NULL) { return 1; } LNode*temp=(*Ps)->next;//删除头节点的下一个节点 (*Ps)->next = temp->next;//把头节点的下一个节点指向下下个节点，跳过一个节点 if (temp->next = NULL) { (*Ps)->top = -1;//说明此时没有元素，可有可无 } free(temp);//因为是动态内存开辟的，是放在栈区的，需要手动释放 return 0; } int TailPush(LinkStack* Ps)//这是一次性全部个建立好 { LNode* tail = (*Ps); int x = 0; scanf("%d", &x); while (x != 99)//等于99就不在建立 { LNode* s = (LNode*)malloc(sizeof(LNode)); if (s == NULL) return 1; s->next = tail->next; s->data = x; s->top = 1; tail->next = s; tail = s; scanf("%d", &x); } tail->next = NULL; return 0; } LNode* GetTail(LinkStack* Ps)//尾插法找top { LNode* p = (*Ps); while (p->next) { p = p->next; } return p;//是倒数最后一个指针 } int TailPush(LinkStack* Ps,int elem)//尾插法，这种办法有点笨，需要每次找到倒数第一个节点 { LNode* p = GetTail(Ps);//找到倒数第一个非空节点，然后在后面插入一个数据 LNode* s = (LNode*)malloc(sizeof(LNode)); if (s == NULL) { return 1; } s->next = p->next; p->next = s; s->top = 1; s->data = elem; return 0; } int TailPop(LinkStack* Ps) { if (NULL == (*Ps)->next) return -1; if ((*Ps)->next->next == NULL)//如果这个链表只有一个元素 { LNode* ptr = (*Ps)->next; (*Ps)->next = ptr->next; free(ptr); return 0; } LNode* ptr = (*Ps); while (ptr->next->next)//链表有两个以上的元素 { ptr = ptr->next; } LNode* temp = ptr->next; ptr->next = temp->next; free(temp);//需要释放 } void Display(LinkStack* Ps) { LNode* p = (*Ps)->next; while (p) { printf("%d->", p->data); p = p->next; } printf("NULL\n"); } int Gettop(LinkStack* Ps)//头插法找top { if ((*Ps)->next == NULL) { return -1; } return (*Ps)->next->data;//既可以返回数据也可以判断是不是空链表 }//链式存储没有存满的 void Destory(LinkStack* Ps) { int ret = 0; while (ret!=1) { ret = HeadPop(Ps);//HeadPop出栈成功会返回0，空栈会返回1 } free(*Ps); } int main() { LinkStack L; InitStack(&L); //HeadPush(&L, 1); //HeadPush(&L, 2); //HeadPush(&L, 3); //Display(&L); //HeadPop(&L); //HeadPop(&L); //HeadPop(&L); TailPush(&L,1); TailPush(&L, 1); TailPush(&L, 1); TailPush(&L,1); Display(&L); TailPop(&L); TailPop(&L); TailPop(&L); TailPop(&L); Display(&L); int ret=Gettop(&L); if (ret == -1) { printf("空链表\n"); } else { printf("%d\n", ret); } return 0; }