【数据结构】栈与队列
一、栈
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博客
s.empty(); //如果栈为空则返回true, 否则返回false;
s.size(); //返回栈中元素的个数
s.top(); //返回栈顶元素, 但不删除该元素
s.pop(); //弹出栈顶元素, 但不返回其值
s.push(); //将元素压入栈顶针对这题
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 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;
}