导航小助手
栈
栈的基本概念
栈的基本性质
- 栈（Stack）是只允许在一段进行插入或者删除的线性表。
- 栈顶（Top）。线性表允许进行插入删除的那一端。
- 栈底（Bottom）。固定，不允许插入删除。
- 空栈。不含任何元素。
栈的基本操作
void InitStack(&S);//初始化一个空栈s。
bool StackEmpty(S);//判断一个栈是否为空， 若栈s 为空则返回true,否则返回false。
bool Push(&S,x);//进栈，若栈s未满， 则将x加入使之成为新栈顶。
bool Pop(&S,&x);//出栈，若栈s非空，则弹出栈顶元素， 并用x返回。
bool GetTop(S,&x);//读栈顶元素，若栈s非空， 则用x返回栈顶元素。
bool DestroyStack(&S);//销毁栈， 并释放栈s占用的存储空间。
栈的存储结构
顺序栈
#define MaxSize 50//栈中元素最大个数
typedef struct{
int data[MaxSize];//存放栈中元素
int top;//栈顶指针
}SqStack;
栈顶指针：S.top,初始时设置s.top=-1;
栈顶元素：S.data[S.top]；
进栈操作：栈不满时， 栈顶指针先加1,再送值到栈顶元素；
出栈操作：栈非空时， 先取栈顶元素值， 再将栈顶指针减1 ；
栈空条件：S.top= =-1;
栈满条件：S.top= =MaxSize-1;
栈长：S.top+1。
基本操作
//初始化
void InitStack(SqStack &S) {
S->top = -1;
}
//判断栈空
bool StackEmpty(SqStack S) {
if (S->top == -1)
return true;
else
return false;
}
//进栈
bool Push(SqStack &S, int x) {
if (S->top == MaxSize - 1)
return false;
else {
S->top++;
S->data[S->top] = x;
}
return true;
}
//出栈
bool Pop(SqStack &S, int &x) {
if (S->top == -1)
return false;
else {
*x = S->data[S->top];
S->top--;
return true;
}
}
//读栈顶元素
bool getTop(SqStack &S, int &x) {
if (S->top == -1)
return false;
*x = S->data[S->top];
return true;
}
链式栈
typedef struct LinkNode{
int data;
struct Linknode *next;
}stack;
插入和删除在表头执行
bool push(stack* S,int e){
p=(struct linkNode*)malloc(sizeof(LinkNode));
p->data=e;
p->next=S;
S=p;
return true;
}
bool empty(stack* S){
if(S->head==NULL){
return true;
}
else{
return false;
}
}
bool pop(stack* S,int* e){
if(emptyz(S)){
return false;
}
e=S->data;
struct Linknode* p=S;
S=S->next;
free(p);
return true;
}
队列
队列的基本概念
队列的定义
队列（Queue），也是一种操作受限的线性表，只允许在一段进行插入并且在另一端进行删除。
队列的操作
void InitQueue(&Q);//初始化队列，构造一个空队列Q。
bool QueueErnpty(Q);//判队列空，若队列Q为空返回七rue,否则返回false。
void EnQueue(&Q,x);//入队，若队列Q未满，将x加入，使之成为新的队尾。
void DeQueue(&Q,x);//出队，若队列Q非空，删除队头元素，并用x返回。
void GetHead(Q, &x);//读队头元素，若队列Q非空，则将队头元素赋值给x。
队列的存储结构
顺序队
#define MaxSize 50//定义队列中元素的最大个数
typedef struct{
int data[MaxSize];//存放队列元素
int front,rear;//队头指针和队尾指针
}SqQueue;
初始状态（队空条件）：Q.front = =Q.rear= = 0。
进队操作：队不满时， 先送值到队尾元素， 再将队尾指针加1。
出队操作：队不空时， 先取队头元素值， 再将队头指针加1。
一般不会采用顺序队，因为对空间的利用率很低，如果需要使用数组来实现队列，都是通过循环队列
循环队
初始:Q.front=Q.rear=0
队首指针加1：Q.front=(Q.front+1)%MaxSize
队尾指针加1：Q.rear=(Q.front+1)%MaxSize
需要注意的是，这样我们看见队满和队空的条件都是Q.front=Q.rear=0
那么怎么区分是满还是空？
方法1：用一个区来区分对空还是队满
约定队头指针在队尾指针下一个时为满队，这样我们就少用一个元素
队满条件：(Q.rear+1)%MaxSize==Q.front
队空条件：Q.rear=Q.front
方法2：增加一个元素来表示队列成员个数
队满：Q.size==MaxSize
队空：Q.size==0
方法3：新增成员来区分队满还是队空
添加操作flag=true,删除操作falg=false
队满:Q.rear=Q.front&&falg
队空:Q.rear=Q.front&&!falg
void InitQueue(SqQueue &Q){
Q.rear=Q.front=0;
}
bool isEmpty(SqQueue Q){
if(Q.rear==Q.front) return true;
else return false;
}
bool isFull(SqQueue Q){
if((Q.rear+1)%MaxSize==Q.front)) return true;
else return false;
}
bool EnQueue(SqQueue &Q,int x){
if(isFull(Q))
return false;
Q.data[Q.rear]=x;
Q.rear=(Q.front+1)%MaxSize;
return true;
}
bool DeQueue(SqQueue &Q,int* x){
if(isEmpty(Q)) return false;
x=Q.data[Q.front];
Q.front=(Q.front+1)%MaxSize;
return true;
}
链式队
typedef struct{
int data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front,*rear; ／／队列的队头和队尾指针
}LinkQueue;
Q.front==NULL&&Q.rear==NULL队列为空
//初始化队列时给一个头节点，便于操作
void initQueue(LinkQueue &Q){
Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
Q.front->next=NULL;
}
bool isEmpty(LinkQueue Q){
if(Q.front==Q.rear)
return true;
else
return false;
}
void enQueue(LinkQueue &Q,int x){
LinkNode* s=(LinkNode*)malloc(sizeof(LinkNode));
s->data=x;
s->next=NULL;
Q.rear->next=s;
Q.rear=s;
}
bool deQueue(LinkQueue &Q,int* x){
if(Q.front==Q.rear)
return false;
LinkNode*p=Q.front->next;
x=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return true;
}
双端队列
可以在队头和队尾进行插入删除的队列。