栈和队列代码总结

川长思鸟来 2023-05-29 03:24 19阅读 0赞

### 文章目录 ###

*   *   *   *  1. 相关结构体定义
             *   *  1.1 顺序栈
                 *  1.2 链栈结点定义
                 *  1.3 顺序队列
                 *  1.4 链队定义
             *  2. 顺序栈相关操作
             *  3. 链栈相关操作
             *  4. 顺序栈的应用
             *  5. 顺序队
             *   *  5.1 循环队列
                 *  5.2 链队

#### 1. 相关结构体定义 ####

##### 1.1 顺序栈 #####

typedef struct{ 
    	int data[maxSize];      //存放栈中元素
    	int top;                //栈顶指针
    }SqlStack;                  //顺序栈类型定义

##### 1.2 链栈结点定义 #####

typedef struct LNode{ 
    	int data;       	   //数据域
    	struct LNode *next;    //指针域
    }LNode;                    //链栈结点定义

##### 1.3 顺序队列 #####

typedef struct{ 
    	int data[maxSize];    
    	int front;           //队首指针
    	int rear;            //队尾指针
    }SqQueue;                //顺序队列类型定义

##### 1.4 链队定义 #####

/** 队列头结点定义 */
    typedef struct QNode{ 
    	int data;            //数据域
    	struct QNode *next;  //指针域
    }QNode;                  //队结点类型定义
    
    /** 链队类型定义 */
    typedef struct{ 
    	QNode *front;      //队头指针
    	QNode *rear;       //队尾指针 
    }LiQueue;              //链队类型定义

#### 2. 顺序栈相关操作 ####

1.  初始化栈空

void initStack(SqStack &St){ 
    	st.top=-1;        //只需要将栈顶指针设置为1
    }

1.  判断栈空

/** 栈空返回1，否则返回0 */
    int isEmpty(SqStack st){ 
    	if(st.top==-1)
    		return 1;
    	else 
    		return 0;
    }

1.  进栈

int push(SqStack &st,int x){ 
    	if(s.top==maxSize-1)     //栈满
    		return 0;
    	++(st.top);              //先移动指针，再进栈
    	st.data[st.top]=x;
    	return 1;
    }

1.  出栈

int pop(SqStack &st,int &x){ 
    	if(st.top==-1)          //栈空，不能出栈
    		return 0;
    	x=st.data[s.top];       //先取出元素，再移动指针
    	--(s.top);
    	return 1;
    }

但试题中一般以以下形式居多：

int stack[maxSize]; int top;   //即完成栈的定义及初始化
    stack[++top]=x;                //元素进栈
    x=stack[top--];                //元素出栈

#### 3. 链栈相关操作 ####

1.  链栈初始化

void initStack(LNode *&lst){ 
    	lst=(LNode*)malloc(sizeof(LNode));    //制造一个头结点
    	lst->next=NULL;
    }

1.  判断栈空

int isEmpty(LNode *lst){ 
    	if(lst->next==NULL)
    		return 1;
    	else 
    		return 0;
    }

1.  进栈

void push(LNode *lst,int x){ 
    	LNode *p;
    	p=(LNode*)malloc(sizeof(LNode));   //为进栈元素申请结点空间
    	p->next=NULL;                      //指针域设为NULL
    	
    	/*链表的头插法*/
    	p->data=x;
    	p->next=lst->next;
    	lst->next=p;
    }

1.  出栈

int pop(LNode *lst,int &x){ 
    	LNode *p;
    	if(lst->next==NULL)
    		return 0;
    	
    	/*单链表的删除*/
    	p=lst->next;
    	x=p->data;
    	lst->next=p->next;
    	free(p);
    	return 1;
    }

#### 4. 顺序栈的应用 ####

**1. 判断一个表达式中的括号是否正确配对**

/** 表达式存放在expr[]中，字符个数为n */
    int match(char expr[],int n){ 
    	char stack[maxSize];int top=-1;
    	
    	for(int i=0;i<n;i++){ 
    		if(expr[i]=='(')        //遇到(入栈，
    			stack[++top]='(';
    		if(expr[i]==')'){ 	
    			if(top==-1)
    				return 0;	
    			else               //栈不空，则出栈，
    				--top;     
    		}
    	}  
    	if(top==-1)            //栈空，匹配
    		return 1;
    	else
    		return 0;
    }

