数据结构::链栈

数据结构::链栈

 

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define MaxSize 10
typedef int ElemType;

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LinkStack;

// 创建链栈
LinkStack*InitStack(){
    LinkStack*s = (LinkStack*)malloc(sizeof(LinkStack));
    s->next = NULL;
    return s;
}
// 判断是否为空
bool empty(LinkStack *s){
    // 为空则说明头节点指向为空
    return s->next == NULL;
}
// 进栈
void push(LinkStack *s, ElemType e){
    // 创建一个新的节点
    LNode *t = (LNode*)malloc(sizeof(LNode));
    // 链接到链栈上来,进栈操作相当于链表的头插法
    t->data = e;
    t->next = s->next;
    s->next = t;
    // s始终指向的是链表的头结点
}
// 出栈
void pop(LinkStack *s, ElemType &e){
    // 判断是否为空栈
    if(empty(s))exit(1);
    // 这里先用一个指针p取得链表第一个节点,相当于栈顶结点
    // 防止出栈后断链
    LNode *p = s->next;
    e = p->data;
    s->next = p->next;
    free(p);
}
// 取得栈顶元素的值
ElemType GetTop(LinkStack *s){
    return (s->next->data);
}
// 获取栈中元素的个数
int StackLength(LinkStack *s){
    // 这里使用一个指针p依次遍历链表
    // 从栈顶元素开始
    LNode *p = s->next;
    int i = 0;
    while(p){
        p = p->next;
        i++;
    }
    return i;
}
int main(){
    // 初始化链栈
    LinkStack *s = InitStack();
    ElemType e;
    printf("请输入要入栈的元素个数:\n");
      int n;
      int i = 0;
      scanf("%d",&n);
      printf("请输入要入栈的元素:\n");
      while(i < n){
            scanf("%d",&e);
            push(s,e);
            i++;
    }

    printf("逐个出栈:\n");
    while(!empty(s)){
            pop(s,e);
            printf("%d  ",e);
    }
    printf("\n");
    push(s,70);
    printf("栈中有元素个数为:%d,栈顶元素为%d\n", StackLength(s), GetTop(s));
    return 0;
}

 

上一篇:从尾到头打印链表


下一篇:BJFU_数据结构习题_253递归求解单链表中的平均值