栈和队列代码总结

  • Post author:
  • Post category:其他




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;
}



版权声明:本文为weixin_38339025原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。