最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

全球焦点！[数据结构] 栈 (C语言)

来源：博客园


(相关资料图)

栈

栈的概念

栈（stack）是一种特殊的线性表存储结构，其一端可以进行插入和弹出的操作，而另一端是封死的。

可以把栈想象成是一个柱状的容器。就比如一个乒乓球筒，我们只能在筒的一段进行乒乓球的放入和取出。

栈顶和栈的两种操作

栈顶就是栈的开口端，每次都是在栈顶处插入元素和删除元素。（1）入栈：将新元素存入栈中，并作为新的栈顶元素；（2）出栈：将栈顶元素弹出，并将其下面的元素作为新的栈顶元素。

栈的特性

栈有着先进先出的特性。假如入栈元素依次是 1、2、3，且中途没有元素出栈，那么最后所有元素出栈的顺序是 3、2、1。

顺序栈

顺序栈基本概念

顺序栈是用数组来实现栈的存储结构，一般会定义一个栈顶 top，初始情况下 top值为-1，表示栈为空，此时栈中无任何元素。每当有元素入栈，top就 +1; 有元素出栈， top就 -1。

顺序栈的入栈操作

顺序栈入栈操作图解

初始情况下的栈

元素1入栈

元素2入栈

元素3入栈

顺序栈入栈操作代码

//元素入栈void push(SqStack *s, Elemtype x){    if(s->top == MAXSIZE - 1) return;  //栈满    s->data[++s->top] = x;}

顺序栈的出栈操作

顺序栈出栈操作图解

元素3出栈

元素2出栈

元素1出栈

顺序栈出栈操作代码

//元素出栈void pop(SqStack *s, Elemtype *x){    if(s->top == -1) return;  //栈空    *x = s->data[s->top--];}

顺序栈完整程序

源代码

#include#include#include#define MAXSIZE 1000typedef int Elemtype;typedef struct{    Elemtype data[MAXSIZE];    int top;                //栈顶指针}SqStack;//初始化栈void Init_SqStack(SqStack *s){    s->top = -1;}//判断栈是否为空bool IsEmpty(SqStack *s){    return s->top == -1;}//元素入栈void push(SqStack *s, Elemtype x){    if(s->top == MAXSIZE - 1) return;    s->data[++s->top] = x;}//元素出栈void pop(SqStack *s, Elemtype *x){    if(s->top == -1) return;    *x = s->data[s->top--];}//取栈顶元素Elemtype top(SqStack *s){    if(IsEmpty(s)){printf("栈为空\n");return -1;    }    return s->data[s->top];}int main(){    SqStack mystack;    Init_SqStack(&mystack);    for(int i = 1; i <= 5; i++)push(&mystack, i);    printf("当前栈顶元素为: %d\n", top(&mystack));    int e;    pop(&mystack, &e);    printf("出栈元素为: %d\n", e);    printf("当前栈顶元素为: %d\n", top(&mystack));    printf("全部元素出栈：\n");    while(!IsEmpty(&mystack)){    printf("%d ", top(&mystack));    pop(&mystack, &e);    }}

顺序栈运行测试

链栈

链栈基本概念

链栈是用链式存储结构实现的，在实现过程中，需要定义一个 top指针保持指向当前栈顶。操作过程和链表有些相似。

链栈的入栈操作

链栈入栈操作图解

初始情况下的链栈

元素1入栈

元素2入栈

元素3入栈

链栈入栈操作代码

//入栈void LinkStack_push(LinkStack *S, ElemType e){    LinkStacknode *node;                node = (LinkStacknode *) malloc(sizeof(LinkStack));    node->data = e;                node->next = S->top;       //新节点的next指向此时的top    S->top = node;             //top指针指向新的节点    S->length++;}

链栈的出栈操作

链栈出栈操作图解

元素3出栈

元素2出栈

元素1出栈

链栈出栈操作代码

//出栈void LinkStack_pop(LinkStack *S, ElemType *e){    if(IsEmpty(S))               //栈空        return;                      LinkStacknode *del = S->top;     *e = del->data;                  S->top = del->next;          //top跳过出栈节点，指向出栈节点的下一节点    S->length--;    free(del);                   //释放内存}

链栈完整程序

源代码

#include #include //定义数据类型typedef int ElemType;//链栈的节点结构typedef struct LinkStacknode{    ElemType data;              //存数据    struct LinkStacknode *next; //存下个节点的地址} LinkStacknode;//链栈的整体结构  typedef struct {    LinkStacknode *top;    int length;    } LinkStack;//初始化链栈void Create_LinkStack(LinkStack *S){    S->top = NULL;    S->length = 0;}//判断栈为空bool IsEmpty(LinkStack *S){    return S->length == 0;}//入栈void LinkStack_push(LinkStack *S, ElemType e){    LinkStacknode *node;                node = (LinkStacknode *) malloc(sizeof(LinkStack));    node->data = e;                node->next = S->top;       //新节点的next指向此时的top    S->top = node;             //top指针指向新的节点    S->length++;}//出栈void LinkStack_pop(LinkStack *S, ElemType *e){    if(IsEmpty(S))               //栈空        return;                      LinkStacknode *del = S->top;     *e = del->data;                  S->top = del->next;          //top跳过出栈节点，指向出栈节点的下一节点    S->length--;    free(del);                   //释放内存}//取栈顶ElemType LinkStack_getTop(LinkStack *S){    if(IsEmpty(S)){        printf("栈为空\n");        return -1;    }    return S->top->data;}int main(){    LinkStack S;    Create_LinkStack(&S);    ElemType e;    ElemType a[5] = {3,6,7,9,10};    for(int i = 0; i < 5; i++)        LinkStack_push(&S, a[i]);    printf("栈顶元素：%d\n", LinkStack_getTop(&S));    LinkStack_pop(&S, &e);    printf("出栈元素：%d\n", e);       printf("全部元素出栈：\n");    while(!IsEmpty(&S)){        printf("%d ", LinkStack_getTop(&S));        LinkStack_pop(&S, &e);    }    return 0;}

链栈运行测试

关键词： 运行测试 基本概念 完整程序