当前位置：首页 > news >正文

数据结构----栈

news 来源：原创 2024/9/20 9:26:19

一丶概念

只能在一端进行插入和删除操作的线性表（又称为堆栈），进行插入和删除操作的一端称为栈顶，另一端称为栈底

二丶特点

先进后出 FILO first in last out
后进先出 LIFO last in first out

三丶顺序栈

逻辑结构：线性结构
存储结构：顺序存储
操作：入栈、出栈

1.创建一个空的栈

2.入栈

3.出栈

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct seqstack
{int maxlen;     // 数组中元素总个数datatype *data; // 指向数组的指针int top;        // 栈顶元素的下表
} seqstack_t;
seqstack_t *CreateEplist(int len)//创建一个空表
{seqstack_t *p = (seqstack_t *)malloc(sizeof(seqstack_t));//先对结构体指针开辟堆区空间if (NULL == p)//判错{printf("Create err");return NULL;}p->maxlen = len;p->top = -1;//初始化结构体p->data = (int *)malloc(sizeof(int) * len);//对指向数组的指针开辟堆区空间if (NULL == p->data)//判错{printf("DATA err");return NULL;}return p;
}
int Isfull(seqstack_t *p)//判断结构体是否为满
{return p->top + 1 == p->maxlen;
}
int IsEmpty(seqstack_t *p)//判断结构体是否为空
{return p->top == -1;
}
int Pushdata(seqstack_t *p, int data)//输入数据，入栈
{if (Isfull(p)){printf("Seqstack is full");return -1;}p->top++;p->data[p->top] = data;return 0;
}
int show(seqstack_t *p)//输出数据，出栈
{if (IsEmpty(p)){printf("Seqstack is empty");return -1;}while (!IsEmpty(p)){p->top--;printf("%d ",p->data[p->top + 1]);}printf("\n");
}
void Clearlist(seqstack_t *p)//清空栈
{p->top = -1;
}
int main(int argc, char const *argv[])
{seqstack_t *p = CreateEplist(10);Pushdata(p, 1);Pushdata(p, 2);Pushdata(p, 3);Pushdata(p, 4);Pushdata(p, 5);show(p);printf("%d\n", p->top);printf("%d\n", p->maxlen);return 0;
}

练习：

1. 若进栈顺序为 1,2,3,4 一下四种情况不可能出现的出栈序列是( )

A. 1,4,3,2 B. 2,3,4,1 C. 3,1,4,2 D. 3,4,2,1

2. 下列叙述正确的是( )

A. 线性表是线性结构
B. 栈与队列是非线性结构 //栈只能在一端进行插入和删除操作的线性表
C. 线性链表是非线性结构
D. 二叉树是线性结构 //树形结构层次关系

3. 下列关于栈叙述正确的是( )

A.在栈中只能插入数据//栈只能在一端进行插入和删除操作的线性表，插入和删除端称为栈顶，另一端是栈底
B.在栈中只能删除数据
C.栈是先进先出的线性表
D.栈是先进后出的线性表

四丶链式栈

逻辑结构：线性结构

存储结构：链式存储
操作：入栈、出栈

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct linkstack
{datatype data;          // 数据域struct linkstack *next; // 指针域
} linkstack_t;
// 1.创建一个空的栈
void CreateEpLinkStack(linkstack_t **ptop)
{*ptop = NULL; // 主函数中top = NULL;
}
// 2.入栈   data是入栈的数据
//  参数上之所以采用二级指针，因为我们要随着入栈添加新的节点作为头，top需要永远指向当前链表的头，
//  那么修改main函数中的top，我们采用地址传递
int PushLinkStack(linkstack_t **ptop, datatype data)
{// 1.创建一个新节点，并初始化linkstack_t *pnew = (linkstack_t *)malloc(sizeof(linkstack_t));if (pnew == NULL){perror("PushLinkStack err");return -1;}pnew->data = data;pnew->next = NULL;// 2.将新节点头插到无头单向链表中pnew->next = *ptop;// 3.移动栈针，栈针top永远只向无头单向链表的第一个节点*ptop = pnew;return 0;
}
// 3.判断栈是否为空
int IsEpLinkStack(linkstack_t *top)
{return top == NULL;
}
// 4.出栈
datatype PopLinkStack(linkstack_t **ptop)
{// 1.容错判断if (IsEpLinkStack(*ptop)){perror("IsEpLinkStack");return -1;}// 2.定义pdel指向被删除节点linkstack_t *pdel = *ptop;// 3.定义一个变量temp保存出栈数据datatype temp = pdel->data;// 4.移动栈针(跨过被删除节点)*ptop = (*ptop)->next;// 5.释放被删除节点free(pdel);pdel = NULL;return temp;
}
// 5.清空栈
void ClearLinkStack(linkstack_t **ptop) // 用二级指针，是因为清空后需要将main函数中的top变为NULL
{while (!IsEpLinkStack(*ptop))PopLinkStack(ptop);
}
// 6.求栈的长度
int LengthLinkStack(linkstack_t *top) // 用一级指针，是因为我只是求长度，不需要修改main函数中top指针的指向
{int len = 0;// top相当于无头单向链表的头指针，求长度，遍历无头单向链表while (top != NULL){len++;top = top->next;}return len;
}
// 7.获取栈顶数据,不是出栈,不需要移动main函数中的top，所以用一级指针
datatype GetTopLinkStack(linkstack_t *top)
{if (!IsEpLinkStack(top))return top->data;return -1;
}int main(int argc, char const *argv[])
{linkstack_t *top; //CreateEpLinkStack(&top);for (int i = 1; i <= 5; i++)PushLinkStack(&top, i);printf("top value is %d\n", GetTopLinkStack(top));printf("len is %d\n", LengthLinkStack(top));while (!IsEpLinkStack(top)){printf("%d ", PopLinkStack(&top));}printf("\n");return 0;
}