链栈

借助单向链表，插入和删除操作若均在表头进行（头插和头删），则表尾为栈底；反之，若插入和删除操作均在表尾进行（尾插和尾删），则表头为栈底。

链栈的结构体声明

typedef struct stackLink{
    data_t data;
    struct stackLink* next;
}STACKLink,*StackLink;

链栈的操作

基本操作：创建、入栈（单端插入）、出栈（单端删除）、遍历（打印）等。

创建一个链栈

StackLink create()
{
    StackLink h = (StackLink)malloc(sizeof(STACKLink));
    h->next = NULL;
    memset(&(h->data),0,sizeof(data_t));
    return h;
}

创建一个数据结点

StackLink createNode(data_t val)
{
    StackLink node = (StackLink)malloc(sizeof(STACKLink));
    node->next = NULL;
    node->data = val;
    return node;
}

判空

int isEmpty(StackLink h)
{
    return h->next==NULL?1:0;
}

入栈（头插法插入）

void headInsert(StackLink h,data_t val)
{
    StackLink node = createNode(val);
    node->next = h->next;
    h->next = node;
}

出栈（头删法删除）

void headDelet(StackLink h)
{
    if(isEmpty(h))
    {
        printf("栈空\n");
        return;
    }
    StackLink temp = h->next;
    h->next = temp->next;
    printf("出栈：%d\n",temp->data);
    free(temp);
}

入栈（尾插法插入）

void tailInsert(StackLink h,data_t val)
{
    StackLink node = createNode(val);
    StackLink temp = h;
    while(temp->next!=NULL)
    {
        temp = temp->next;
    }
    temp->next = node;
}

出栈（尾删法删除）

void tailDelet(StackLink h)
{
    if(isEmpty(h))
    {
        printf("栈空\n");
        return;
    }
    StackLink temp = h;
    StackLink tail = temp->next;
    while(tail->next!=NULL)
    {
        temp = temp->next;
        tail = tail->next;
    }
    temp->next = NULL;
    printf("出栈：%d\n",tail->data);
    free(tail);
}

遍历（打印）

void printStack(StackLink h)
{
    StackLink temp = h;
    while(temp->next!=NULL)
    {
        printf("%d ",temp->next->data);
        temp = temp->next;
    }
    putchar(10);
}

示例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int data_t;
typedef struct stackLink{
    data_t data;
    struct stackLink* next;
}STACKLink,*StackLink;

StackLink create();
StackLink createNode(data_t val);
void printStack(StackLink h);
int isEmpty(StackLink h);
void headInsert(StackLink h,data_t val);
void headDelet(StackLink h);
void tailInsert(StackLink h,data_t val);
void tailDelet(StackLink h);
int main(int argc, const char *argv[])
{
    printf("头节点为栈顶：");
    StackLink hh = create();
    headInsert(hh,1);
    headInsert(hh,2);
    headInsert(hh,3);
    headInsert(hh,4);
    headInsert(hh,5);
    printStack(hh);
    headDelet(hh);
    printStack(hh);

    printf("头节点为栈底：");
    StackLink ht = create();
    tailInsert(ht,1);
    tailInsert(ht,2);
    tailInsert(ht,3);
    tailInsert(ht,4);
    tailInsert(ht,5);
    printStack(ht);
    tailDelet(ht);
    printStack(ht);

    return 0;
}
//创建一个链式栈
StackLink create()
{
    StackLink h = (StackLink)malloc(sizeof(STACKLink));
    h->next = NULL;
    memset(&(h->data),0,sizeof(data_t));
    return h;
}
//创建一个数据节点
StackLink createNode(data_t val)
{
    StackLink node = (StackLink)malloc(sizeof(STACKLink));
    node->next = NULL;
    node->data = val;
    return node;
}
//判空
int isEmpty(StackLink h)
{
    return h->next==NULL?1:0;
}
//尾插法插入 （入栈）
void tailInsert(StackLink h,data_t val)
{
    StackLink node = createNode(val);
    StackLink temp = h;
    while(temp->next!=NULL)
    {
        temp = temp->next;
    }
    temp->next = node;
}
//头部删除（出栈）
void headDelet(StackLink h)
{
    if(isEmpty(h))
    {
        printf("栈空\n");
        return;
    }
    StackLink temp = h->next;
    h->next = temp->next;
    printf("出栈：%d\n",temp->data);
    free(temp);
}
//头插法插入（入栈）
void headInsert(StackLink h,data_t val)
{
    StackLink node = createNode(val);
    node->next = h->next;
    h->next = node;
}
//尾部删除（出栈）
void tailDelet(StackLink h)
{
    if(isEmpty(h))
    {
        printf("栈空\n");
        return;
    }
    StackLink temp = h;
    StackLink tail = temp->next;
    while(tail->next!=NULL)
    {
        temp = temp->next;
        tail = tail->next;
    }
    temp->next = NULL;
    printf("出栈：%d\n",tail->data);
    free(tail);
}
//遍历
void printStack(StackLink h)
{
    StackLink temp = h;
    while(temp->next!=NULL)
    {
        printf("%d ",temp->next->data);
        temp = temp->next;
    }
    putchar(10);
}

结果

头节点为栈顶：5 4 3 2 1 
出栈：5
4 3 2 1
头节点为栈底：1 2 3 4 5
出栈：5
1 2 3 4

本文链接：https://shengto.top/data_structure/156.html

转载时须注明出处及本声明

Last modification：2021 年 03 月 26 日 10 : 16 : 00
© 允许规范转载