数据结构01-线性结构-链表栈队列-栈篇

简介: 数据结构01-线性结构-链表栈队列-栈篇


参考:


线性结构-栈


总结


本系列为C++数据结构系列,会介绍 线性结构,简单树,特殊树,简单图等。本文为线性结构部分。


大纲要求

线性结构

【 3 】链表:单链表、双向链表、循环链表

【 3 】栈

【 3 】队列


线性结构-栈


栈是Stack一个后进先出Last In First Out,LIFO的线性表,他要求只在表尾对数据执行删除和插入等操作。

栈就是一个线性表,可以是数组、也可以是链表。但它的操作有别于一般的线性表。栈的元素必须先进后出,也就是先进入栈的元素必须后出栈。而不能像一般的链表或数组那样从任意位置读取元素。

栈的操作只能在线性表的表尾进行,这个标为被称为栈的栈顶top,相应的表头被称为栈的栈底bottom


4aa40a9b898f590168672abd56b054c2_5b0eac387e634bb2a176a6991e7e502c.png

栈的数据必须从栈顶进入,也必须从栈顶取出,先入栈的数据在后入栈的数据下面。

栈中不含有任何数据时的状态叫作空栈,此时栈顶top等于栈底bottom。


回文匹配

#include <stdio.h>
#include <string.h>
int main ( )
{
    char a[ 101],s[101] ;
    int i, len, mid,next, top;
    gets(a) ; //读入一行字符串
    len=strlen(a) ; //求字符串的长度
    mid=len / 2-1; //l求字符串的中点
    top=0 ; //栈的初始化
//将mid前的字符依次入栈
    for(i=0 ; i<=mid; i++)
        s [++top]=a[ i] ;
//判断字符串的长度是奇数还是偶数,并找出需要进行字符匹配的起始下标
    if ( len%2==0 )
        next=mid+1;
    else
        next=mid+2;
//开始匹配
    for(i=next; i<=len-1; i++)
    {
        if(a[i]!=s[top])
            break;
        top--;
    }
    if(top==0)
        printf("yes");
    else
        printf("no");
    getchar();
    getchar();
    return 0;
}

4f01d1bafaf8eee4fe307d09511ce230_dbbcf8da06954cdf9c29c39875bf396c.png


小猫钓鱼的故事

#include <stdio.h>
struct queue
{
    int data[100];//100
    int head;
    int tail;
};
struct stack
{
    int data[10];
    int top;
};
int main ( )
{
    struct queue q1,q2;
    struct stack s;
    int book[10]= {0};
    int i,t;
    //初始化队列
    q1.head=1;
    q1.tail=1;
    q2.head=1;
    q2.tail=1;
    // 初始化栈
    s.top=0;
    //int q1_data[7]= {0,2,4,1,2,5,6};
    //初始化标记数组,标记哪些牌在桌上
    for(i=1; i<=6; i++)
    {
        scanf("%d",&q1.data[q1.tail]);
        //q1.data[q1.tail]=q1_data[i];
        q1.tail++;
    }
    //int q2_data[7]= {0,3,1,3,5,6,4};
    //初始化标记数组,标记哪些牌在桌上
    for(i=1; i<=6; i++)
    {
        scanf("%d",&q2.data[q2.tail]);
        //q2.data[q1.tail]=q2_data[i];
        q2.tail++;
    }
    //当队列不为空时执行循环
    while(q1.head<q1.tail &&
            q2.head<q2.tail)
    {
        t=q1.data[q1.head];//q1取出一张牌
        printf("q1---> t  %d , book[t]  %d \n",&t,&book[t]);
        // 判断q1当前打出的牌能否赢牌
        if(book[t]==0)//表明桌面上没有牌面为t的牌
        {
            // q1次轮没有赢牌
            q1.head++;//把q1打出的牌出列
            s.top++;
            s.data[s.top]=t;//把打出的牌t放在桌上,入栈
            book[t]=1;//标记桌上有牌面为t的牌
        }
        else
        {
            //q1可以赢牌
            q1.head++;
            q1.data[q1.tail]=t;//把刚打的牌放在手牌中的末尾 入队
            q1.tail++;
            //把桌上可以赢得的牌依次放入手中
            while(s.data[s.top]!=t)
            {
                book[s.data[s.top]]=0;//取消标记
                q1.data[q1.tail]=s.data[s.top];//依次放入队尾
                q1.tail++;
                s.top--; //栈中少了一张牌,栈顶减一
            }
        }
        //q2出一张牌
        t=q2.data[q2.head];
        printf("q2---> t  %d , book[t]  %d \n",&t,&book[t]);
        // 判断q2当前打出的牌能否赢牌
        if(book[t]==0)//表明桌面上没有牌面为t的牌
        {
            // q2次轮没有赢牌
            q2.head++;//把q1打出的牌出列
            s.top++;
            s.data[s.top]=t;//把打出的牌t放在桌上,入栈
            book[t]=1;//标记桌上有牌面为t的牌
        }
        else
        {
            //q2可以赢牌
            q2.head++;
            q2.data[q2.tail]=t;//把刚打的牌放在手牌中的末尾 入队
            q2.tail++;
            //把桌上可以赢得的牌依次放入手中
            while(s.data[s.top]!=t)
            {
                book[s.data[s.top]]=0;//取消标记
                q2.data[q2.tail]=s.data[s.top];//依次放入队尾
                q2.tail++;
                s.top--; //栈中少了一张牌,栈顶减一
            }
        }
    }
    if(q2.head ==q2.tail)
    {
        printf("q1赢win\n");
        printf("q1当前手中的牌是:");
        for(i=q1.head; i<=q1.tail-1; i++)
        {
            printf(" %d",q1.data[i]);
        }
        //如果桌面有牌,输出桌面的牌
        if(s.top>0)
        {
            printf("\n桌上的牌是");
            for(i=1; i<=s.top; i++)
            {
                printf(" %d",s.data[i]);
            }
        }
        else
        {
            printf("\n桌上没牌了");
        }
    }
    else
    {
        printf("q2赢win\n");
        printf("q2当前手中的牌是:");
        for(i=q2.head; i<=q2.tail-1; i++)
        {
            printf(" %d",q2.data[i]);
        }
        //如果桌面有牌,输出桌面的牌
        if(s.top>0)
        {
            printf("\n桌上的牌是");
            for(i=1; i<=s.top; i++)
            {
                printf(" %d",s.data[i]);
            }
        }
        else
        {
            printf("\n桌上没牌了");
        }
    }
    getchar();
    getchar();
    return 0;
}

15a78c0a13bc1e6b63781305e0ea05e3_068d114002054facbf3501241f7128e1.png

相关文章
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
137 9
|
25天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
24 1
|
12天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
30 5
|
28天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
67 16
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
50 4
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
6月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
6月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表