表、栈和队列
表、栈和队列
第1节 顺序表
顺序表存储结构
// 顺序表的存储结构
#define MAXSIZE 100
typedef int ElemType;
typedef struct
{
ElemType *elem;
int length;
}SqList;
// 顺序表的初始化
bool initSqList(SqList &L);
// 顺序表的按位查找
bool getElem(SqList L, int i, ElemType &e);
// 顺序表按值查找
int locateElem(SqList L, ElemType e);
// 向第i个位置插入元素e
bool insertElem(SqList &L, int i, ElemType e);
// 删除第i个位置的元素
bool deleteElem(SqList &L, int i);
顺序表算法实现
getElem和locateElem这两个函数的参数都是值传递，造成表L的拷贝，这种实现方式并不好。
#include"SqList.h"
bool initSqList(SqList &L)
{
L.elem = new ElemType[MAXSIZE];
if(!L.elem)
{
return false;
}
L.length = 0;
return true;
}
bool getElem(SqList L, int i, ElemType &e)
{
if(i<1 || i> L.length)
{
return false;
}
e = L.elem[i-1];
return true;
}
int locateElem(SqList L, ElemType e)
{
for(int i =0; i < L.length; i++)
{
if(L.elem[i] == e)
{
return i + 1;
}
}
return 0;
}
bool insertElem(SqList &L, int i, ElemType e)
{
if(i < 1 || i > L.length + 1)
{
return false;
}
if(L.length == MAXSIZE)
{
return false;
}
for( int j = L.length-1; j >= i-1; j--)
{
L.elem[j+1] = L.elem[j];
}
L.elem[i-1] = e;
L.length++;
return true;
}
bool deleteElem(SqList &L, int i)
{
if(i < 1 || i > L.length - 1)
{
return false;
}
for(int j = i-1; j<L.length;j++)
{
L.elem[j]=L.elem[j+1];
}
L.length--;
return true;
}
第2节 单链表
单链表的存储结构
// 单链表的存储结构
typedef struct LNode
{
int data; // 结点的数据域
struct LNode *next; // 结点的指针域
}LNode, *LinkList;
// 单链表的初始化
bool initList(LinkList &L);
// 查找单链表中的第i个元素
bool getElem(LinkList L,int i,int &e);
// 单链表按值查找
LNode *locateElem(LinkList L, int e);
// 单链表向第i个位置插入元素
bool insertElem(LinkList &L,int i,int e);
// 单链表删除第i个结点
bool deleteElem(LinkList &L,int i,int &e);
// 头插法创建单链表,插入n个元素
void createListFromHeader(LinkList &L,int n);
// 尾插法创建单链表，插入n个元素
void createListFromTail(LinkList &L,int n);
单链表算法实现
#include <iostream>
#include "LinkList.h"
bool initList(LinkList &L)
{
L=new LNode;
L->next=NULL;
return true;
}
bool getElem(LinkList L,int i,int &e)
{
LNode* p=L;
int j=0;
//从头结点开始，数到第j次，p指向的就是第j个结点
for(j=0;j<i&&p;j++)
{
p=p->next;
}
// 经过以上循环，j<i（未找到第i个结点，提前结束循环）或者j=i(找到第i个结点)
if(i==j)
{
e=p->data;
return true;
}
return false;
}
// 单链表按值查找
LNode *locateElem(LinkList L, int e)
{
LNode *p=L->next;
while(p&&p->data!=e)
{
p=p->next;
}
return p;
}
// 单链表向第i个位置插入元素
bool insertElem(LinkList &L,int i,int e)
{
//第1步，首先找到第i-1个结点
LNode *p=L;
int j=0;
for(j=0;j<i-1&&p;j++)
{
p=p->next;
}
// 经过以上循环，如果j=!i-1，说明没有找到第i-1个结点
if(j!=i-1)
{
return false;
}
// 第2步，生成新的结点并加入到链表中
LNode* s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
// 单链表删除第i个结点
bool deleteElem(LinkList &L,int i,int &e)
{
//第1步，首先找到第i-1个结点
LNode *p=L;
int j=0;
for(j=0;j<i-1&&p;j++)
{
p=p->next;
}
// 经过以上循环，如果j=!i-1，说明没有找到第i-1个结点
if(j!=i-1)
{
return false;
}
// 第2步，删掉第i个结点并释放空间，通过出参返回结点值
LNode *q=p->next;
p->next=p->next->next;
delete q;
return true;
}
// 头插法创建单链表,插入n个元素
void createListFromHeader(LinkList &L,int n)
{
// 第1步，先生成头结点
L=new LNode;
L->next=NULL;
// 第2步，插入元素
for(int i=0;i<n;i++)
{
LNode *p=new LNode;
std::cin>>p->data;
p->next=L->next;
L->next=p;
}
}
// 尾插法创建单链表，插入n个元素
void createListFromTail(LinkList &L,int n)
{
// 第1步，先生成头结点
L=new LNode;
L->next=NULL;
LNode *r=L; //r始终指向链表的尾结点
// 第2步，插入元素
for(int i=0;i<n;i++)
{
LNode *p=new LNode;
std::cin>>p->data;
p->next=NULL;
r->next=p;
r=p;
}
}
第3节 双向链表(未完成)
第4节 顺序栈
栈是一种特殊的线性表，也可以说是受到限制的线性表。它的特点就是只能在表尾进行插入或者删除。由于栈始终是在线性表的尾部进行操作，所以栈应该始终维护一个指针，让该指针指向栈的尾部。在这里设计的栈，其栈顶指针始终指向栈顶元素的上一个位置（或者说栈顶指针当前的指向的是个空位置）。我们思考为什么要这样实现呢？栈顶指针指向末尾元素就不行吗？我认为栈顶指针指向末尾元素是可行的。当栈顶指针指向末尾元素时，栈空的标志就是top小于base。栈的大小就是top-base+1;
栈的存储结构
#define MAXSIZE 100
typedef struct
{
int *base; // 栈底指针
int *top; // 栈顶指针
int stackSize; // 栈可用的最大容量
}SqStack;
// 初始化栈
bool initStack(SqStack &S);
// 入栈
bool push(SqStack &S,int e);
// 出栈
bool pop(SqStack &S,int &e);
// 取栈顶元素
bool getTopElem(SqStack S,int &e);
栈的算法实现
#include "SqStack.h"
// 初始化栈
bool initStack(SqStack &S)
{
S.base=new int[MAXSIZE];
if(!S.base)
{
return false;
}
S.top=S.base;
S.stackSize=MAXSIZE;
return true;
}
// 入栈
bool push(SqStack &S,int e)
{
if(S.top-S.base==S.stackSize)
{
return false;
}
*S.top++=e;
return true;
}
// 出栈
bool pop(SqStack &S,int &e)
{
if(S.top==S.base)
{
return false;
}
e=*--S.top;
}
// 取栈顶元素
bool getTopElem(SqStack S,int &e)
{
if(S.top==S.base)
{
return false;
}
e=*(S.top-1);
return true;
}
栈的应用
栈的应用一：括号匹配的检验
栈的应用二：表达式求值
栈的应用三：汉诺塔问题
栈的应用四：将递归算法转化为非递归算法
第6节 循环队列
队列也是一种特殊的线性表，也可以说是受到限制的线性表。它的特点是元素只能从线性表尾部插入，只能删除头部的元素。由于普通的顺序表从头部删除元素之后，后面的元素都要前移导致开销巨大。因此队列并不将顺序表的开头作为队列的首部，而是维护一个头指针指向队列的首部，这样删除队首元素就不用移动其它元素了，改变头指针即可。队列插入元素总是在顺序表的尾部，因此也需要维护一个尾指针指向队列的尾部。以上就是用顺序表实现队列设计成循环队列的原因。由于队空的判别条件是front==rear，而循环队列队满时也会有front==rear，两者产生冲突，解决冲突的办法就是少使用一个元素空间。
循环队列的存储结构
#define MAXSIZE 100
typedef struct
{
int *base; // 存储空间的基地址
int front; // 头指针
int rear; // 尾指针
}SqQueue;
// 队列初始化
bool initSqQueue(SqQueue &Q);
// 入队
bool enterQueue(SqQueue &Q,int e);
// 出队
bool deleteQueue(SqQueue &Q,int &e);
// 取队首元素
bool getHead(SqQueue Q,int &e);
循环队列的算法实现
#include "Queue.h"
// 队列初始化
bool initSqQueue(SqQueue &Q)
{
Q.base=new int[MAXSIZE];
Q.front=0;
Q.rear=0;
return true;
}
// 入队
bool enterQueue(SqQueue &Q,int e)
{
if((Q.rear+1)%MAXSIZE==Q.front)
{
return false;
}
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXSIZE;
return true;
}
// 出队
bool deleteQueue(SqQueue &Q,int &e)
{
if(Q.front==Q.rear)
{
return false;
}
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXSIZE;
return true;
}
// 取队首元素
bool getHead(SqQueue Q,int &e)
{
if(Q.front==Q.rear)
{
return false;
}
e=Q.base[Q.front];
return true;
}
第7节 单调队列
【滑动窗口最大值】给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
// 单调递减队列
// 只需要在窗口中抽离出一个单调递减队列，那么这个队列的首部就是窗口的最大值
// 当单调队列的首部元素小于窗口左边下标时，弹出单调队列的首部元素
// 这样就能保证单调队列始终是从窗口中抽离出来的
int n = nums.size();
deque<int> q;
// 单调队列的构造方法
for (int i = 0; i < k; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
}
vector<int> ans = {nums[q.front()]};
for (int i = k; i < n; ++i) {
// 维持一个单调队列
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
// i-k+1代表的是窗口左边
// 维护单调队列是在窗口的范围内
while (q.front() < i - k + 1 ) {
q.pop_front();
}
ans.push_back(nums[q.front()]);
}
return ans;
}
单调队列是一种添加新元素进队列的时候，需要弹出较小元素的队列，以此来维持队列的单调性。假设我们有一个数组，我们要将数组中的元素添加进单调队列中，过程如下：如果添加的元素大于队列中已有的元素，那么弹出所有小于该元素的元素，然后将该元素加入到队列中。
单调队列分为单调递减队列与单调递增队列。那么如何记忆这两个队列呢？假设我们想要的是单调递减队列，那么当新元素小于队列末尾元素时，就应该将新元素直接加入队列中。所以，如果想要先弹出队列中的元素，那么就对之前的条件取反，这样就知道循环条件是如何设置的了。
第8节 单调栈
单调栈分为单调递减栈与单调递增栈。那么如何记忆这两个栈呢？假设我们想要的是单调递减栈，那么当新元素小于栈顶元素时，就应该将新元素直接加入栈顶中。所以，如果想要先弹出栈中的元素，那么就对之前的条件取反，这样就知道循环条件是如何设置的了。
所有的单调栈归根结底、从本质上来说，就是找到某个数的左边或者右边第一个比它大或者小的数。
对于单调递增栈而言，我们很容易清楚栈顶元素的左边的最小值，而右边最小值就是让该栈顶元素出栈的那个元素。所以，可以知道，每次有元素出栈的时候，我们都应该记录它的左边最近最小值以及右边的最近最小值。
单调递增栈：每个元素都会经历入栈和出栈的过程。对于栈顶元素来说，左边的最近最小值就是自己出栈后的栈顶元素，右边的最近最小值就是让自己出栈的新元素。每个元素入栈时可知自己左边的最近最小值（入栈之前的栈顶元素），每个元素出栈时可知自己右边的最近最小值（让自己出栈时的元素）。最后剩余在栈中的元素，都是不存在右边最近最小值的元素。
题目一 单调栈
给定一个不含有重复值的数组arr，找到每一个i位置左边和右边离i位置最近且值比arr[i]小的位置，返回所有位置相应的信息。
vector<vector<int>> rightWay(vector<int> arr) {//int arr[] = {3, 4, 1, 5, 6, 2, 7};
int n = arr.size();
vector<vector<int>> res(n, vector<int>(2, -1));//创建一个二维数组并初始化（这也是我们最终将要返回的答案）
stack<int> stk;
for (int i = 0; i < n; i++) {
while (!stk.empty() && arr[stk.top()] >= arr[i]) {//倘若考虑有值相等的情况，则加上等号；
//如果不考虑值相等的情况，则可以不用加
int popIndex = stk.top(); //取出栈顶元素
stk.pop();
int LeftIndex = stk.empty() ? -1 : stk.top();//判断此时是否为空，如果为空，则定义为-1
res[popIndex][0] = LeftIndex; //下标赋值
res[popIndex][1] = i;
}
stk.push(i); //将此时的下标压入栈中
}
while (!stk.empty()) {
int popIndex = stk.top(); //清算栈中剩余的元素
stk.pop();
int leftIndex = stk.empty() ? -1 : stk.top();
res[popIndex][0] = leftIndex;
res[popIndex][1] = -1;
}
return res;
}
题目二 柱状图中的最大矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
int largestRectangleArea(vector<int>& heights) {
stack<int> stk;
int n = heights.size();
//开辟两个数组，分别记为左侧最小值和右侧最小值，相当于我们上面代码中将一个有两行的二维数组拆分成两个一维数组
vector<int> left(n + 1,-1), right(n + 1,n);
for(int i = 0; i < n; i++) {
while(!stk.empty() && heights[i]<=heights[stk.top()]){
//结算栈顶元素右边的最近最小值
right[stk.top()] = i;
stk.pop();
}
//每次新元素入栈时都结算它左边的最近最小值
left[i] = stk.empty() ? -1 : stk.top();
stk.push(i);
}
int Max = INT_MIN;
//遍历该数组的元素，并计算出面积的最大值
for(int i = 0; i < n; i++) {
Max = max(Max, (right[i] - left[i] - 1)*heights[i]);
}
return Max;
}
思考：为什么左边的最近最小值不存在时用-1来代替，右边的最近最小值不存在时用n来代替？这是为了方便下面计算面积。因为所有元素的下标都在0~n-1之间，所以找不到自己左边的最近最小值设为-1比较合理，找不到自己右边更小的最近最小值，设为n比较合理。这样左边最近最小值的左边-右边最近最小值的坐标-1就可以知道矩形的长度。
思考：栈中可能会有剩余元素，应该要怎样处理他们？因为每次元素入栈时，都结算了它的左边的最近最小值，所以可知所有元素都已经知道了它左边的最近最小值。对于剩下的元素，由于事先已经初始化right数组中的所有元素为n，所以也无需再次结算它们右边的最近最小值。
题目三 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
利用栈，可以很容易知道括号之间能否相互匹配。
int longestValidParentheses(string s) {
stack<int> stk;
//在栈底放-1，方便计算括号有效长度
stk.push(-1);
int i = 0, size = s.size();
int maxx = 0;
while(i < size){
if(s[i] == '('){ //如果是左括号，就直接入栈
stk.push(i);
}
else{
stk.pop();
//如果pop一个之后栈就为空，那么就代表着栈中原来只有一个'('或者')'，-1打底
if(stk.empty()){
//这个时候，我们直接将i push进去，类似于将i打底，方便计算括号有效长度
stk.push(i);
}
else{
//如果不为空，那么就计算括号的长度，然后保留最大值
maxx = max(maxx, i - stk.top());
}
}
i++;
}
return maxx;
}
