栈的相关概念
栈是仅在表尾进行插入，删除操作的线性表
表尾称为栈顶Top，表头称为栈底Base
插入元素到栈顶，称为入栈；从栈顶删除最后一个元素，称为出栈
栈的运算规则：先进后出
一.顺序栈
顺序栈的表示
利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端
为了方便操作，通常Top指示真正的栈顶元素之上的下标地址，所以Top指向内存空间不存放元素
- 空栈：top==base
- 栈满：top-base==stacksize
- 上溢：栈已满还要压入元素
- 下溢：栈已空还要弹入元素
- 栈中元素个数：top-base
顺序栈的定义
#define MAXSIZE 100
typedef char Elemtype; //栈的数据类型
typedef struct Sqstack
{Elemtype* base; //栈底指针Elemtype* top; //栈顶指针int stacksize; //栈的最大容量
}Sqstack;
顺序栈的初始化
bool Initstack(Sqstack& S) //构造一个空栈
{S.base = new Elemtype[MAXSIZE]; //在堆区开辟内存if (!S.base) //存储分配失败{cout << "顺序栈不存在" << endl;return false;}S.top = S.base; //栈顶指针等于栈底指针，空栈的标志S.stacksize = MAXSIZE;return true;
}
判断顺序栈是否为空
bool Isempty(Sqstack& S)
{if (S.base == S.top){return true;}return false;
}
顺序栈长度
int Stacklength(Sqstack& S)
{return S.top - S.base; //top指示真正的栈顶元素之上的下标地址//base指示的元素的下标地址为0
}
顺序栈的清空和销毁
bool Clearstack(Sqstack& S)
{if (S.base){S.base = S.top; //空栈定义return true;}return false;
}void Destroystack(Sqstack& S)
{if (S.base) //栈还存在的条件判断{delete S.base; //删除栈底指针S.stacksize = 0; //栈的容量置为0S.base = S.top = nullptr; //栈顶和栈底指针均为空}
}
顺序栈的入栈
- 判断是否栈满，若满则出错（上溢）
- 元素e压入栈顶
- 栈顶指针加1
bool Push(Sqstack& S,const Elemtype& e)
{if ((S.top - S.base) == S.stacksize){cout << "栈已满，无法入栈" << endl;return false;}*S.top = e; //将元素e压入栈顶++S.top; //栈顶指针加1return true;
}
顺序栈的出栈
- 判断是否栈空，若栈为空则出错（下溢）
- 获取栈顶元素e
- 栈顶指针减1
bool Pop(Sqstack& S,Elemtype& e)
{if (S.base == S.top){cout << "空栈，无法出栈！" << endl;return false;}--S.top; //栈顶指针减1e = *S.top; //获取栈顶元素ereturn true;
}
进制转换
void Change(int x)
{cout << "八进制转换后为：" << endl;Sqstack S;Initstack(S);int temp = x;while (temp) {Push(S, temp % 8);temp = temp / 8;}while (!Isempty(S)) {int i;//Pop(S, i);//cout << i;}
}
括号匹配
//输入括号()[]，判断括号是否匹配成功， # 字符表示输入结束
//例: ([()]) 成功[(())]] 失败
bool Match(void)
{Sqstack S;Initstack(S);char ch, pop;int flag = 1;cout << "输入符号（以#为结束标志）:" << endl;cin >> ch;while (flag && ch != '#') {switch (ch){case '(':Push(S, ch);break;case'[':Push(S, ch);break;case')':if (!Isempty(S) && *(S.top-1) == '('){Pop(S, pop);}else {flag = 0;}break;case']':if (!Isempty(S) && *(S.top - 1) == '['){Pop(S, pop);}else {flag = 0;}break;}cin >> ch;}if (flag && Isempty(S)){cout << "匹配成功！" << endl;return true;}else{cout << "匹配失败！" << endl;return false;}
}
二.链栈
链栈的表示
链栈是运算受限的单链表，只能在链表的头部进行操作
链表的头指针就是栈顶，不需要头结点（在下面代码中，我新建了一个头结点，头结点的数据域用来存放链栈中元素的个数）
基本不存在栈满的情况，空栈就相当于头指针指向空
插入和删除操作仅在栈顶处执行
链栈的定义
typedef char Elemtype;
typedef struct Stacknode
{Elemtype data;Stacknode* next;
}*Linkstack
链栈的初始化
void Initstack(Linkstack& L)
{//创建一个头结点，在头结点的数据域中保存栈中元素的个数L = new Stacknode; L->next = nullptr;L->data = 0;
}
判断链栈是否为空
bool Isempty(Linkstack& L)
{if (L->next == nullptr){return true;}return false;
}
链栈的入栈
void Push(Linkstack& L, const Elemtype& e)
{Stacknode *p = new Stacknode; //生成一个新结点pp->data = e; //新结点的数据域置为ep->next = L->next; //将新结点插入栈顶L->next = p; //修改栈顶指针++L->data; //栈中元素个数加1
}
链栈的出栈
void Pop(Linkstack& L, Elemtype& e)
{if (L->next == nullptr){cout << "栈为空，无法出栈！" << endl;return ;}else {Stacknode* p = L->next; //生成一个新结点pe = p->data;L->next = p->next;--L->data;delete p;}
}
获取链栈的元素的个数
int Stacklength(Linkstack& L)
{return L->data;
}
创建一个链栈（元素批量入栈）
#define count 6
void Creatstack(Linkstack& L)
{Elemtype e;for(int i=1;i<=count;i++){cin >> e;Push(L, e);}
}
队列的相关概念
队列是仅在表尾进行插入操作，在表头进行删除操作的线性表
队列的运算规则：先进先出
一.顺序队列
顺序队列的定义
#define MAXQSIZE 100 //定义数组大小
typedef char Elemtype;
typedef struct SqQueue
{Elemtype* elem;int front; //队头下标，指向队列头元素int rear; //队尾下标，指向队尾元素下一个位置
}SqQueue;
循环队列
初始时：front=rear=0
空队标志：front==rear
- 若front=0，rear=MAXQSIZE时，再入队–真溢出
- 若front≠0，rear=MAXQSIZE时，再入队–假溢出
解决假上溢的方法：
将队空间设想成一个循环的表，即分配给队列的m个存储单元可以循环使用，当rear=MAXQSIZE时，若向量的开始端空着，又可以从头使用空着的空间。当front=MAXQSIZE时也一样。
base[0]接在base[MAXQSIZE-1]之后，若rear+1==MAXQSIZE，则令rear=0
（实现方法：利用模运算%）
插入元素：
Q.base[Q.rear]=x
Q.rear=(Q.rear+1)%MAXQSIZE
删除元素：
Q.base[Q.front]=x
Q.front=(Q.front+1)%MAXQSIZE
但是此时会出现一个新的问题，就是队空和队满的标志都是front==rear，要解决这个问题，可以在队列中少用一个元素空间，此时
队空： front== rear
队满： (rear+1)%MAXQSIZE==front
元素个数： (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE
顺序队列的初始化
void Initqueue(SqQueue& Q)
{Q.elem = new Elemtype[MAXQSIZE];Q.front = Q.rear = 0; //头指针和尾指针置为0，队列为空的标志
}
判断顺序队列是否为空/满
bool Isempty(SqQueue& Q)
{if (Q.front == Q.rear)return true;return false;
}
//判断是否满队
//如果队尾+1等于队头，表明队已经满了
//该队列是少用一个空间的循环队列，满队和空队的判断条件不一致
bool Isfull(SqQueue& Q)
{auto rear_next = (Q.rear + 1) % MAXQSIZE;if (rear_next == Q.front)return true;elsereturn false;
}
进队&批量进队
bool Insertqueue(SqQueue& Q, const Elemtype& e)
{if (Isfull(Q)) {cout << "队已满，无法进队！" << endl;return false;}Q.elem[Q.rear] = e; //新元素加入队尾Q.rear = (Q.rear + 1) % MAXQSIZE; //队尾指针加1（当成是循环队列）return true;
}
//批量进队
#define n 6
void Creatqueue(SqQueue& Q)
{cout << "请输入"<<n<<"个队列元素：" << endl;Elemtype e;for (int i = 1; i <= n; i++) {cin >> e;Insertqueue(Q, e);}
}
出队
void Outqueue(SqQueue& Q)
{if (Isempty(Q)) //如果队头等于队尾，表明队里没有元素，不执行该程序{cout << "队列为空，没有元素可以出队" << endl;}Elemtype e;e = Q.elem[Q.front]; //保存队头元素Q.front = (Q.front + 1) % MAXQSIZE; //队头指针加1
}
获取队列中元素的个数
int Length(SqQueue& Q)
{return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}
打印队列
void Printqueue(SqQueue& Q)
{for (auto i = Q.front; i != Q.rear; i = (i + 1) % MAXQSIZE){cout << Q.elem[i] << " ";}
}
测试代码
#include <iostream>
using namespace std;int main(void) {SqQueue Q;Initqueue(Q);Creatqueue(Q);cout << "此队列为：" << endl;Printqueue(Q);Outqueue(Q);cout <<endl<< "一个元素出队后队列为：" << endl;Printqueue(Q);int n1 = Length(Q);cout<<endl<< "队列中元素的个数为：" << n1 << endl;cout << "元素出队为：" << endl;while (!Isempty(Q)){cout <<Q.elem[Q.front] << " ";Outqueue(Q);}int n2 = Length(Q);cout <<endl<< "队列中元素的个数为：" << n2<< endl;system("pause");return 0;
}
二.链队
链队的表示
若用户无法估计所用队列的长度，则适合采用链队列
链队的定义
typedef char Elemtype;
typedef struct Qnode
//定义结点，每个结点包括数据域data和指向下一个结点的指针域next
{Elemtype data;Qnode* next;
}Qnode;
//再定义一个抽象数据类型，表示队列，建立两个Qnode指针
typedef struct Linkqueue
{Qnode* front; //链队的头指针Qnode* rear; //链队的尾指针
}Linkqueue;
链队的初始化
void Initqueue(Linkqueue &L)
{L.front = L.rear = new Qnode;L.front->data = 0; //用于保存链队的元素个数L.rear->next = nullptr; //尾指针的指针域置为空
}
链队的销毁
从队头结点开始，依次释放所有的结点
bool Destroyqueue(Linkqueue& L)
{while (L.front){Qnode* p = L.front->next;delete L.front;L.front = p;}return true;
}
链队入队
void Insertqueue(Linkqueue& L, const Elemtype& e)
//把元素插在队尾
{Qnode* p = new Qnode;p->data = e;p->next = nullptr;L.rear->next = p;L.rear = p;++L.front->data; //队头指针数据域储存元素个数，加1
}
链队出队
bool Outqueue(Linkqueue& L, Elemtype &e)
{if (L.front->next == nullptr){cout << "空队列，无法出队！" << endl;return false;}Qnode* p = L.front->next;L.front->next = p->next;e = p->data;delete p;--L.front->data;return true;
}
创建&打印链队
void Creatqueue(Linkqueue& L)
{cout << "请输入"<<count<<"个链队元素：" << endl;for (int i = 1; i <= count; i++) {Elemtype e;cin >> e;Insertqueue(L, e);}
}
void Printqueue(Linkqueue& L)
{Qnode* p = L.front->next;while(p){cout << p->data <<" ";p = p->next;}
}
测试代码
#include <iostream>
using namespace std;int main(void)
{Linkqueue L;Initqueue(L);Creatqueue(L);cout << "此链队为：" << endl;Printqueue(L);//int m = L.front->data;//cout <<endl<< "此时链队中的元素个数为：" << m << endl;char e1 = L.front->next->data;cout <<endl<< "此时链队的队头元素为：" << e1 << endl;Elemtype x;Outqueue(L,x);cout << "出队元素为：" << x << endl;cout << "头元素出队后的链队为：" << endl;Printqueue(L);int n = L.front->data;cout << endl << "此时链队中的元素个数为：" << n << endl;char e2 = L.front->next->data;cout << "此时链队的队头元素为：" << e2 << endl;system("pause");return 0;}
