Data Structure — Stacks and Queues

Data Structure — Chapter 3: Stacks and Queues

Stacks and queues restrict where insertion and deletion can happen. These simple rules make them especially useful for parsing, traversal, scheduling, and sliding-window problems.

Reading guide: Compare the LIFO rule of a stack with the FIFO rule of a queue, then connect each rule to the examples in the notes.

1. 栈

如何解决括号匹配问题？ 所有左括号存入栈中，每来一个右括号，匹配成功则成对弹出，否则报错

特性：后进先出（Last In First Out, LIFO)

• 栈的首部为栈底，尾部为栈顶
• 插入删除均在栈顶进行，分别称为出栈（pop）和进栈（push）
• 此外还有取栈顶（top）和判断是否为空栈的操作

1.1 顺序栈：顺序存储的栈

• bottom=0；
• 栈空标志：top=-1；
• 栈满标志：top=maxSize-1；

class seqStack{
	private:
	int *elem;
	int top_p;
	int maxSize;
	void doubleSpace();
	
	public:
	seqStack(int initSize=10);
	~seStack();
	bool isEmpty() const;
	void push(const int &x);
	int pop();
	int top() const;
}

seqStack::seqStack(int initSize){
	elem=new int [initSize];
	maxSize=initSize;
	top_p=-1;
}

~seqStack(){
	delete[] elem;
}

void seqStack::doubleSpace(){
	int *tmp=elem;
	elem=new int [2*maxSize];
	for(int i=0; i<maxSize; i++) elem[i]=tmp[i];
	maxSize*=2;
	delete[] tmp;
}

void seqStack::push(const int &x){
	if(top_p==maxSize-1) doubleSpace();
	elem[++top_p]=x;
}

int seqStack::pop(){
	return elem[top_p--];
}

bool seqStack::isEmpty() const{
	return top_p==-1;
}

int seqStack:: top() const{
	return elem[top_p];
}

扩容时间复杂度是o(n)，其他是o(1)

1.2 链式栈：

==栈顶指针top指向处于栈顶的结点，即链表中的首节点==

class node{
	int data;
	node *next;
	node(const int &data, node *N=NULL){
		data=x;
		next=N;
	}
	node():next(NULL){}
	~node(){}
};

class linkStack{
	private:
	node *top_p;
	public:
	linkStack();
	~linkStack();
	bool isEmpty()const;
	void push(const int &x);
	int pop();
	int top() const;
}

linkStack::linkStack(){
	top_p=NULL;
}

linkStack::~linkStack(){
	node *tmp;
	while(top_p!=NULL){
		tmp=top_p;
		top_p=top_p->next;
		delete tmp;
	}
}

void linkStack::push (const int &x){
	top_p=new node (x,top_p);
}

int linkStack::pop(){
	node *tmp=top_p;
	int x=tmp->data;
	top_p=top_p->next;
	delete tmp;
	return x;
}

bool linkStack::isEmpty() const{
	return top_p==NULL;'
}

int linkStack::top() const{
	return top_p->data;
}

应用：表达式求值
三种表达形式：

• 中缀表达式：运算符在操作数中间
• 后缀表达式（逆波兰式）：运算符在操作数后
• 前缀表达式（波兰式）：运算符在操作数前
  使用后缀表达式

中缀转后缀方法：数字顺序不变，根据实际运算顺序调整符号顺序：

1. 初始化空栈，用于保存运算符，初始化一个空输出队列
2. 从左到右扫描中缀表达式：遇到操作数直接加入输出队列，遇到（入栈，遇到），弹出栈顶元素至输出队列，直到遇到（，（出栈但是不输出，遇到运算符，比较优先级，弹出栈顶优先级大于等于当前运算符的元素，再入栈当前运算符
3. 扫描完成后，将栈中剩余运算符依次弹出至输出队列

后缀式计算方法：

1. 初始化空栈，用于保存操作数
2. 从左到右扫描后缀表达式，遇到操作数入栈，遇到运算符，弹出栈顶两个元素，计算结果入栈
3. 最终栈顶元素为计算结果

2. 队列

一段插入，另一端删除
先进先出（First In First Out, FIFO)

2.1 顺序队列：

