数据结构——栈 二

点击打开在线编译器,边学边练

1. 栈的基本操作—出栈

如图:

1111.png

出栈(pop)操作,是在栈不为空的情况下(注意一定要进行判空操作),将栈顶的元素删除,同时top指针,next向下进行移动即可的操作。

其代码可以表示为:

//出栈 pop
Link_Stack *Pop_stack(Link_Stack *p)
{
    Node *temp;
    temp = p->top;
    if (p->top == NULL)
    {
        printf("错误:栈为空");
        return p;
    }
    else
    {
        p->top = p->top->next;
        free(temp);
        //delete temp;
        p->count--;
        return p;
    }
}


2. 栈的基本操作—遍历

栈的遍历相对而言比较复杂,由于栈的特殊性质,其只允许在一端进行操作,所以我们的遍历操作永远都是逆序的,其过程为,在栈不为空的情况下,一次从栈顶元素向下访问,直到指针指向空(即到栈尾)为结束。

其代码可以表示为:

//遍历栈:输出栈中所有元素
int show_stack(Link_Stack *p)
{
    Node *temp;
    temp = p->top;
    if (p->top == NULL)
    {
        printf("");
        printf("错误:栈为空");
        return 0;
    }
    while (temp != NULL)
    {
        printf("%d\t", temp->data);
        temp = temp->next;
    }
    printf("\n");
    return 0;
}

3. 快速栈实现--数组栈

数组栈是一种更为快速的模拟实现栈的方法,所谓模拟,就是不采用真实的链表设计,转而采用数组的方式进行“模拟操作”,这是一种仿真类型的操作,其可以快速的帮助我们构建代码,分析过程,相应的实现起来也更加的便捷。

其代码如下(请参考上文进行自主分析):

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 10000
 
//结点设计
typedef struct stack{
    int data[maxn];
    int top;
}stack;
 
//创建
stack *init(){
    stack *s=(stack *)malloc(sizeof(stack));
    if(s==NULL){
        printf("分配内存空间失败");
        exit(0);
    }
    memset(s->data,0,sizeof(s->data));
    //memset操作来自于库文件string.h,其表示将整个空间进行初始化
    //不理解可以查阅百度百科https://baike.baidu.com/item/memset/4747579?fr=aladdin
    s->top=0;     //栈的top和bottom均为0(表示为空)
    return s;
}
 
//入栈push
void push(stack *s,int data){
    s->data[s->top]=data;
    s->top++;
}
 
//出栈pop
void pop(stack *s){
    if(s->top!=0){
        s->data[s->top]=0;  //让其回归0模拟表示未初始化即可
        s->top--;
    }
}
 
//模拟打印栈中元素
void print_stack(stack *s){
    for(int n=s->top-1;n>=0;n--){
        printf("%d\t",s->data[n]);
    }
    printf("\n");   //习惯性换行
}
 
int main(){
    stack *s=init();
    int input[5]={11,22,33,44,55};  //模拟五个输入数据
    for(int i=0;i<5;i++){
        push(s,input[i]);
    }
    print_stack(s);
    /////////////
    pop(s);
    print_stack(s);
    return 0;
}

 

4. 题目推荐

可以尝试的去利用栈的思维实现一下进制转换的题目

如十进制到八进制:1055题

十进制到二进制:1192题 

或者可以尝试一下利用递归栈的方式,将栈去代替函数递归实现一些功能(注意,这将会是DFS搜索算法的理解基础)

如斐波那契数列:1131题  


第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记