王道数据结构 第三章 栈和队列 编程题1

栈部分

1. 判断栈的操作序列是否合法（栈的初始状态和终止状态均为空）。若合法，返回true，反之返回false，操作序列存入一维数组中。I为入栈，O为出栈。

bool validate(const char *a) {
    int Icnt = 0, Ocnt = 0;
    int i = 0;
    while (a[i]!='\0') {
        if (a[i] == 'I') {
            Icnt++;
        }
        else if (a[i] == 'O') {
            Ocnt++;
        }
        if (Ocnt > Icnt) return 0;
        i++;
    }
    if (Icnt != Ocnt) return 0;
    else return 1;
}

2. 判断单链表的前n个数字是否中心对称。例如121，1221都是中心对称。

bool isSymetric(linkList l, int n) {
    stack<int> s;
    linkList p = l->pNext;
    for (int i = 0; i < n/2; i++) {
        s.push(p->data);
        p = p->pNext;
    }
    if (n % 2) p = p->pNext;
    while (p && s.top() == p->data && !s.empty() )
    {
        s.pop();
        if (s.empty()) break;
        p = p->pNext;
    }
    if (s.empty()) return true;
    else return false;
}

3. 设有两个栈都采用顺序栈方式，共享一个存储区，[0,maxsize - 1]，采用栈顶相向，迎面增长的存储方式，设计出栈和入栈等操作算法。（为了验证，把几乎所有操作都写了,貌似代码不够鲁棒，还希望大佬能看看哪里不太好。）

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int top1, top2;
}Stack;

void initStack(Stack &s) {
    s.top1 = -1;
    s.top2 = MAXSIZE;
}

bool isEmpty(int i,Stack& s) {
    if(i == 0 && s.top1 == -1) return true;
    else if (i == 1 && s.top2 == MAXSIZE) return true;
    else return false;
}
int top(int i, Stack& s) {
    if (isEmpty(i, s)) {
        cout << "栈为空" << endl;
        return 0;
    }
    if (i == 0) 
        return s.data[s.top1];
    else if(i==1)
        return s.data[s.top2];
}

void pop(int i, Stack& s) {
    if (isEmpty(i, s)) {
        cout << "栈为空，无法弹出" << endl;
        return;
    }
    if (i == 0) {
        cout << "弹出值为" << s.data[s.top1] << endl;
        s.top1--;
    }
    else {
        cout << "弹出值为" << s.data[s.top2] << endl;
        s.top2++;
    }
}

void push(Stack &s, int i, int x) {
    if (i != 0 && i != 1) {
        cout << "栈号输入错误" << endl;
    }
    if (s.top2 - s.top1 == 1) {
        cout << "栈已满" << endl;
        return;
    }
    if (i == 0) {
        s.data[++s.top1] = x;
        return;
    }
    else {
        s.data[--s.top2] = x;
        return;
    }
}

队列部分

1. 自己实现一个循环队列，支持队尾的push 和 pop，队头的push和pop。（双端队列）

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define MAXSIZE 3
typedef struct {
    int data[MAXSIZE];
    int front, rear;
}queue;//做成循环队列那是相当好的   队空条件 front = rear  队满 （rear+1） % maxsize = front


void initQueue(queue &q) {
    q.rear = q.front = 0;
}

bool isEmpty(queue &q) {
    if (q.rear == q.front) return true;
    return false;
}

void push_front(queue &q, int x) {
    if ((q.front - 1) % MAXSIZE == q.rear) {
        cout << "队列已满，不可加入" << endl;
        return;
    }
    q.data[q.front ] = x;
    q.front = (q.front - 1 + MAXSIZE) % MAXSIZE;
    cout << "加入元素 \"x=" << x << "\"成功！" << endl;
}

void push_back(queue &q, int x) {
    if ((q.rear + 1) % MAXSIZE == q.front) {
        cout << "队列已满，不可加入" << endl;
        return;
    }
    q.data[q.rear] = x;
    q.rear = (q.rear + 1) % MAXSIZE;
    cout << "加入元素 \"x=" << x << "\"成功！" << endl;
}

