博客

栈链式存储的特点

链式存储，可以带头结点，或不带头结点，本篇介绍带头结点的链式存储栈的基本操作。

进栈、出栈都在头结点一侧进行。

由于带有头结点，可不设置栈顶指针，头结点可视为栈顶指针来进行操作。

链式存储栈的基本操作代码实现

/**
 * 带头节点的链式存储栈
 */
#include <cstdio>
#include <malloc.h>

/**
 * 定义结构
 */
typedef struct LNode{
    int data;             //指针域
    struct LNode *next;   //数据域
}SqStack,*LinkStack;

/**
 * 初始化栈
 */
LNode* initStack(LinkStack &linkStack){
    linkStack = (LinkStack)malloc(sizeof(LNode)); //创建头结点
    linkStack->data = -1;   //头结点指针域初始化为-1
    linkStack->next = NULL;
    return linkStack;
}

/**
 * 判断栈是否为空
 */
bool linkStackIsEmpty(LinkStack linkStack){
    if(linkStack->next == NULL){   // 只有头结点
        return true;  //栈空
    }
    return false;    //栈非空
}

/**
 * 进栈操作(只在头结点进行进栈操作)
 */
void push(LinkStack &linkStack,int value){

    LNode * newNode = (LNode *)malloc(sizeof(LNode)); //创建新结点
    newNode->data = value;   //给新节点赋值
    newNode->next = linkStack->next;//指针域
    linkStack->next = newNode;    //新节点进栈

}

/**
 * 出栈操作(在头结点进行出栈)
 */
bool pop(LinkStack &linkStack){

    LNode * delNode;
    delNode = linkStack->next;  //要出栈的结点

    if(linkStackIsEmpty(linkStack)){
        return false;  //栈空
    }

    linkStack->next = delNode->next; //头结点的指针域指向删除结点的后一位
    free(delNode);

    return true;
}

/**
 * 获取栈顶元素
 */
int getTop(LinkStack linkStack){
    if(linkStackIsEmpty(linkStack)){
        return -1; //栈空，返回-1
    }
    return linkStack->next->data;
}

/**
 * 创建一个完整的栈
 * @return
 */
void creatLinkStack(LinkStack &linkStack){
    int x;
    scanf("%d",&x);
    while(x != 9999){
        push(linkStack,x);
        scanf("%d",&x);
    }
}

/**
 * 打印
 * @return
 */
void printStack(LinkStack linkStack){

    while(linkStack != NULL){
        printf("栈里的值(包含头结点)- %d \n",linkStack->data);
        linkStack= linkStack->next;

    }
}

int main(){
    LinkStack linkStack;
    LNode *top;

    printf("---------初始化--------- \n");
    top = initStack(linkStack);
    printf("初始化栈顶指针值(头结点)： %d \n",top->data);

    printf("---------进栈(创建一个完整栈)---------\n");
    creatLinkStack(linkStack);
    printf("---------打印---------\n");
    printStack(linkStack);

    printf("---------获取栈顶元素---------\n");
    int top1 = getTop(linkStack);
    printf("栈顶元素: %d\n",top1);

    printf("---------出栈---------\n");
    pop(linkStack);
    printStack(linkStack);

    printf("---------获取栈顶元素---------\n");
    int top2 = getTop(linkStack);
    printf("栈顶元素: %d\n",top2);

    return 0;
}

测试结果

---------初始化---------
初始化栈顶指针值(头结点)： -1
---------进栈(创建一个完整栈)---------
3
4
2
5
6
9999
---------打印---------
栈里的值(包含头结点)- -1
栈里的值(包含头结点)- 6
栈里的值(包含头结点)- 5
栈里的值(包含头结点)- 2
栈里的值(包含头结点)- 4
栈里的值(包含头结点)- 3
---------获取栈顶元素---------
栈顶元素: 6
---------出栈---------
栈里的值(包含头结点)- -1
栈里的值(包含头结点)- 5
栈里的值(包含头结点)- 2
栈里的值(包含头结点)- 4
栈里的值(包含头结点)- 3

顺序存储栈基本操作：

https://blog.csdn.net/qq_35963993/article/details/106025787

.