第二章栈和队列

第二章栈和队列

栈的基本操作

const int maxSize=100010;
//顺序栈
typedef struct{
    ElemType data[maxSize];//存放栈中元素
    int top;//存放栈顶指针
}SqStack;

/*
链式栈 入栈和出栈都在表头执行，相当于只处理表头一端的单链表
出栈：相当于删除链表的一个结点
入栈：相当于头插法插入结点
*/
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}*LiStack;
/*
共享栈：
利用栈底位置相对不变的特性，让两个顺序栈共享一个数组空间，将两个栈底设置在数组的两端，两个栈顶向中间延伸
*/

//顺序栈的初始化
void InitStack(SqStack &S){
    S.top=-1;
}
//判断栈是否为空
bool StackEmpty(SqStack S){
    if(S.top==-1)
        return true;
    else
        return false;
}
//进栈
bool Push(SqStack &S,int x){
    if(top==maxSize)
        return false;
    S.data[top++]=x;
    return true;
}

//出栈
bool Pop(SqStack &S,int &x){
    if(S.top==-1)
        return false;
    x=S.data[top--];
    return true;
}
//读栈顶元素赋值给x
bool GetTop(SqStack S,int &x){
    if(S.top==-1)
        return false;
    x=S.data[top];
    return true;
}

//链栈实现
//初始化
void InitStack(LiStack &L){
    L=(LiStack)malloc(sizeof(LiStack));
    L->next=NULL;
}
//判空
bool isEmpty(LiStack L){
    if(L->next==NULL){
        return true;
    }else
        return false;
}

//进栈
bool push(LiStack &x,int x){
    LNode *p;
    p=(LNode)malloc(sizeof(LNode));
    p->next==NULL;
    p->data=x;
    p->next=L->next;
    L->next=p;
}

//出栈
bool pop(LiStack &L,int &x){
    if(L->next==NULL)
        return false;
    LNode *p;
    p=L->next;
    x=p->data;
    L->next=p->next;
    free(p);
    return true;
}

判断单链表的数据是否中心对称

const int Maxn=1e3+7;
int fun(LinkList L,int n){
    char chStack[Maxn];
    int top=-1;
    LNode* p=L->next;
    for(int i=0;i<n/2;i++){
        chStack[++top]=p->data;
        p=p->next;
    }
    if(n%2==1)
        p=p->next;
    while(p!=NULL&&chStack[top--]==p->data){
        p=p->next;
    }
    if(p==NULL&&top==-1){
        return 1;
    }else{
        return 0;
    }
}

十进制n转k进制

const int Maxn=1e3+7;
void fun(int n){
    int ansStack[Maxn];
    int top=-1;
    while(n){
        ansStack[++top]=n%k;
        n/=k;
    }
    while(top!=-1){
        cout<<ansStack[top--];
    }
    
}

计算器

#include<iostream>
#include<stack>
using namespace std;
void fun(char str[],int n){
    stack<char> ch;
    stack<double> number;
    int i=0;
    while(i<n){
        if(str[i]>='0'&&str[i]<='9'){
            double tepNum=0;
            while(i<n&&str[i]!=' '){
                tepNum+=str[i]-'0';
                tepNum*=10;
                i++;
            }
            tepNum/=10;
            i++;
            if(ch.empty()==0&&(ch.top()=='/'||ch.top()=='*')){
                double x=number.top();
                number.pop();
                if(ch.top()=='/')
                    tepNum = (x*1.0)/tepNum;
                else
                    tepNum =x * tepNum;
                ch.pop();
            }
            number.push(tepNum);
        }
        else{
            ch.push(str[i]);
            i+=2;
        }
    }
    double sum=0;
    while(ch.empty()==0){
        if(ch.top()=='+')
            sum+=number.top();
        else
            sum-=number.top();
        number.pop();
        ch.pop();
    }
    sum+=number.top();
    printf("%.2lf",sum);
}
int main(){
    char str[18]={'4',' ','+',' ','2',' ','*',' ','5',' ','-',' ','7',' ','/',' ','1','1'};
    fun(str,18);
    return 0;
}

队列的基本操作

//顺序队列
typedef struct{
    ElemType data[maxSize];
    int front,rear;
}SqQueue;

