数据结构——栈和队列

栈和队列

1. 栈

1.1 栈的基本概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

1.2 栈的实现

栈的基本操作如下：

1.2.1 顺序栈

class SeqStack{
public:SeqStack():a(nullptr),_size(0),capacity(InitSize){a=(T*)malloc(sizeof(T)*InitSize);}void push(T  x){if(_size==capacity){T *temp=(T*)realloc(a,sizeof(T)*capacity*2);if(temp==nullptr){perror("malloc fail");return ;}a=temp;capacity*=2;}a[_size++]=x;}void pop(){assert(_size!=0);_size--;}T top(){assert(_size!=0);return a[_size-1];}bool empty(){return _size==0;}int size(){return _size;}~SeqStack(){}
private:T *a;int _size;int capacity;
};

1.2.2 链栈

链栈的实现就是头插法。

#include <iostream>
#include <cassert>template <class T>struct SNode
{T data;SNode *next;SNode(T a) : data(a), next(nullptr) {}
};template <class T>class LinkStack
{typedef SNode<T> SNode;public:LinkStack() : _size(0), head(nullptr) {}void push(T x){SNode *node = new SNode(x);if (head == nullptr){head = node;}else{node->next = head;head = node;}_size++;}void pop(){assert(_size != 0);if (head->next == nullptr){delete head;head = nullptr;}else{SNode *temp = head->next;delete head;head = temp;}_size--;}int size(){return _size;}T top(){assert(_size != 0);return head->data;}bool empty(){return _size == 0;}~LinkStack() {}private:int _size;SNode *head;
};

2. 队列

2.1 队列的基本概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)。

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

2.2 队列的实现

队列的基本操作如下：

队列可以使用顺序、链式等结构存储，通常链式存储更为方便。

2.2.1 顺序队列

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针:队头指针 front 指向队头元素,队尾指针rear指向队尾元素的下一个位置(不同教材对front 和rear的定义可能不同)。这一点很重要，一定要看清楚rear和front具体指哪个元素。

初始：rear=front=0

判断队列为空：rear=front

入队操作：q[rear++]=x

出队操作：x=q[front++]

当front=0,rear=M时，再有元素入队发生溢出——真溢出
当front≠0,rear=M时，再有元素入队发生溢出——假溢出
解决方法：

当rear = MAXSIZE 时，即超过队列末端时，
令rear = 0；从而使队列的首尾相连接。  
用表达式描述:       
if （rear == MAXSIZE ）           rear = 0 ;       
else            rear = rear + 1 ;

2.2.2 循环队列

上面指出了顺序队列“假溢出”的问题，这里引出循环队列的概念。将顺序队列臆造为一个环状的空间,即把存储队列元素的表从逻辑上视为一个环,称为循环队列。当队首指针 Q.front=Maxsize-1后，再前进一个位置就自动到0，这可以利用除法取余运算%来实现。

初始：rear=front=0

入队操作：q[rear]=x; rear=(rear+1)%Maxsize

出队操作：x=q[front]; front=(front+1)%Maxsize

判断队空队满的方法：

队满：(rear+1)%M==front

队空：rear==front

队列元素个数：(rear-front+M)%M

入队与出队操作一般是不变的，无论rear和front指哪个元素，但是队满、队空、初始条件会不一样。

循环队列的实现：

2.2.3 链式队列

队列的链式表示称为链队列,它实际上是一个同时有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。

#include <iostream>
#include <cassert>
#include <cstdlib>template <class T>struct QNode
{T data;QNode *next;QNode(T a) : data(a), next(nullptr) {}
};
// 使用链式存储实现队列，便于实现其操作
template <class T>class LinkQueue
{typedef QNode<T> QNode;public:LinkQueue() : head(nullptr), tail(nullptr), _size(0) {}void push(T x)//尾插法{QNode *node = new QNode(x);if (head == nullptr){head = tail = node;}else{tail->next = node;tail = node;}_size++;}void pop(){assert(_size != 0);if (head->next == nullptr){free(head);head = nullptr;}else{QNode *temp = head->next;delete head;head = temp;}_size--;}bool empty(){return _size == 0;}size_t size(){return _size;}T front(){assert(_size != 0);return head->data;}T back(){assert(_size != 0);return tail->data;}~LinkQueue(){QNode *cur = head;while (cur){QNode *temp = cur->next;free(cur);cur = temp;}head = tail = nullptr;_size = 0;}private:QNode *head;QNode *tail;int _size;
};

3. 栈与队列的应用

3.1 括号匹配问题

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

有效字符串需满足：

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

https://leetcode.cn/problems/valid-parentheses/description/

