【数据结构】栈与队列

一、栈

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 buffer;

buffer.empty()  看是否为空

buffer.push(s[i]）将s[i] 插入到栈顶

buffer.pop();  删除栈顶元素

针对这题

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

有效字符串需满足：

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

示例 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;
}