一、栈
1.基本概念
栈是只能在一段进行插入或者删除的线性表
出栈进栈 只能在栈顶进行
三个术语：栈底，空栈，栈顶 字面理解即可
栈的基本操作：
创 销 增 删 查
2.顺序栈的实现
（1）初始化
#define max 10
typedef struct
{
int data[max];
int top; //记录数组下标
}sqstack;
//初始化
void inite(sqstack& s)
{
s.top = -1;
} 2.入栈
//入栈
bool push(sqstack& s, int x)
{
if (s.top == max - 1) //栈满 报错
return false;
s.top = s.top + 1; //指针加一
s.data[s.top] = x;
return true;
}3.出栈
//出栈
bool pop(sqstack& s, int& x)
{
if (s.top == -1)
return false;
x = s.data[s.top]; //栈顶元素先出栈
s.top = s.top - 1;
return true;
}4.读取栈顶元素
//读取栈顶元素
bool getpop(sqstack& s, int& x)
{
if (s.top == -1)
return false;
x = s.data[s.top];
return true;
}【数据结构】栈的链式实现和操作（创建栈，入栈，出栈，获取栈顶元素）_任务分析:链式栈的入栈操作先创建新结点node,再将新结点node指向栈顶指针,最-CSDN博客
stack<char> buffer;
buffer.empty() 看是否为空
buffer.push(s[i]）将s[i] 插入到栈顶
buffer.pop(); 删除栈顶元素
针对这题
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]" 输出：false
class Solution {
public:
bool isValid(string s) {
stack<char> buffer;
for (int i=0;i<s.size();i++)
{
if (buffer.empty())
{
buffer.push(s[i]);
continue;
}
char top=buffer.top();
if (s[i]=='}'&&top=='{')
{
buffer.pop();
continue;
}
else if (s[i]==']'&&top=='[')
{
buffer.pop();
continue;
}
else if (s[i]==')'&&top=='(')
{
buffer.pop();
continue;
}
buffer.push(s[i]);
}
return (buffer.empty());
}
};
二、队列
队列是前段插入，后端删除的线性表
看成一种循环线性表
判断元素个数：
(rear+max-front)%max
1.初始化
#define max 10
typedef struct
{
int data[max];
int front; int rear;
}sq;2.入队
//入队
bool enq(sq& q, int x)
{
if ((q.rear + 1) % max == q.front) //队列已满
return false;
q.data[q.rear] = x;
q.rear = (q.rear + 1)%max;
return true;
}3.出队
//出队
bool deq(sq& q, int &x)
{
if (q.rear=q.front) //队列为空
return false;
x = q.data[q.front];
q.front = (q.front + 1) % max; //队头指针向后移一位
return true;
}4.查
//查 获取队头元素的值
bool get(sq& q, int& x)
{
if (q.rear = q.front) //队列为空
return false;
x = q.data[q.front];
return true;
}