// 顺序栈实现
typedef struct Stack {char data[10010];int top;
} Stack;
void InitStack(Stack* s) { s->top = 0; }void StackPush(Stack* s, char x) {s->data[s->top] = x;s->top++;
}
void StackPop(Stack* s) { s->top--; }char StackTop(Stack* s) { return s->data[s->top - 1]; }bool StackEmpty(Stack* s) { return s->top == 0; }bool isValid(char* s) {Stack st;InitStack(&st);int n = strlen(s);for (int i = 0; i < n; i++) {if(s[i]=='('||s[i]=='{'||s[i]=='[') StackPush(&st,s[i]);else{if(StackEmpty(&st))return false;else if(s[i]==')'&&StackTop(&st)!='(')  //只考虑错误情况return false;else if(s[i]=='}'&&StackTop(&st)!='{')return false;else if(s[i]==']'&&StackTop(&st)!='[')return false;StackPop(&st);}}return StackEmpty(&st);
}

/需要注意的是如果不返回结点，那么就要使用二级指针来写，链表章节注意的问题。

// 链栈实现
typedef struct SNode{struct SNode *next;char val;
}SNode;
void InitStack(SNode* s) 
{ s->next=NULL;
}
// 需要注意的是如果不返回结点，那么就要使用二级指针来写
void StackPush(SNode** s, char x) {SNode *temp = (SNode*)malloc(sizeof(SNode));temp->val = x;temp->next = *s;*s = temp;
}void StackPop(SNode** s) {if (*s != NULL) {SNode *temp = *s;*s = (*s)->next;free(temp);}
}char StackTop(SNode* s) { return s->val; }bool StackEmpty(SNode* s) { return s->next == NULL; }bool isValid(char* s) {SNode *st=(SNode*)malloc(sizeof(SNode));InitStack(st);int n = strlen(s);for (int i = 0; i < n; i++) {if(s[i]=='('||s[i]=='{'||s[i]=='[')StackPush(&st,s[i]);else{if(StackEmpty(st))return false;else if(s[i]==')'&&StackTop(st)!='(')return false;else if(s[i]=='}'&&StackTop(st)!='{')return false;else if(s[i]==']'&&StackTop(st)!='[')return false;StackPop(&st);}}return StackEmpty(st);
}


typedef struct SNode {struct SNode* next;char val;
} SNode;
void InitStack(SNode* s) { s->next = NULL; }SNode* StackPush(SNode* s, char x) {SNode* temp = (SNode*)malloc(sizeof(SNode));temp->val = x;temp->next = s;return temp;
}
SNode* StackPop(SNode* s) {SNode* temp = s->next;free(s);return temp;
}char StackTop(SNode* s) { return s->val; }bool StackEmpty(SNode* s) { return s->next == NULL; }bool isValid(char* s) {SNode* st = (SNode*)malloc(sizeof(SNode));InitStack(st);int n = strlen(s);for (int i = 0; i < n; i++) {if (s[i] == '(' || s[i] == '{' || s[i] == '[')st = StackPush(st, s[i]);else {if (StackEmpty(st))return false;else if (s[i] == ')' && StackTop(st) != '(')return false;else if (s[i] == '}' && StackTop(st) != '{')return false;else if (s[i] == ']' && StackTop(st) != '[')return false;st = StackPop(st);}}return StackEmpty(st);
}

3.2 表达式问题

前、中、后缀表达式

3.3 栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

https://leetcode.cn/problems/implement-queue-using-stacks/description/

一个栈用来存数据，一个用来出数据，出数据的栈为空时，将如数据栈的元素存入出数据栈。

class MyQueue {
public:MyQueue() {}void push(int x) { s1.push(x); }int pop() {int res = peek();s2.pop();return res;}int peek() {if (s2.empty()) {while (!s1.empty()) {s2.push(s1.top());s1.pop();}}int res = s2.top();return res;}bool empty() { return s1.empty() && s2.empty(); }private:stack<int> s1;stack<int> s2;};

typedef struct {int st1[100];int st2[100];int top1;int top2;
} MyQueue;MyQueue* myQueueCreate() {MyQueue *q = (MyQueue*)malloc(sizeof(MyQueue));q->top1=0;q->top2=0;return q;
}void myQueuePush(MyQueue* obj, int x) {obj->st1[obj->top1++]=x;
}int myQueuePeek(MyQueue* obj) {if(obj->top2==0){for(int i=obj->top1-1;i>=0;i--){obj->st2[obj->top2++]=obj->st1[i];}obj->top1=0;}int res=obj->st2[obj->top2-1];return res;
}int myQueuePop(MyQueue* obj) {int res=myQueuePeek(obj);obj->top2--;return res;
}bool myQueueEmpty(MyQueue* obj) {return obj->top1==0&&obj->top2==0;
}void myQueueFree(MyQueue* obj) {free(obj);obj=NULL;
}

3.4 队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

https://leetcode.cn/problems/implement-stack-using-queues/description/

class MyStack {
public:MyStack() {}void push(int x) {int n = q1.size();q1.push(x);for (int i = 0; i < n; i++) {  // 将元素重新pushq1.push(q1.front());q1.pop();}}int pop() {int res = top();q1.pop();return res;}int top() { return q1.front(); }bool empty() { return q1.empty(); }private:queue<int> q1;
};