顺序表实现队列

class Vector {
public:
    int *data;
    int size;

    Vector(int n) : size(n) {
        data = new int[n];
    }

    ~Vector() {
        delete[] data;
    }

    int seek(int pos) {
        if (pos < 0 || pos >= size) return -1;
        return data[pos];
    }

    bool insert(int pos, int val) {
        if (pos < 0 || pos >= size) return false;
        data[pos] = val;
        return true;
    }
};

class Queue {
private:
    Vector *data;
    int size;
    int head;
    int tail;
    int count;

public:
    Queue(int n) : size(n), head(0), tail(0), count(0) {
        data = new Vector(n);
    }

    ~Queue() {
        delete data;
    }

    bool empty() {
        return count == 0;
    }

    int front() {
        return data->seek(head);
    }

    bool push(int val) {
        if (count == size) return false;
        data->insert(tail, val);
        tail += 1;
        if (tail == size) tail = 0;
        count += 1;
        return true;
    }

    bool pop() {
        if (empty()) return false;
        head += 1;
        if (head == size) head = 0;
        count -= 1;
        return true;
    }

    void clear() {
        delete data;
        data = new Vector(size);
        head = tail = count = 0;
    }

    void output() {
        std::cout << "Queue : ";
        for (int i = 0; i < count; i++) {
            std::cout << data->seek((head + i) % size) << " ";
        }
        std::cout << std::endl;
    }
};

链表实现队列

class Node {
public:
    int data;
    Node *next;

    Node(int val) : data(val), next(nullptr) {}
};

class LinkList {
public:
    Node head;
    Node *tail;

    LinkList() : head(0), tail(&head) {}

    bool empty() {
        return head.next == nullptr;
    }

    int front() {
        if (empty()) return 0;
        return head.next->data;
    }

    bool insertTail(int val) {
        Node *node = new Node(val);
        tail->next = node;
        tail = node;
        return true;
    }

    bool eraseHead() {
        if (empty()) return false;
        Node *p = head.next;
        head.next = head.next->next;
        if (p == tail) tail = &head;
        delete p;
        return true;
    }

    void clear() {
        Node *p = head.next, *q;
        while (p) {
            q = p->next;
            delete p;
            p = q;
        }
        head.next = nullptr;
        tail = &head;
    }

    ~LinkList() {
        clear();
    }
};

class Queue {
private:
    LinkList *l;
    int count;

public:
    Queue() : l(new LinkList()), count(0) {}

    ~Queue() {
        delete l;
    }

    bool empty() {
        return count == 0;
    }

    int front() {
        if (empty()) return 0;
        return l->front();
    }

    bool push(int val) {
        l->insertTail(val);
        count++;
        return true;
    }

    bool pop() {
        if (empty()) return false;
        l->eraseHead();
        count--;
        return true;
    }

    void clear() {
        l->clear();
        count = 0;
    }

    void output() {
        std::cout << "Queue : ";
        Node *p = l->head.next;
        for (int i = 0; i < count; i++, p = p->next) {
            std::cout << p->data << " ";
        }
        std::cout << std::endl;
    }
};

栈

class Stack {
private:
    int *data;
    int size;
    int topIndex;

public:
    Stack(int n) : size(n), topIndex(-1) {
        data = new int[n];
    }

    ~Stack() {
        delete[] data;
    }

    bool empty() const {
        return topIndex == -1;
    }

    int top() const {
        if (empty()) return 0;
        return data[topIndex];
    }

    bool push(int val) {
        if (topIndex + 1 == size) return false;
        data[++topIndex] = val;
        return true;
    }

    bool pop() {
        if (empty()) return false;
        --topIndex;
        return true;
    }

    void clear() {
        topIndex = -1;
    }

    void output() const {
        std::cout << "Stack : ";
        for (int i = topIndex; i >= 0; --i) {
            std::cout << data[i] << " ";
        }
        std::cout << std::endl;
    }
};

Leetcode-20 有效的括号

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) return false; 
        stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') st.push(')');
            else if (s[i] == '{') st.push('}');
            else if (s[i] == '[') st.push(']');
            else if (st.empty()) return false;
            else if(s[i]!=st.top())return false;
            else st.pop();
        }
        return st.empty();
    }
};

HZOJ-595 程序调用关系

int main()
{
    int n;
    cin >> n;
    string s[n];
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }
    vector<string> st;
    string target;
    cin >> target;
    int flag = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == target)
        {
            st.push_back(s[i]);
            flag = 1;
            break;
        }
        else if (s[i] == "return")
            st.pop_back();
        else
            st.push_back(s[i]);
    }
    if (flag == 1)
    {
        for (int i = 0; i < st.size(); i++)
        {
            if (i)
                cout << "->";
            cout << st[i];
        }
        cout << endl;
    }
    return 0;
}

HZOJ-838 2020年数据结构41题

每次将最小数向后移动

int func(queue<int> que1, queue<int> que2, queue<int> que3)
{
    int min_distance = INT_MAX;

    while (!que1.empty() && !que2.empty() && !que3.empty())
    {
        int a = que1.front();
        int b = que2.front();
        int c = que3.front();

        int current_distance = abs(a - b) + abs(b - c) + abs(c - a);
        min_distance = min(min_distance, current_distance);

        int min_value = min_num(a, b, c);

        if (a == min_value)
        {
            que1.pop();
        }
        else if (b == min_value)
        {
            que2.pop();
        }
        else
        {
            que3.pop();
        }
    }

    return min_distance;
}

