首页 > 代码库 > 栈的简单实现（2）-单链表实现

栈的简单实现（2）-单链表实现

2024-09-05 00:18:44   220人阅读

引言

    栈(stack)是一种被广泛使用的线性数据结构，它只允许在表的一端进行插入或删除操作，因而栈也可以被称作为操作受限的线性表 。在栈中，允许插入或删除的一端称作栈顶（top）不允许插入和删除的另一端称作栈底（bottom）;

示意图如下：

技术分享

 

此文借助单链表简单地实现栈及其基本操作。

代码如下：

技术分享 
typedef struct stack{
    int data;
    struct stack* next;
}ListStack;
View Code

  注：这里假设栈中储存的是整型 (int) 的数据

基本操作

1.栈的初始化

技术分享 
void  init(ListStack** top)
{
    *top = NULL;
}
View Code

2.进栈

技术分享 
void push(ListStack** top, int value)
{
    ListStack * newNode = (ListStack*)malloc(sizeof(ListStack));
    newNode->data =http://www.mamicode.com/ value;
    newNode->next = *top;
    *top = newNode;
}
View Code

3.出栈

技术分享 
int pop(ListStack** top)
{
    if(*top==NULL){
        return NULL;
    }else{
        ListStack* p = *top;
        int val = p->data;
        *top = (*top)->next;
        free(p);
        
        return val;
        
    }
}
View Code

4.判断栈是否为空

技术分享 
bool isEmpty(ListStack** top)
{
    if((*top)==NULL){
        return true; 
    }else{
        return false;
    }
    
}
View Code

5.清空栈

技术分享 
void clear(ListStack** top)
{
    if((*top)!=NULL){
        ListStack* pFree, * pExtra;
        pFree = *top;
        while(pFree!=NULL){
            pExtra = pFree;
            pFree = pFree->next;
            free(pExtra);
        }
        *top = NULL;
    }    
}
View Code

   进行测试 ：

技术分享 
int main(void)
{
    ListStack s;
    ListStack * top;
    init(&top);
    //入栈 
    push(&top, 3);
    push(&top, 2); 
    
    if(isEmpty(&top)){
        printf("栈为空\n");
    }else{
        printf("栈不为空\n");
    }
    //出栈 
    printf("%d\n", pop(&top));
    printf("%d\n", pop(&top));
    
    push(&top, 333);
    push(&top, 666);    
    clear(&top);
    if(isEmpty(&top)){
        printf("栈为空\n");
    }else{
        printf("栈不为空\n");
    }    
    return 0;
}
View Code

   测试结果：

技术分享

完整代码

技术分享 
#include<stdio.h>
#include<stdlib.h>

typedef struct stack{
    int data;
    struct stack* next;
}ListStack;

void init(ListStack** top);
void push(ListStack** top, int value);
int pop(ListStack** top);
bool isEmpty(ListStack** top);
void clear(ListStack** top);
int main(void)
{
    ListStack s;
    ListStack * top;
    init(&top);
    //入栈 
    push(&top, 3);
    push(&top, 2); 
    
    if(isEmpty(&top)){
        printf("栈为空\n");
    }else{
        printf("栈不为空\n");
    }
    //出栈 
    printf("%d\n", pop(&top));
    printf("%d\n", pop(&top));
    
    push(&top, 333);
    push(&top, 666);    
    clear(&top);
    if(isEmpty(&top)){
        printf("栈为空\n");
    }else{
        printf("栈不为空\n");
    }    
    return 0;
} 

void  init(ListStack** top)
{
    *top = NULL;
}

void push(ListStack** top, int value)
{
    ListStack * newNode = (ListStack*)malloc(sizeof(ListStack));
    newNode->data =http://www.mamicode.com/ value;
    newNode->next = *top;
    *top = newNode;
}

int pop(ListStack** top)
{
    if(*top==NULL){
        return NULL;
    }else{
        ListStack* p = *top;
        int val = p->data;
        *top = (*top)->next;
        free(p);
        
        return val;
        
    }
}
bool isEmpty(ListStack** top)
{
    if((*top)==NULL){
        return true; 
    }else{
        return false;
    }
    
}

void clear(ListStack** top)
{
    if((*top)!=NULL){
        ListStack* pFree, * pExtra;
        pFree = *top;
        while(pFree!=NULL){
            pExtra = pFree;
            pFree = pFree->next;
            free(pExtra);
        }
        *top = NULL;
    }    
}
View Code

 

栈的简单实现（2）-单链表实现


联系
我们