利用循环队列删除栈元素

我们先来抄书

所有函数，都是抄书，反正考试的时候也要复习，现在提前啃啃哦

第零步

链栈的 增 ， 删 ， 改 ，查 ，判空等

typedef struct Snode{
    int data;
    struct Snode *next;
}Snode , *LinkStack;
//初始化
bool InitStack(LinkStack &s){
    s = NULL;
    return true;
}
//判断是否为空
bool Empty(LinkStack s){
    if(s == NULL) return true;
    return false;
}
//入栈
bool Push(LinkStack &s , int e){
    LinkStack p = new Snode;
    p -> data = e;
    p -> next = s;
    s = p;
    return true;
}
//出栈
bool Pop(LinkStack &s , int &e){
    if(Empty(s)) return false;
    e = s->data;
    LinkStack p = s;
    s = s->next;
    delete p;
    return true;
}
//取栈顶元素
int GetTop(LinkStack s){
    if(Empty(s)) return false;
    return s->data;
}

表达式求值里已经写过了，一模一样，就不赘述

第一步

定义队列

typedef struct{
    int *base;
    int front;
    int rear;
}SqQueue;

第二步

判断队空

bool QEmpty(SqQueue q){
    if(q.front == q.rear) return true;
    return false ;
}

第三步

队列的初始化

//队列的初始化
int InitQueue(SqQueue &q){
    q.base = new int(Maxsize);
    if(!q.base) exit(OVERFLOW);
    q.front = q.rear = 0;
    return true;
}

第四步

判断队满

//判断队满
bool Full(SqQueue q){
    if((q.rear +1) % Maxsize == q.front) return true;
    return false;
}

第五步

入队

bool Enqueue(SqQueue &q , int e){
    if(Full(q)) return false;
    else{
        q.base[q.rear] = e;
        q.rear = (q.rear +1 )% Maxsize;
        return true;
    }
}

第六步

出队

bool Dequeue(SqQueue &q , int &e){
    if(QEmpty(q)) return false;
    e = q.base[q.front];
    q.front = (q.front + 1) % Maxsize;
    return true;
}

第七步

取队首元素

int GetHead(SqQueue q){
    if(QEmpty(q)) return false;
    return q.base[q.front];
}

开始写

第八步

思路，就先把栈的元素，放到队列里，然后准备一个中间栈，当队列中的元素和删除的元素值不相等时，就把元素，放进中间栈中，放完后，在从中间栈，按顺序再放到原栈里

main函数

int main()
{
    SqQueue q;                     //定义和初始化（栈还有队列的）
    InitQueue(q);
    LinkStack s , s1;
    InitStack(s);
    InitStack(s1);
    int n;                    //原来栈的元素个数
    cout<<"请输入栈元素个数"<<"\n";
    cin >> n;     
    int t;
    cout<< "请输入栈元素" <<"\n";
    for(int i = 0 ;i < n;i++){
        cin >> t;                //输入，栈中原来的元素，并放入栈中
        Push(s, t);
    }
    while(!Empty(s)){                // 当s不为空时，将s中的元素，一个个放进队列中
        int t1;
        Pop(s, t1);
        Enqueue(q, t1);
    }
    cout<<"请输入要删除的特定值"<<"\n";
    int t3;                    //要删除的特定值
    cin >> t3;
    while(!QEmpty(q)){            //当队列不为空的时候
        if(GetHead(q) != t3){        //当队头元素，和要删除的元素不相等的时候，把它放入中间栈中
            Push(s1, GetHead(q));
        }
        int e;
        Dequeue(q, e);            //一个个出栈的同时，放入，中间栈
    }
    while(!Empty(s1)){               // 当中间栈不为空的时候，将中间栈的元素，放回原栈
        Push(s, GetTop(s1));
        int c;
        Pop(s1, c);
    }
    s1 = s;
    while(s1){
        cout << s1->data <<" ";     // 输出原栈s中的元素
        s1 = s1 ->next;
    }
    cout << "\n";
}