**2. 编写一个求后缀式的数值的函数**

/** 后缀式存储在expr中，最后一个字符为"\0",作为结束符，后缀式中数字只有一位 */
    int op(int a,char opt,int b){ 
    	if(opt=='+') return a+b;
    	if(opt=='-') return a-b;
    	if(opt=='*') return a*b;
    	if(opt=='/') { 
    		if(b==0){ 
    			return 0;
    		}
    		else
    			return a/b;
    	}
    }
    
    int com(char expr[]){ 
    	int stack[maxSize];int top=-1;
    	int a,b,c;
    	char opt;
    	for(int i=0;expr[i]!='\0';i++){ 
    		if(expr[i]>='0'&&expr[i]<='9')
    			stack[++top]=expr[i]-'0';
    		else{ 
    			opt=expr[i];         //取运算符
    			b=stack[top--];		 //取第二个操作数
    			a=stack[top--];      //取第一个操作数
    			c=op(a,opt,b);
    			stack[++top]=c;      //运算结果入栈
    		}
    	}
    	return stack[top];
    }

#### 5. 顺序队 ####

##### 5.1 循环队列 #####

两个状态：  
队空状态：qu.rear== qu.front  
队满状态：(qu.rear+1)%maxSize==qu.front

两个操作：  
入队：`qu.rear=(qu.rear+1)%maxSize; qu.data[qu.rear]=x;`  
出队：`qu.front=(qu.front+1)%maxSize; x=qu.data[qu.front];`

*  初始化队列

void initQueue(SqQueue &qu){ 
    	qu.front=qu.rear;       //队首和队尾指针重合，并且指向0
    }

*  判断队空

int isEmpty(SqQueue qu){ 
    	if(qu.front==qu.rear)
    		return 1;
    	else 
    		return 0;
    }

*  进队

int enQueue(SqQueue &qu,int x){ 
    	if((qu.rear+1)%maxSize==qu.front)         //队满
    		return 0;
    	qu.rear=(qu.rear+1)%maxSize;      //队未满，先移动指针
    	qu.data[qu.rear]=x;               //再存入元素
    	return 1;
    }

*  出队

int Dequeue(Squeue &qu,int &x){ 
    	if(qu.front==qu.rear)      //队空，不能出队
    		return 0;
    	qu.front=(qu.front+1)%maxSize; 
    	x=qu.data[qu.front];       //取出元素
    	return 1;
    }

##### 5.2 链队 #####

*  两个状态  
    队空：`lqu->rear== NULL或者lqu->front== NULL`
 *  两个操作  
    进队：`lqu->rear->next=p;lqu->rear=p;`  
    出队：`p=lqu->front;lqu->front=p->next;x=p->data;free(p);`

1.  初始化队列

void initQueue(LiQueue *&lqu){ 
    	lqu=(LiQueue*)malloc(sizeof(LiQueue));
    	lqu->front=lqu->rear=NULL;
    }

1.  判断队空

int isEmpty(LiQueue *lqu){ 
    	if(lqu->rear==NULL||lqu->front==NULL)
    		return 1;
    	else 
    		return 0;
    }

1.  入队

void enQueue(LiQueue *lqu,int x){ 
    	QNode *p;
    	p=(QNode*)malloc(sizeof(QNode));
    	p->data=x;
    	p->next=NULL;
    	if(lqu->rear==NULL)   //队列空，则新结点是队首结点，也是队尾结点
    		lqu->front=lqu->rear=p;	
    	else
    		lqu->rear->next=p;  //将新结点链接到队尾，rear指向它
    		lqu->rear=p;
    }

1.  出队

int deQueue(LiQueue *lqu,int &x){ 
    	QNode *p;
    	if(lqu->rear==NULL)
    		return 0;
    	else
    		p=lqu->front;
    	if(lqu->front==lqu->rear)   //队列中只有一个结点时
    		lqu->front=lqu->rear=NULL;
    	else
    		lqu->front=lqu->front->next;
    	x=p->data;
    	free(p);
    	return 1;
    }