//链式队列
typedef struct{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{
    LinkNode *front,*rear;
}LinkQueue;
//顺序队列的操作
//初始化
void InitQueue(SqQueue &Q){
    Q.front=Q.rear=0;
}
//判空
bool QueueEmpty(SqQueue Q){
    if(Q.rear==Q.front)
        return true;
    else
        return false;
}


//进队
bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%maxSize==Q.front)
        return false;
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%maxSize;
    return true;
}

//出队
bool DeQueue(SqQueue &q,ElemType &x){
    if(Q.rear==Q.front)
        return false;
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%maxSize
    return true;
}

//链式队列的操作
//初始化
void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkQueue)malloc(sizeof(LinkQueue));
}

//入队
bool EnQueue(LinkQueue &Q,int x){
    LNode *s=(LNode)malloc(sizeof(LNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}

//出队
bool Dequeue(LinkQueue &Q,int &x){
    LNode *s=Q.front->next;
    x=s->data;
    Q.front->next=s->next;
    if(Q.rear==p)
        Q.rear=Q.front;
    free(s);
    return true;
}

只有队尾指针出队和入队

//只有队尾指针出队和入队
bool DeQueue(LinkQueue &Q,int &x){
    if(Q.rear->next==Q.rear) return false;
    LNode *s=Q.rear->next->next;
    x=s->data;
    Q.rear->next->next=s->next;
    if(Q.rear==s)
    Q.rear=Q.rear->next;
    free(s);
    return true;
}
bool EnQueue(LinkQueue &Q,int x){
    LNode *s=(LinkQueue)malloc(sizeof(LinkQueue));
    s->data=x;
    s->next=NULL;
    s->next=Q.rear->next;
    Q.rear->next=s;
    Q.rear=s;
}

双端链表队尾删除队头插入

//队尾删除 队头插入
typedef struct{
    int data[maxSize];
    int front,rear;
}cycqueue
bool DeQueue(cycqueue &Q,int &x){
    if(Q.rear==Q.front)
        return false;
    x=Q.data[Q.rear];
    Q.rear=(Q.rear-1+maxSize)%maxSize;
    return true;
}

bool EnQueue(cycqueue &Q,int &x){
    if(Q.rear==(Q.front-1+maxSize)%maxSize)
        return false;
    Q.data[Q.front]=x;
    Q.front=(Q.front-1+maxSize)%maxSize;
    return true;
}

括号匹配

bool fun(char str[100],int n){
    char ch[maxSize];
    int top=-1;
    for(int i=0;i<n;i++){
        if(str[i]=='{'||str[i]=='['||str[i]=='(')
            ch[++top]=str[i];
        else if(top==-1||str[i]=='}'&&ch[top]!='{'||str[i]==']'&&ch[top]!='['||str[i]==')'&&ch[top]!='(')
        return 0;
        else
            top--;
    }
    if(top!=-1){
        return 0;
    }
    return 1;
}

括号价值求和

#include<iostream>
#include<cstring>
using namespace std;
const int Maxn=1e5+7;
char str[Maxn];
int ans;
int deep;
int main(){
    scanf("%s",str);
    int len=strlen(str);
    for(int i=0;i<len;i++){
        if(str[i]=='(')
            deep++;
        else{
            ans+=deep;
            deep--;
        }
    }
    cout<<ans<<endl;
    return 0;
}

对于输入序列 写出入栈或出栈

bool check(int n,char In[],char Out[]){
        int n=3;
        int i=0;//遍历Out
        int j=0;//遍历In
    stack<char> s;
    while(j<n){
        if(s.empty()||s.top()!=Out[i]){
            s.push(In[j]);
            j++;
        }
        else if(s.top()==Out[i]){
            s.pop();
            i++;
        }
    }
    if(i!=n-1)
        return 0;
    return 1;
}

两个栈实现队列并写出出队入队算法

int enQueue(SqStack &s1,SqStack &s2,int x){
    int y;
    if(s1.top()==maxSize-1){
        if(!isEmpty(s2))
            return 0;
        else{
            while(!isEmpty(s1)){
                pop(s1,y);
                push(s2,y);
            }
            push(s1,x);
        }
    }
    else
        push(s1,x);
}
int deQueue(SqStack &s1,SqStack &s2,int x){
    if(isEmpty(s1)||isEmpty(s2))
        return 0;
    int y;
    if(!isEmpty(s2))
        pop(s2,x);
    else{
        while(!isEmpty(s1)){
            pop(s1,y);
            push(s2,y);
        }
        pop(s2,x);
    }
    return 1;
}