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

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


参考:

线性结构-栈

总结

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

大纲要求

  1. 线性结构
    【 3 】链表:单链表、双向链表、循环链表
    【 3 】栈
    【 3 】队列

线性结构-栈

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

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

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

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

栈中不含有任何数据时的状态叫作空栈,此时栈顶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;
}

小猫钓鱼的故事

#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;
}

目录
打赏
0
0
0
0
13
分享
相关文章
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
144 77
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
48 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
39 7
|
9月前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
76 2
|
9月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
93 1