栈和队列

栈

一种特殊的线性表，只允许固定的一端进行删除和插入数据操作。

1. 包括两个部分：

• 栈顶-进行数据的插入和删除操作

• 栈底-不做操作

2. 原则：**先进后出，后进先出****，**类似于弹夹

3. 两个基础操作：

• 入栈：栈的插入操作，也叫压栈/进栈**，入数据在栈顶**

• 出栈：栈的删除操作，出数据在栈顶

如图所示：

数组栈的实现

template<class T>
class Stack {
private:
    int size;
    int capacity;
    T *arr;

    void checkSpace();

public:
    Stack() : size(0), capacity(0) {
        arr = new T[5];
    }

    ~Stack() {
        size = 0;
        capacity = 0;
        arr = nullptr;
    }

    void push(T t);

    void pop();

    int getSize() {
        return size;
    }

    T top() {
        return arr[size - 1];
    }

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

template<class T>
void Stack<T>::checkSpace() {
    if (size > capacity) {
        // 扩容
        capacity *= 2;
        arr = (T *) realloc(arr, sizeof(T) * capacity);
    }
}

template<class T>
void Stack<T>::push(T t) {
    checkSpace();
    arr[size] = t;
    size++;
}

template<class T>
void Stack<T>::pop() {
    if (size > 0)
        size--;
}

void testStack() {
    Stack<int> stack;
    stack.push(100);
    stack.push(23);

    cout << stack.top();
    cout << endl;
    cout << stack.getSize();

}

队列

一种特殊的线性表，只允许在一端插入数据操作，另一端删除数据操作。

1. 原则：先进先出，后进后出，类似于排队

2. 两个基本操作：

• 入队列：进行插入数据操作，在队尾的一端

• 出队列：进行删除数据操作，在队头的一端

链式队列的实现

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"

void QueueInit(Queue* pq)
{
        assert(pq);
        pq->head = NULL;
        pq->tail = NULL;
}

void QueuePush(Queue* pq, Queuedatetype x)
{
        assert(pq);
        QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
        newnode->date = x;
        newnode->next = NULL;
        //head/tail为空
        if (pq->head == NULL)
        {
                pq->head = pq->tail = newnode;
        }
        //不为空
        else
        {
                pq->tail->next = newnode;
                pq->tail = newnode;
        }
}

void QueuePop(Queue* pq)
{
        assert(pq);
        assert(!QueueEmpty(pq));

        QueueNode* prev = pq->head->next;
        free(pq->head);
        pq->head = prev;
        if (pq->head == NULL)
        {
                pq->tail = NULL;
        }
}

Queuedatetype QueueFront(Queue* pq)
{
        assert(pq);
        assert(!QueueEmpty(pq));
        return pq->head->date;
}
Queuedatetype QueueBack(Queue* pq)
{
        assert(pq);
        assert(!QueueEmpty(pq));
        return pq->tail->date;
}

bool QueueEmpty(Queue* pq)
{
        assert(pq);
        return pq->head == NULL;
}

void QueueDestory(Queue* pq)
{
        assert(pq);
        QueueNode* cur = pq->head;
        while (cur != NULL)
        {
                QueueNode* next = cur->next;
                free(cur);
                cur = next;
        }
        pq->head = pq->tail = NULL;
}

循环队列的实现

class CircularQueue {
private:
    int *arr;
    int front;
    int rear;
    int capacity;   // max_size

public:
    CircularQueue() : front(0), rear(0), capacity(5) {
        arr = new int[5];
    }

    // 判断队空
    bool empty() {
        return front == rear;
    }

    // 判断队满
    bool full() {
        return (rear + 1) % capacity == front;
    }

    void push(int t) {
        if (full() || rear != 0) {
            cout << "队列已满,不能入队~" << endl;
            return;
        }
        arr[rear] = t;
        rear = (rear + 1) % capacity;
    }

    int pop() {
        if (empty()) {
            cout << "队列已空,不能出队~" << endl;
            return 0;
        }
        int temp = arr[front];
        front = (front + 1) % capacity;
        return temp;
    }

    int getfront() {
        if (empty()) {
            cout << "队列已空,不能出队~" << endl;
            return 0;
        }
        return arr[front];
    }

    int getrear() {
        if (empty()) {
            cout << "队列已空,不能出队~" << endl;
            return 0;
        }
        return arr[rear];
    }

    int getsize() {
        return (rear - front + capacity) % capacity;
    }

};

栈和队列算法题

有效的括号

描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        unordered_map<char, char> parenthesesMap = {{')', '('}, {']', '['}, {'}', '{'}};
        
        for (char c : s) {
            if (parenthesesMap.count(c)) { // 如果是右括号
                if (st.empty() || st.top() != parenthesesMap[c]) 
                    return false;
                st.pop();
            } else { // 左括号直接入栈
                st.push(c);
            }
        }
        return st.empty();
    }
};

用队列实现栈

描述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。

• int pop() 移除并返回栈顶元素。

• int top() 返回栈顶元素。

• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

• 两个队列来实现：

class MyStack {
public:
    MyStack() {}

    void push(int x) {
        if (q1.empty()) {
            q1.push(x);
        } else {
            q2.push(x);
            while (!q1.empty()) {
                q2.push(q1.front());
                q1.pop();
            }
            queue<int> tempqueue;
            tempqueue = q2;
            q2 = q1;
            q1 = tempqueue;
        }
    }

    int pop() {
        int temp = q1.front();
        q1.pop();
        return temp;
    }

    int top() { return q1.front(); }

    bool empty() { return q1.empty(); }

private:
    queue<int> q1; // 主队列
    queue<int> q2; // 辅助队列
};

• 一个队列来实现：

class MyStack {
public:
    MyStack() {}

    void push(int x) {
        q.push(x);
        int n = q.size() - 1;
        for (int i = 0; i < n; i++) {
            int temp = q.front();
            q.pop();
            q.push(temp);
        }
    }

    int pop() {
        int temp = q.front();
        q.pop();
        return temp;
    }

    int top() { return q.front(); }

    bool empty() { return q.empty(); }

private:
    queue<int> q;
};

用栈实现队列

描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

class MyQueue {
public:
    MyQueue() {}

    void push(int x) { in.push(x); }

    int pop() {
        if (out.empty()) {
            while (!in.empty()) {
                int temp = in.top();
                in.pop();
                out.push(temp);
            }
        }
        int res = out.top();
        out.pop();
        return res;
    }

    int peek() {
        int res = pop();
        out.push(res);
        return res;
    }

    bool empty() { return in.empty() && out.empty(); }

private:
    stack<int> out; // 出栈
    stack<int> in;  // 入栈
};

字符串解码

描述：给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入

class Solution {
public:
    string decodeString(string s) {
        stack<int> numstk;
        stack<string> stringstk;
        int num = 0;
        string str = "";
        for (auto& c : s) {
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } else if (isalpha(c)) {
                str += c;
            } else if (c == '[') {
                numstk.push(num);
                num = 0;
                stringstk.push(str);
                str = "";
            } else if (c == ']') {
                int count = numstk.top();
                numstk.pop();
                string temp = str;
                count--;
                while (count--) {
                    str += temp;
                }
                str = stringstk.top() + str;
                stringstk.pop();
            }
        }
        return str;
    }
};

# from cen

---