首页 > 其他分享 >数据结构栈与队列学习以及刷题总结

数据结构栈与队列学习以及刷题总结

时间:2022-10-23 01:22:50浏览次数:81  
标签:Status return sqstack 队列 elemtype top base 数据结构 刷题

1.栈与队列基本内容

(1).栈:栈是一种线性结构,限定仅在表尾进行插入和删除操作的线性表。

通过学习栈的性质,我们可以将其形象的想成叠盘子,每一个元素压入栈时都会成为栈顶元素,删除时也是从栈顶删除,因此符合“先入后出,后入先出原则”,下面是栈基于c++的实现。

 

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

using namespace std;

#define stack_initsize 100

#define stackincrement 10

#define overflow -1

#define OK 1

#define error 0

typedef int elemtype;

typedef int Status;

typedef struct{

    elemtype *base;

    elemtype *top;

    int stacksize;

}sqstack;

Status initstack(sqstack &s);

Status gettop(sqstack &s,elemtype &e);

Status push(sqstack &s,elemtype e);

Status pop(sqstack &s,elemtype &e);

Status check(char *ch,sqstack &s,elemtype &e);

Status length(sqstack &s);

 

int main(){

    sqstack s; initstack(s);

    elemtype e; int n; cin>>n;

    for(int i=0;i<n;i++){

        cin>>e; push(s,e);

    }

    cout<<"the stack is:";

    for(int i=0;i<n;i++){

        cout<<*(s.base++)<<' ';

    }

    cout<<'\n'<<"the convertion number is:";

    convertion();

    fflush(stdin);

    cout<<'\n'<<"input:";

    sqstack s1; initstack(s1);elemtype e1;

    char str[100];

    gets(str);

    int a=check(str,s1,e1);

    if(a==1)

      cout<<"ok";

    else cout<<"false";

    fflush(stdin);

    char exp[100];

    int result;

    cout<<"Please Enter Expression:";

    gets(exp);  result=evaluateexpression(exp);

    cout<<'\n';cout<<exp<<result;

}

Status initstack(sqstack &s){

    s.base=(elemtype*)malloc(stack_initsize*sizeof(elemtype));

    if(!s.base) exit (overflow);

    s.top=s.base;

    s.stacksize=stack_initsize; return OK;

}

Status gettop(sqstack &s,elemtype &e){

    if(s.base==s.top) return error;

    e=*(s.top-1); return OK;

}

Status push(sqstack &s,elemtype e){

    if(s.top-s.base>=s.stacksize){

        s.base=(elemtype*)realloc(s.base,(s.stacksize+stackincrement)*sizeof(elemtype));

    s.top=s.base+s.stacksize;

    s.stacksize+=stackincrement;

    }

    *s.top++=e;

     return OK;

}

Status pop(sqstack &s,elemtype &e){

    if(s.top=s.base) return error;

    e=*--s.top;

    return OK;

}

Status length(sqstack &s){

    elemtype length=s.top-s.base;

    return 0;

}

Status stackempty(sqstack &s){

        if (s.base==s.top)

           return OK;

        else return error;

}

void create(sqstack *s){

    s->base=(elemtype *)malloc(stack_initsize*sizeof(elemtype));

     if(!s->base)

     {

        printf("Space allocation failed!\n");

        return;

     }

    s->top=s->base;

    s->stacksize=stack_initsize;

    return;

}

elemtype GetTop(sqstack *s) {

    if(s->base==s->top)

    {

        printf("Stack is empty!\n");

        printf("Unable to fetch top stack element!\n");

    }

    return *(s->top-1);

}

(1).leetcode-225:用队列实现栈 全ac代码如下:

class Mystack{
public:
queue<int>q;
Mystack(){}//初始化栈
void push(int x){
int len=q.size();
q.push(x);
for(int I=0;i<len;i++){
q.push(q.front());
q.pop();
}
}
int pop(){
int r=q.front();
q.pop();
return r;
}
int top(){
int r=q.front();
return r;
}
bool empty(){
return q.empty();
}
}

代码分析:当栈和队列放一起时,我们自然会想到如何相互转换。由于栈与队列是进入规则是反的,所以入栈和出栈是难题所在。而我们又想将队首元素成为栈顶,但是当我们将一个元素加入队列时,是处于队尾的,若想将它变成队首元素,所以想到我们先将新元素入队,再将新元素之前的元素依此重新入队,这样新元素的前后都是原来队列中的元素。此时再将新元素前面的元素依此出队。此时就可以实现加入队列的元素成为队首而不是队尾,与栈的性质对应,即新入栈的元素都是栈顶元素。

 

标签:Status,return,sqstack,队列,elemtype,top,base,数据结构,刷题
From: https://www.cnblogs.com/curtain-cpp/p/16817751.html

相关文章

  • 单调队列
    单调队列思想以寻找滑动窗口中的最小值为例维护一个最小值的队列,队头为最小值,将最新的数组元素加入队尾时,将队列中比最新的数组元素小的元素从尾部出队,这样我们就维......
  • #yyds干货盘点# 前端歌谣的刷题之路-第一百三十五题-定位-fixed-广告
     前言我是歌谣我有个兄弟巅峰的时候排名c站总榜19叫前端小歌谣曾经我花了三年的时间创作了他现在我要用五年的时间超越他今天又是接近兄弟的一天人生难免坎坷大不了......
  • #yyds干货盘点# 前端歌谣的刷题之路-第一百三十六题-display-flex
     前言我是歌谣我有个兄弟巅峰的时候排名c站总榜19叫前端小歌谣曾经我花了三年的时间创作了他现在我要用五年的时间超越他今天又是接近兄弟的一天人生难免坎坷大不了......
  • #yyds干货盘点# 前端歌谣的刷题之路-第一百三十七题-可伸缩属性
     前言我是歌谣我有个兄弟巅峰的时候排名c站总榜19叫前端小歌谣曾经我花了三年的时间创作了他现在我要用五年的时间超越他今天又是接近兄弟的一天人生难免坎坷大不了......
  • 数据结构:数组
    一、是什么数组是一种线性表结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。首先我们需要理解一下这句话,以便于我们更好地理解数组。1.1线性表线性表是n个具......
  • 数据结构_用数组实现环形队列
    思路分析:一、front就指向队列的第一个元素,也就是说,arr[front]就是队列的第一个元素 二、rear就是指向队列的最后一个元素的后一个位置,我们需要空出这个rear指向的空间(......
  • 13-13-消息队列设计实践课_ev
                                        ......
  • 数据结构与算法系列二之链表、哈希表及栈
    第四章链表21、删除倒数第k个节点题目:如果给定一个链表,请问如何删除链表中的倒数第k个节点?假设链表中节点的总数为n,那么1≤k≤n。要求只能遍历链表一次。例如,输入下图1......
  • 利用redis作为消息队列实现异步秒杀业务
    实现消费券秒杀的优化,在加入限时抢购的优惠券时,自动的将消费券的库存stock信息也加入到redis中(可设为抢购结束后过期)抢购之前在redis中进行库存是否充足(stock)、用户是否已......
  • 刷题 LeetCode 栈和队列2
    代码随想录LeetCode20. 有效的括号carl栈思路左括号入栈,右括号出栈,如果出栈时栈为空或不匹配,或者最终栈不为空则false细节LeetCode1047. 删除字符串中的所有......