栈
栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照后进先出的原则来存储数据，也就是说，先插入的数据将被压入栈底，最后插入的数据在栈顶，读出数据时，从栈顶开始逐个读出。栈在汇编语言程序中，经常用于重要数据的现场保护。栈中没有数据时，称为空栈。入栈出栈原理图见图
栈的实现
栈的结构就像一个集装箱，越先放进去的东西越晚才能拿出来，所以，栈常应用于实现递归功能方面的场景，例如斐波那契数列。
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int nValue;
struct node *pNext;
}MyStack;
typedef struct node2
{
int nCount;
MyStack *pTop;
}Stack;
void s_Init(Stack **pStack)
{
*pStack = (Stack*)malloc(sizeof(Stack));
(*pStack)->nCount = 0;
(*pStack)->pTop = NULL;
}
void s_Push(Stack *pStack,int nNum)
{
if(pStack == NULL)
{
printf("栈不存在!\n");
return;
}
MyStack *pTemp = NULL;
pTemp = (MyStack*)malloc(sizeof(MyStack));
pTemp->nValue = nNum;
pTemp->pNext = pStack->pTop;
pStack->pTop = pTemp;
pStack->nCount++;
}
int s_Pop(Stack *pStack)
{
if(pStack == NULL || pStack->pTop == NULL)return -1;
MyStack *pDel = NULL;
int nNum;
pDel = pStack->pTop;
nNum = pDel->nValue;
pStack->pTop = pStack->pTop->pNext;
free(pDel);
pDel = NULL;
pStack->nCount--;
return nNum;
}
void s_Clear(Stack *pStack)
{
if(pStack == NULL)return;
while(pStack->nCount != 0)
{
s_Pop(pStack);
}
}
void s_Destroy(Stack **pStack)
{
s_Clear(*pStack);
free(*pStack);
*pStack = NULL;
}
MyStack *s_GetTop(Stack *pStack)
{
if(pStack == NULL)exit(1);
return pStack->pTop;
}
int s_GetCount(Stack *pStack)
{
if(pStack == NULL)exit(1);
return pStack->nCount;
}
int s_IsEmpty(Stack *pStack)
{
if(pStack == NULL)exit(1);
return pStack->nCount == 0?1:0;
}
int main()
{
Stack *pStack = NULL;
s_Init(&pStack);
s_Push(pStack,1);
s_Push(pStack,2);
s_Push(pStack,3);
s_Push(pStack,4);
printf("%d\n",s_Pop(pStack));
printf("%d\n",s_Pop(pStack));
printf("%d\n",s_Pop(pStack));
printf("%d\n",s_Pop(pStack));
s_Destroy(&pStack);
s_Push(pStack,4);
return 0;
}
有效的括号
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: “()”
输出: true
示例 2:
输入: “()[]{}”
输出: true
bool isValid(char * s){
if (s == NULL || s[0] == '\0') return true; //差错检验
char *stack = (char*)malloc(strlen(s)+1); //申请一个数组 模拟栈
int top =0; //模拟栈顶指针
for (int i = 0; s[i]; ++i) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{')
stack[top++] = s[i]; //如果是左边的括号 就入栈
else { //不是的话 就做对比
if ((--top) < 0) //栈中没有元素了
return false;//先减减，让top指向栈顶元素
//不匹配 就返回false
if (s[i] == ')' && stack[top] != '(') return false;
if (s[i] == ']' && stack[top] != '[') return false;
if (s[i] == '}' && stack[top] != '{') return false;
}
}//正常top最终 = 0 否则就是还有没匹配
return (!top);//防止“【”这种类似情况
}
最长有效括号
给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”
“()(())” 输出：6
int longestValidParentheses(string s)
{
stack<char> vec; //用来放左括号或者未匹配的右括号
stack<int> num; //存放左括号的下标
vector<int> pos; //存放成对括号 的两个下标
int maxlen=0; //最终返回值
int len=0;
if(s.size()<=1) return 0; //差错检验
for(int i=0;i<s.size();i++)
{
if(!vec.empty()) //栈中有值 即有未匹配的左括号
{
if(vec.top()=='('&&s[i]==')') //是匹配的()
{
pos.push_back(num.top()); //讲左右括号的下标存入pos容器
pos.push_back(i);
//cout<<num.top()<<endl;
//cout<<i<<endl;
vec.pop(); //已匹配的左括号出栈
num.pop(); //已匹配的左括号的下标出栈
}
else //和栈顶元素不匹配
{
num.push(i); //将元素下标入栈
vec.push(s[i]); //将元素入栈
}
}
else //栈中没有元素 就将元素和元素下标入栈
{
num.push(i);
vec.push(s[i]);
}
}
sort(pos.begin(),pos.end()); //将成对的括号下标排序
for(int i=0;i<pos.size();i++)
{
// cout<<pos[i]<<endl;
if(i!=0&&pos[i]-pos[i-1]==1) //相邻下标都有标记
{
len=len+1;
maxlen=max(len,maxlen);
}
else //若有间隔 就直接将长度归1
{
len=1;
}
}
return maxlen;
}
};
方法2：
class Solution {
public:
int longestValidParentheses(string s) {
int size = s.size();
// 一个默认为-1的用于标记的数组
vector<int> m(size, -1);
// 从 1 开始 向右 遍历每个字符。
for (int i = 1; i < size; i++) {
// 跳过左括号
if (s[i] == '(') { continue; }
// 向前遍历，跳过 已经成对 括号【标记为 0 或者 2】的位置
// 找到 标记为 -1 且 字符为 左括号的地方，将左括号标记为0，右括号标记为2
for (int j = i - 1; j >= 0; j--) {
if (m[j] < 0 && s[j] == '(') {
m[j] = 0; m[i] = 2;
break;
}
}
}
// max为返回值， tmp记录当前匹配括号总和
int max = 0, tmp = 0;
// 获取连续的 0,2标记总和，并随时更新到max，如果被-1标记打断，则tmp重新开始计算新长度。
for (auto i : m)
{
if (i >= 0)
{
tmp += i;
}
else
{
tmp = 0;
}
max = (tmp > max) ? tmp : max;
}
return max;
}
二叉树的递归遍历
#include <iostream>
using namespace std;
typedef int TreeEntry;
struct TreeNode
{
TreeEntry val;
TreeNode* pleft;
TreeNode* pright;
};
//二叉树的递归遍历
//前序
void PreOrderTraverse(TreeNode* root)
{
if(root == NULL)
return;
//根
cout<<root->val<<endl;
//左
PreOrderTraverse(root->pleft);
//右
PreOrderTraverse(root->pright);
return;
}
//中序
void InOrderTraverse(TreeNode* root)
{
if(root == NULL)
return;
//左
InOrderTraverse(root->pleft);
//根
cout<<root->val<<endl;
//右
InOrderTraverse(root->pright);
return;
}
//后序
void LstOrderTraverse(TreeNode* root)
{
if(root == NULL)
return;
//左
LstOrderTraverse(root->pleft);
//右
LstOrderTraverse(root->pright);
//根
cout<<root->val<<endl;
return;
}
int main(void)
{
TreeNode node1;
node1.val = 2;
node1.pleft = NULL;
node1.pright = NULL;
TreeNode node2;
node2.val = 3;
node2.pleft = NULL;
node2.pright = NULL;
TreeNode root;
root.val = 1;
root.pleft = &node1;
root.pright = &node2;
cout<<"前序"<<endl;
PreOrderTraverse(&root);
cout<<"中序"<<endl;
InOrderTraverse(&root);
cout<<"后序"<<endl;
LstOrderTraverse(&root);
return 0;
};
非递归遍历
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
typedef int TreeEntry;
struct TreeNode
{
TreeEntry val;
TreeNode* pleft;
TreeNode* pright;
};
//二叉树的非递归遍历
//深度优先 前序
void DeepTravese(TreeNode * root)
{
if(root == NULL)
return;
stack<TreeNode> stk;
stk.push(*root);//根节点入栈
while(!stk.empty())
{
TreeNode node = stk.top();
stk.pop();
cout<<node.val<<endl;
if(node.pright != NULL) //右节点入栈
{
stk.push(*node.pright);
}
if(node.pleft != NULL) //左节点入栈
{
stk.push(*node.pleft);
}
}
}
int main(void)
{
TreeNode node1;
node1.val = 2;
node1.pleft = NULL;
node1.pright = NULL;
TreeNode node2;
node2.val = 3;
node2.pleft = NULL;
node2.pright = NULL;
TreeNode root;
root.val = 1;
root.pleft = &node1;
root.pright = &node2;
DeepTravese(&root);
LevelTravese(&root);
return 0;
};
队列和栈
队列：先进先出 栈：先进后出
两个队列实现一个栈
queue<int> que1;
queue<int> que2; // 1 2 3 4
void push(int x) { //向非空队列后面放
if(que1.empty())
{
que2.push(x);
}
else{
que1.push(x);
}
}
int pop() { //非空的队列把前n-1元素顺序放到空队列 再将最后一个元素出队返回
if(que1.empty())
{
while(que2.size() > 1){
que1.push(que2.front());
que2.pop();
}
int n = que2.front();
que2.pop();
return n;
}
else
{
while(que1.size() > 1){
que2.push(que1.front());
que1.pop();
}
int n = que1.front();
que1.pop();
return n;
}
}
两个栈实现一个队列
stack <int> stk1; //1 2 3 4
stack <int> stk2; //存倒序的
void push(int x) { //stk1中存的是正序的 所以在stk1入栈
while(!stk2.empty()) //如果stk2中有元素（都是倒叙的），都倒在stk1中，再push
{
stk1.push(stk2.top());
stk2.pop();
}
stk1.push(x);
}
int pop() { //返回的是第一个入栈的 stk1是1 2 3 4 所以要倒叙stk2
while(!stk1.empty())
{
stk2.push(stk1.top());
stk1.pop();
}
int n = stk2.top();
stk2.pop();
return n;
}
删除字符串中所有相邻重复项
案例如下：
输入：“abbaca”
输出：“ca”
string removeDuplicates(string S) {
if(S.empty())
return NULL;
stack<char> stk;
for(int i=0;i<S.length();i++){
if(stk.empty() || S[i]!=stk.top()) //空栈或者不匹配 入栈
{
stk.push(S[i]);
}
else //匹配就直接出栈 说明是相邻重复 重复的都出栈了 栈中都是不相邻重复的
stk.pop();
}
string s;
while(!stk.empty())
{
s+=stk.top();
stk.pop();
}
reverse(s.begin(),s.end()); //ac->ca
return s;
}
自定义栈
设计包含min 函数的栈。定义栈的数据结构，要求添加一个min 函数，
能够得到栈的最小元素。要求函数min、push 以及pop 的时间复杂度都是O(1)。
struct StackItem
{
int m_val;
int m_min; //存到某节点为止的最小值
};
class MyStack
{
public:
MyStack(int size);
~MyStack();
public:
StackItem* stack;
int m_top; //一直指向栈顶元素
public:
void push(int value);
int pop();
int min();
};
MyStack::MyStack(int size)
{
stack = new StackItem[size];
for(int i=0;i<size;i++)
{
stack[i].m_min = 2147483647;
}
m_top = 0;
}
MyStack::~MyStack()
{
delete[] stack;
stack = NULL;
}
void MyStack::push(int value)
{
m_top++;
stack[m_top].m_val = value;
if(m_top > 0)
{
if(value < stack[m_top-1].m_min)
stack[m_top].m_min = value;
else
{
stack[m_top].m_min = stack[m_top-1].m_min;
}
}
else
stack[m_top].m_min = value;
}
int MyStack::pop()
{
if(m_top == 0)
return 0;
return stack[m_top--].m_val;
}
int MyStack::min()
{
if(m_top == 0)
return 0;
return stack[m_top].m_min;
}