队列中元素个数最多为maxSize个，下标范围从0到maxSize-1，front指向队首元素，rear指向队尾元素

采用循环数组，且规定front指向的单元不能存储队列元素，只起到一个标志作用，表示后面一个是对头元素。
故队列满的条件是：(rear+1) % MaxSize == front；
队列为空的条件为 front == rear。

class seqQueue{
	private:
	int *elem;
	int maxSize;
	int front,rear;
	void doublespace();
	
	public:
	seqQueue(int size=10);
	~seqQueue();
	bool isEmpty() const;
	void enQueue(const int &x);
	in tdeQueue();
	int getHead() const;
}

seqQueue::seqQueue(int size){
	elem=new int [size];
	maxSize=size;
	front=rear=0;
}

seqQueue::~seqQueue(){
	delete[] elem;
}

bool seqQueue::isEmpty() const{
	return front==rear;
}

int seqQueue::deQueue(){
	front=(front+1)%maxSize;
	return elem[front];
}

int seqQueue::getHead() const{
	return elem[(front+1)%maxSize];
}

void seqQueue::enQueue(const int &x){
	if((rear+1)%maxSize==front) doubleSpace();
	rear=(rear+1)%maxSize;
	elem[rear]=x;
}

void seqQueue::doubleSpace(){
	int *tmp=elem;
	elem=new elemType[2*maxSize];
	for(int i=1;i<=maxSize;++i) elem[i]=tmp[(front+i)%maxSize];
	front=0;
	rear=maxSize;
	maxSize*=2;
	delete tmp;
}

2.2 链式队列

队首指针front指向队首结点，队尾指针rear指向队尾节点。不存在队满的情况，队空时，front=rear=NULL

class linkQueue{
	private:
	struct node{
		int data;
		node *next;
		node(const int &x, node *N=NULL):data(x),next(NULL){}
		~node(){}
	};
	
	node *front, *rear;
	
	public:
	linkQueue();
	~linkQueue;
	bool isEmpty() const;
	void enQueue(const int &x);
	int deQueue();
	int getHead() const;
}

linkQueue::linkQueue(){
	front=rear=NULL;
}

linkQueue::~linkQueue(){
	node *tmp;
	while(front!=NULL){
		tmp=front;
		front=front->next;
		delete tmp;
	}
}

bool linkQueue::isEmpty() const{
	return front==NULL
}

int linkQueue::getHead() const{
	return front->data;
}

void linkQueue::enQueue(const int &x){
	if(rear==NULL) front=rear=new node(x);
	else rear=rear->next=new node(x);
}

int linkQueue::deQueue(){
	node *tmp=front;
	int value=front->data;
	front=front->next;
	if(front==NULL) rear=NULL;
	delete tmp;
	return value;
}

2.3 优先队列

进入队列的元素有优先级，==优先级越高，出队越早，优先级越低，出队越晚==

顺序优先队列：
方案一：进队时不排序，出队时找到优先级最高的出队，可以不用使用循环队列，直接把队尾插入出队元素的存储位置，队空时rear=0，队满时rear=maxsize
方案二：进队时就将元素按优先级由小到大插入，出队时删去队头元素即可，采用循环队列
两种方法时间复杂度均为o(n)

2.4 单调队列（了解即可）

一个满足单调性质的双向队列，队内元素排列顺序满足单调递增或递减。若心如对元素破坏单调性，弹出对内元素，直至满足单调性再入队

可用于求一个序列中，连续k个数的最大值和最小值

# include <iostream>
using namespace std;
const int MAXN=100000;

int n,k;
//n 是数组长度，k是滑动窗口大小
int a[MAXN];
int ans[MAXN];

int main(){
	cin>>n>>k;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	int head=1;
	int tail=0;
	int q[MAXN]={0};
	//q中存放索引值
	for(int i=1;i<=n;++i){
		while (head<=tail && a[q[tail]]>=a[i]) --tail;
		//原队列里所有比a[i]大的数出列，因为它们不可能再是滑动窗口里的最小值了
		q[++tail]=i;
		while (q[head]<=i-k) ++head;
		if(i>=k) ans[i]=a[q[head]];
	}
	for(int i=k;i<=n;++i){
		cout<<ans[i]<<" ";
	}
	return 0;
}