1.栈的相关知识
这是上篇关于栈的相关知识的续。
栈解决括号匹配问题：
class Solution { public: bool isValid(string s) { stack<char> cs; for(char ch:s) { if(ch == '(' || ch == '[' || ch == '{') { cs.push(ch); } else { if(cs.empty()) { return false; } char ctmp = cs.top(); cs.pop(); if(ch == ')' && ctmp != '(' || ch == ']' && ctmp != '[' || ch == '{' && ctmp != '}') { return false; } } } return cs.empty(); } };对于有栈对称结构的匹配问题思路都与此类似。
逆波兰表达式的求解：
class Solution { public: int solut(vector<string> &s) { stack<int> stack; for (string &str : s) { if (str == "+" || str == "-" || str == "*" || str == "/") { int right = stack.top(); stack.pop(); int left = stack.top(); stack.pop(); if (str == "+") { stack.push(left + right); } else if (str == "-") { stack.push(left - right); } else if (str == "*") { stack.push(left * right); } else { stack.push(left / right); } } else { stack.push(stoi(str)); } } return stack.top(); } };中缀表达式转为后缀表达式(逆波兰表达式)：
vector<string> InfixToPostfix(vector<string> &is) { vector<string> ps; stack<string> tmp; for (string &str : is) { // 遇到运算符 if (str == "+" || str == "-" || str == "*" || str == "/" || str == "(" || str == ")") { // 遇到左括号直接入栈 if (str == "(") { tmp.push(str); } // 遇到右括号，将栈中元素依次输出直到左括号 else if (str == ")") { while (tmp.top() != "(") { ps.push_back(tmp.top()); tmp.pop(); } tmp.pop(); } else { // 当栈为空或者栈顶元素是(时，运算符直接入栈 if (tmp.empty() || tmp.top() == "(") { tmp.push(str); } else { // 当栈不为空，当前运算符优先级比栈顶元素优先级大则入栈 if ((str == "*" || str == "/") && (tmp.top() == "+" || tmp.top() == "-")) { tmp.push(str); } // 当栈不为空，当前运算符优先级比栈顶元素优先级小或者相等则出栈输出, // 直到遇到空或者小括号停止，并将当前运算符入栈 else { while (!tmp.empty() && tmp.top() != "(") { ps.push_back(tmp.top()); tmp.pop(); } tmp.push(str); } } } } // 遇到数字直接输出 else { ps.push_back(str); } } while (!tmp.empty()) { ps.push_back(tmp.top()); tmp.pop(); } return ps; }2.队列的c++实现及相关知识
(1)底层由数组实现的队列
//数组实现的环形队列 class Queue { public: Queue(int size = 10) :front_(0) ,rear_(0) ,cap_(size) ,size_(0) { Que_ = new int[cap_]; } ~Queue() { delete Que_; Que_ = nullptr; } //入队 void push(int val) { if((rear_ + 1) % cap_ == front_) { expand(2*cap_); } Que_[rear_] = val; rear_ = (rear_ + 1) % cap_; size_ ++; } //出队 void pop() { if(rear_ == front_) { throw "queue is empty!"; } front_ = (front_ + 1 + cap_) % cap_; //对于队列，出队是对头出队 size_ --; } //获取队头元素 int front() { return Que_[front_]; } //获取队尾元素 int back() { return Que_[(rear_ - 1 + cap_) % cap_]; } //判空 bool empty() { return rear_== front_; } //获取队列有效元素个数 int size() { return size_; } private: int *Que_; int front_; int rear_; int cap_; int size_; void expand(int size) { int *p = new int[size]; int i = 0; int j = front_; for(;j != rear_;j = (j + 1 + cap_) % cap_) { p[i] = Que_[j]; i ++; } delete Que_; Que_ = p; front_ = 0; rear_ = i; cap_ = size; } };1.队列的出队是由对头进行出队。2.对由数组实现的循环队列在扩容时不能只是简单的内存拷贝。
(2)底层由双向循环链表实现的队列
// 双向循环链表实现队列 class LinkQueue { public: LinkQueue() : size_(0) { head_ = new Node(); head_->next_ = head_; //在双向循环链表的构造中，头节点的pre和next都要进行初始化 head_->pre_ = head_; } ~LinkQueue() { Node *p = head_->next_; while (p != head_) { head_->next_ = p->next_; p->next_->pre_ = head_; delete p; p = head_->next_; } delete head_; head_ = nullptr; } // 入队 void push(int val) { Node *node = new Node(val); Node *p = head_->pre_; p->next_ = node; node->pre_ = p; node->next_ = head_; head_->pre_ = node; size_ ++; } // 出队 void pop() { Node *p = head_->next_; head_->next_ = p->next_; p->next_->pre_ = head_; delete p; size_ --; } //获取对头元素 int front() { if(head_->next_ == head_) //注意括号里面的等于判断不要写成了赋值 { throw "queue is empty!"; } return head_->next_->data_; } //获取队尾元素 int back() { if (head_->next_ == head_) { throw "queue is empty!"; } return head_->pre_->data_; } //判空 bool empty() { return head_->next_ == head_; } //获取有效元素个数 int size() { return size_; } private: struct Node { Node(int data = 0) : data_(data), pre_(nullptr), next_(nullptr) { } int data_; Node *pre_; Node *next_; }; Node *head_; int size_; };1.在双向循环链表的构造函数中其头节点的pre和next都要指向头节点自己。2.注意括号里面的等于判断不能写成了赋值。
(2)队列的相关知识
特点：先进先出，后进后出
用两个栈来实现一个队列：
class Queue { public: //入队 void push(int val) { s1.push(val); } //出队 void pop() { if(s2.empty()) { while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } } s2.pop(); } //获取对头元素 int top() { if(s2.empty()) { while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } } return s2.top(); } //判空 bool empty() { return s1.empty() && s2.empty(); } private: stack<int> s1; stack<int> s2; };两个队列来实现一个栈：
class Stack { public: Stack() { p1 = new queue<int>; p2 = new queue<int>; } ~Stack() { delete p1; delete p2; p1 = nullptr; p2 = nullptr; } //入栈 void push(int val) { p1->push(val); if(!p2->empty()) { while(!p2->empty()) { p1->push(p2->front()); p2->pop(); } } queue<int> *p = p1; p1 = p2; p2 = p; } //出栈 void pop() { p2->pop(); } //获取栈顶元素 int top() { return p2->front(); } //判空 bool empty() { return p2->empty(); } private: queue<int> *p1; //p1用来指向新放入元素的队列 queue<int> *p2; //p2用来指向已经调整好的队列 };3.搜索
这里的搜索主要来看看对于有序数组的二分搜索的两种实现。
二分搜索的非递归实现：
int BinarySearch(int arr[],int size,int val) { int first = 0; int last = size-1; int mid = (first+last)/2; while(first <= last) { if(arr[mid] == val) { return mid; } else if(arr[mid] > val) { last = mid -1; mid = (first + last)/2; } else { first = mid + 1; mid = (first + last)/2; } } return -1; }二分搜索的递归实现：
int Binary_Search(int arr[],int i,int j,int val) { if(i > j) { return -1; } int mid = (i + j)/2; if(arr[mid] == val) { return mid; } else if(arr[mid] < val) { return Binary_Search(arr,mid+1,j,val); } else { return Binary_Search(arr,i,mid-1,val); } } int BinarySearch(int arr[],int size,int val) { return Binary_Search(arr,0,size-1,val); }4.排序
这里先记录的排序时冒泡排序：
void BubbleSort(int arr[], int size) { for (int i = 0; i < size-1; i++) { int flag = false; for (int j = 0; j < size - 1; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = true; } } if(!flag) { return; } } }