Leetcode-844 比较含退格的字符串

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        stack<char>s1,s2;
        for(int i=0;i<s.size();i++){
            if(s[i]=='#'){
                if(!s1.empty())s1.pop();
            }
            else s1.push(s[i]);
        }
        for(int i=0;i<t.size();i++){
            if(t[i]=='#'){
                if(!s2.empty())s2.pop();
            }
            else s2.push(t[i]);
        }
        return s1==s2;
    }
};

HZOJ-263 火车进栈

next_permutation 是 C++ 标准库中的一个函数，用于生成给定序列的下一个字典序排列。

bool isValid(int a[], int n)
{
    stack<int> s;
    int x = 1;
    for (int i = 0; i < n; i++)
    {
        if (s.empty() || s.top() < a[i])
        {
            while (x <= a[i])
            {
                s.push(x);
                x++;
            }
        }
        if (s.top() != a[i])
            return false;
        s.pop();
    }
    return true;
}
int main()
{
    int n,cnt=20;
    int a[25];
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        a[i] = i + 1;
    }
    do
    {
        if (isValid(a, n))
        {
            for (int i = 0; i < n; i++)
            {
                cout << a[i];
            }
            cout << endl;
                cnt--;
        }
    } while (next_permutation(a, a + n)&&cnt);
    return 0;
}

Leetcode-946 验证栈序列

与上一题类似

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>popped){
        int x=0;
        stack<int>s;
        for(int i=0;i<pushed.size();i++){
            if(s.empty()||s.top()!=popped[i]){
                while(x<pushed.size()&&pushed[x]!=popped[i]){
                    s.push(pushed[x]);
                    x++;
                }
                if(x==pushed.size())return false;
                s.push(pushed[x]);
                x++;
            }
            s.pop();
        }
        return true;
    }
};

Leetcode-622 设计循环队列

顺序表:

class MyCircularQueue {
public:
    int front;
    int back;
    int capacity;
    vector<int>s;
    MyCircularQueue(int k) {
        capacity=k+1;
        s=vector<int>(k+1);
        back=front=0;
    }

    bool enQueue(int value) {
        if(isFull())return false;
        s[back]=value;
        back++;
        back%=capacity;
        return true;
    }

    bool deQueue() {
        if(isEmpty())return false;
        front++;
        front%=capacity;
        return true;
    }

    int Front() {
        if(isEmpty())return -1;
        return s[front%capacity];
    }

    int Rear() {
        if(isEmpty())return -1;
        return s[(back-1+capacity)%capacity];
    }

    bool isEmpty() {
        return back==front;
    }

    bool isFull() {
        return ((back+1)%capacity)==front;
    }
};

链表:

struct Node {
    int data;
    Node *next;
};

class MyCircularQueue {
public:
    int size, count;
    Node *head, *tail;
    MyCircularQueue(int k) {
        head = new Node();
        tail = head;
        for (int i = 1; i < k; i++) {
            tail->next = new Node();
            tail = tail->next;
        }
        tail->next = head;
        size = k;
        count = 0;
        return ;
    }

    bool enQueue(int value) {
        if (isFull()) return false;
        tail = tail->next;
        tail->data = value;
        count += 1;
        return true;
    }

    bool deQueue() {
        if (isEmpty()) return false;
        head = head->next;
        count -= 1;
        return true;
    }

    int Front() {
        if (isEmpty()) return -1;
        return head->data;
    }

    int Rear() {
        if (isEmpty()) return -1;
        return tail->data;
    }

    bool isEmpty() {
        return count == 0;
    }

    bool isFull() {
        return count == size;
    }
};

HZOJ-265 括号画家

#define MAX_N 10000
char str[MAX_N + 5];
int match[MAX_N + 5] = {0};
stack<int> s;

int main() {
    cin >> (str + 1);
    for (int i = 1; str[i]; i++) {
        switch (str[i]) {
            case '(': 
            case '[': 
            case '{': s.push(i); break;
            case ')': {
                if (!s.empty() && str[s.top()] == '(') {
                    match[s.top()] = i;
                    match[i] = s.top(); // delete
                    s.pop();
                } else {
                    s.push(i);
                }
            } break;
            case ']': {
                if (!s.empty() && str[s.top()] == '[') {
                    match[s.top()] = i;
                    match[i] = s.top(); // delete
                    s.pop();
                } else {
                    s.push(i);
                }
            } break;
            case '}': {
                if (!s.empty() && str[s.top()] == '{') {
                    match[s.top()] = i;
                    match[i] = s.top(); // delete
                    s.pop();
                } else {
                    s.push(i);
                }
            } break;
        }
    }
    int temp_ans = 0, ans = 0, i = 1;
    while (str[i]) {
        if (match[i]) {
            temp_ans += (match[i] - i + 1);
            i = match[i] + 1;
        } else {
            i += 1;
            temp_ans = 0;
        }
        if (temp_ans > ans) ans = temp_ans;
    }
    cout << ans << endl;
    return 0;
}