void pop_back(queue &q) {
    
    //cout << q.rear <<"     "<< q.front << endl;
    if (isEmpty(q)) {
        cout << "队列为空，不可弹出" << endl;
        return;
    }
    //cout << q.rear << "     " << q.front << endl;
    int x = q.data[q.rear-1];
    //cout << "debug1:" << q.rear << endl;
    q.rear = (q.rear - 1 + MAXSIZE) % MAXSIZE;
    //cout << "debug2:" << q.rear << endl;
    cout << "弹出元素为"<<x <<"!"<< endl;
}


void pop_front(queue &q) {
    if (isEmpty(q)) {
        cout << "队列为空，不可弹出" << endl;
        return;
    }
    int x = q.data[(q.front + 1 )%MAXSIZE];
    cout << "弹出元素为" << x << "!" << endl;
    q.front = (q.front + 1 ) % MAXSIZE;
}

int main() {
    ios::sync_with_stdio(false);
    queue q;
    initQueue(q);
    push_back(q, 10);
    push_back(q, 10);
    pop_back(q);
    pop_back(q);
    cout << "front"<<q.front << endl;
    cout << "rear" << q.rear << endl;

    push_front(q, 10);
//  cout << "front" << q.front << endl;
    //cout << "rear" << q.rear << endl;
    push_front(q, 2);
    pop_front(q);
    pop_front(q);
    system("pause");
    return 0;
}

2. 实现队列的链式存储结构

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef int elemType;
typedef struct node{
    int data;
    struct  node* next;
}LinkNode;
//设置为带头结点的单链表

typedef struct {
    LinkNode *front, *rear;
}queue;

void initQueue(queue &q) {
    q.front = (LinkNode*)malloc(sizeof(LinkNode));
    q.rear = q.front;
    q.front->next = nullptr;
}

bool isEmpty(queue q) {
    if (q.front == q.rear) return true;
    return false;
}
void enQueue(queue &q, elemType x) {
    LinkNode* temp = (LinkNode*)malloc(sizeof(LinkNode));
    temp->data = x;
    temp->next = nullptr;
    q.rear->next = temp;
    q.rear = temp;
}

elemType deQueue(queue &q) {
    if (isEmpty(q)) {
        cout << "队列为空" << endl;
        return 0;
    }
    LinkNode* temp = (LinkNode*)malloc(sizeof(LinkNode));
    
    temp = q.front->next;
    int x = temp->data;
    
    q.front ->next= temp->next;
    if (q.rear == temp) q.rear = q.front;
    free(temp);
    return x;
}

int main() {
    queue q;
    initQueue(q);
    enQueue(q, 10);
    enQueue(q, 9);
    enQueue(q, 11);
    enQueue(q, 12);
    cout << deQueue(q) << endl;
    cout << deQueue(q) << endl;
    cout << deQueue(q) << endl;
    cout << deQueue(q) << endl;
    system("pause");
    return 0;
}

最适合做链队的链表是：带队首指针和队尾指针的循环单链表
最不适合的：只带队首指针的非循环链表。
用链式存储方式的队列，进行存储操作时，头尾指针可能都要进行修改。

3. 利用一个栈，将队列中的元素逆置。

void reverseQueue(queue<int> &q) {
    stack<int> s;
    while (!q.empty()) {
        s.push(q.front());
        q.pop();
    }
    while (!s.empty()) {
        q.push(s.top());
        s.pop();
    }
}

4. 利用两个栈来模拟一个队列。

class Solution
{
public:
    void push(int node) {
        while (!stack2.empty())
        {
            stack1.push(stack2.top());
            stack2.pop();
        }
        stack1.push(node);
    }

    int pop() {
        while (!stack1.empty())
        {
            stack2.push(stack1.top());
            stack1.pop();
        }
        int result = stack2.top();
        stack2.pop();
        return result;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};