栈和队列的实现及操作

 本文章是在考研复习过程中通过观看网络上的讲解视频之后进行的归纳总结，以便日后的复习，同时也想分享给大家，如有问题，欢迎评论区留言！

栈和队列

栈和队列栈

栈的顺序存储实现栈的链式存储实现栈的应用

栈在括号匹配的应用栈在表达式求值的应用栈在递归的应用栈在其他的应用队列

队列的顺序实现队列的链式实现（带头结点）队列的链式实现（不带头结点）双端队列队列的应用

栈

（1）栈是只允许在一端进行插入或删除操作的线性表，即插入或删除操作只可以在栈顶进行

（2）特点：后进先出，n个不同元素出栈，出栈元素不同排列的个数为(C2n n)/n+1

栈的顺序存储实现

结构体

typedef struct stack
{
	int *ptop;  //栈顶指针 
	int *pbase;	//栈底指针 
	int max;//栈的最大容量 
}ST,*ps;

顺序栈的初始化

void init(ps s,int m)//顺序栈的初始化 
{
	s->pbase=new int[m];
	if(s->pbase==NULL)
	{
		printf("内存分配失败！n");
		return ;
	}
	else
	{
		s->max=m;
		s->ptop=s->pbase;
		return;
	}
 }

压栈

void push(ps s,int d) //压栈 
 {
 	if((s->ptop)-(s->pbase)==s->max)
 	{
 		printf("栈已满！n");
 		return ;
	 }
	else
	{
		*(s->ptop)=d;
		(s->ptop)++;
	} 
	return;
}

出栈

void pop(ps s,int *e)//出栈 
{
	if(is_empty(s)==true)
	{
		printf("栈为空！n");
		return;
	}
	
	else
	{
		*e=*(s->ptop);
		(s->ptop)--;
		return ;
	}
}

判断栈是否为空

bool is_empty(ps s)//判断栈是否为空 
{
	if(s->ptop==s->pbase)
	{
		return true; 
	} 
	else
	return false;
}

取栈顶的元素

int Getzd(ps s)//取栈顶的元素 
{
	int zd;
    if(is_empty(s)==true)
	{
		printf("栈为空！n");
	}
	else
	{
		return *(s->ptop-1);
	}
}

栈的遍历输出

void traverse(ps s)//栈的遍历输出 
{
	if(is_empty(s)==true)
	{
		printf("栈为空！n");
		return;
	}
	else
	{
		int *p=s->ptop;
		printf("栈中的数据为：n");
		while(p!=s->pbase)
		{
			p--;
			printf("%d  ",*(p));
			
		}
		printf("n");
		return ;
		
	}
	
}

栈的链式存储实现

结构体（一个结点，一个是栈）

typedef struct JieDian
{
	int data;
	struct JieDian *pnext;	
}jd,*pj;

typedef struct stack
{
	pj ptop;
	pj pbottom;	
}stack,*ps;

链栈的初始化

void init (ps s)//栈的初建 
{
	s->ptop=new(jd);
	if(s->ptop==NULL)
	{
		printf("内存分配失败！");
		return; 
	}
	else
	{
		s->pbottom=s->ptop;
		s->pbottom->pnext=NULL;
	}
}

压链栈

void push(ps s,int d)//压栈 
{
	pj pnew=new(jd);
	if(pnew==NULL)
	{
		printf("内存分配失败！");
		return; 
	}
	else
	{
		pnew->data=d;
		pnew->pnext=s->ptop;
		s->ptop=pnew;
	}	
}

判断链栈是否为空

bool is_empty(ps s)//判断栈是否为空 
{
	if(s->pbottom==s->ptop)
	return true;
	else 
	return false;
}

链栈的遍历

void traverse(ps s)//栈的遍历 
{
	if(is_empty(s)==true)
	{
	  printf("栈为空，请先输入数据！n");
	  return ;
    }
	else
	{
		pj p=s->ptop;
		printf("栈中的数据为：n");
		while(p!=s->pbottom)
		{
			printf("%d  ",p->data);
			p=p->pnext;		
		}
		printf("n");
		return ;	
	}
}

出链栈

void pop(ps s,int *val)//出栈 
{
	if(is_empty(s)==true)
	{
	  printf("栈为空，请先输入数据！n");
	  return ;
    }
    
    else 
    {
    	pj p=s->ptop;
    	*val=p->data;
    	s->ptop=p->pnext;
    	delete(p);
	}
	return ;
	
}

链栈的清空

void clear_stack(ps s,int *a)//栈的清空 
{
	int i=0;
	if(is_empty(s)==true)
	{
	  printf("栈为空，请先输入数据！n");
	  return ;
    }
    else
	{
		pj p=s->ptop,q;
		while(p!=s->pbottom)
		{
			a[i]=p->data;
			i++;
			q=p->pnext;
			delete(p);
			p=q;
		}
		s->ptop=s->pbottom;
	return ;	
    	
	}	
}

取链栈顶元素

int GEtzd(ps s)//取栈顶元素 
{
	if(is_empty(s)==true)
	{
	  printf("栈为空，请先输入数据！n");
    }
    else
	{
		pj p=s->ptop;
		return p->data;
    }
	
 }

栈的应用栈在括号匹配的应用

原理：最后出现的左括号最先被匹配。遇到左括号就入栈，遇到右括号就消耗一个左括号，即弹出栈顶元素，检查是否匹配。

匹配失败情况：
（1）左括号‘单身’
（2）右括号‘单身’
（3）左右括号不匹配

代码示例：

#include
#include
typedef struct JieDian
{
	char a;
	struct JieDian *pnext;	
}jd,*pj;

typedef struct stack
{
	pj ptop;
	pj pbottom;	
}stack,*ps;
void init (ps s);//栈的初建 
void push(ps s,char d);//压栈
bool is_empty(ps s);//判断栈是否为空
char gettop(ps s);//取栈顶元素
void kuohao(ps s,char *a);//括号匹配
void pop(ps s);//出栈 
int main()
{
	stack s;
	char a[20];
	printf("请输入一个字符串！n");
	scanf("%s",a);
	if(a[0]==']'||a[0]==')'||a[0]=='}')
	{
	   printf("输入错误！n");
	   return 0;
    }
    init(&s);
    kuohao(&s,a);//括号匹配
	return 0;
}


void init (ps s)//栈的初建 
{
	s->ptop=new(jd);
	if(s->ptop==NULL)
	{
		printf("内存分配失败！");
		return; 
	}
	else
	{
		s->pbottom=s->ptop;
		s->pbottom->pnext=NULL;
	}
}


void push(ps s,char d)//压栈 
{
	pj pnew=new(jd);
	if(pnew==NULL)
	{
		printf("内存分配失败！");
		return; 
	}
	else
	{
		pnew->a=d;
		pnew->pnext=s->ptop;
		s->ptop=pnew;
	}		
} 


bool is_empty(ps s)//判断栈是否为空 
{
	if(s->pbottom==s->ptop)
	return true;
	else 
	return false;
}

char gettop(ps s)//取栈顶元素 
{
	if(s->ptop==s->pbottom)
	return 0;
	else
	return s->ptop->a;
}

bool pd(char *a)
{
	int i;
	for(i=0;iptop;
    	val=p->a;
    	s->ptop=p->pnext;
    	delete(p);
    	printf(" %c 出栈n",val);
	}
	return ;
	
}

栈在表达式求值的应用

三种表达式：
（1）中缀表达式：运算符在两个操作数中间
（1）后缀表达式：运算符在两个操作数后面
（1）前缀表达式：运算符在两个操作数前面

中缀表达式的计算（用栈实现，中缀转后缀和后缀表达式计算两算法结合）
（1）初始化两个栈（操作数栈和运算符栈）
（2）若扫描到操作数，压入操作数栈
（2）若扫描到运算符，则按照“中缀转后缀”相同逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符，就需要再弹出操作数栈的两个栈顶元素，并执行相应运算，运算结果再压回操作数栈）

栈在递归的应用

每进入一层递归，就将递归调用所需信息压入栈顶
每退出一层递归，就从栈顶弹出相应信息
缺点：太多递归可能导致栈溢出

栈在其他的应用

如进制转换，函数调用等很多符合“先进后出”这一特点的应用

队列

（1）队列是只允许在一端进行插入，另一端进行删除的线性表

（2）特点：先进入队列的元素先出队

（3）队头：允许删除的一端

（4）队尾：允许插入的一端

（5）循环队列已满条件：（Q.rear+1）%MaxSize==Q.front

（6）循环队列为空条件：Q.rear==Q.front

（7）循环队列元素个数：（Q.rear-Q.front+MaxSize）%MaxSize

队列的顺序实现

结构体

typedef struct{
	int data[MaxSize];
	int front,rear;
}SqQueue;

入队

//入队 
bool EnQueue(SqQueue &Q,int x)
{
	if((Q.rear+1)%MaxSize==Q.front)//判断队满 
	 return false;
	Q.data[Q.rear]=x;
	Q.rear=(Q.rear+1)%MaxSize;
	return true;
}

判断队列是否为空

//判断队列是否为空 
bool QueueEmpty(SqQueue Q){
	if(Q.rear==Q.front)
{
	return true;
}
else
    return false;	
}

出队

//出队（删除队头元素，并用x返回） 
bool DeQueue(SqQueue &Q,int &x)
{
	if(Q.rear==Q.front)
	return false;
	x=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;//队头指针后移 
	return true;
 }

取队头元素

bool GetHead(SqQueue Q,int &x)
{
	if(Q.rear==Q.front)
	return false;
	x=Q.data[Q.front];
	return true;
 }

求队列的长度

int  Queuelength(pd d)//求队列的长度 
{
	return ((d->rear)-(d->front)+maxsize)%maxsize;
}

队列的链式实现（带头结点）

结构体（一个为链式队列结点，另一个为链式队列）

typedef struct linkNode{//链式队列结点 
	int data;
	struct linkNode *next;
}linkNode; 

typedef struct{ //链式队列 
	linkNode *front,*rear;//队列的队头和队尾指针 
}linkQueue;

初始化（定义头结点）

void InitQueue (linkQueue &Q){
//定义头结点 
Q.front=Q.rear=(linkNode*)malloc(sizeof(linkNode));
Q.front->next=NULL;
}

新元素入队（带头结点）

//新元素入队（带头结点） 
void EnQueue (linkQueue &Q,int x){
	linkNode *s=(linkNode *)malloc(sizeof(linkNode));
	s->data=x;
	s->next=NULL;
	Q.rear->next=s;//新结点插入到rear后 
	Q.rear=s;	//表尾指针rear指向新结点 
}

队头元素出队（带头结点）

//队头元素出队，带头结点 
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(rear==p)//若是最后一个元素出队 
	 Q.rear=Q.front;//修改rear指针
	free(p); 
	return true; 
 }

判断队列是否为空

bool IsEmpty(linkQueue Q){
	if(Q.front==Q.rear)//或者Q.front->next=NULL; 
	 return true;
	else
	 return false;
}

队列的链式实现（不带头结点）

结构体（和带头结点一样）

typedef struct linkNode{//链式队列结点 
	int data;
	struct linkNode *next;
}linkNode; 

typedef struct{ //链式队列 
	linkNode *front,*rear;//队列的队头和队尾指针 
}linkQueue;

初始化（不带头结点）

void InitQueue (linkQueue &Q){
//不带头结点 
Q.front=NULL;
Q.rear=NULL; 
}

新元素入队（不带头结点）

//新元素入队（不带头结点） 
void EnQueue (linkQueue &Q,int x){
	linkNode *s=(linkNode *)malloc(sizeof(linkNode));
	s->data=x;
	s->next=NULL;
	//不带头结点的指针，第一个元素需要特殊处理 
	if(Q.front==NULL)
	{
		Q.front=s;
		Q.rear=s;
	 } 
	 
	 else{
	 	Q.rear->next=s;
	 	Q.rear=s;
	 }
}

队头元素出队（不带头结点）

//队头元素出队，不带头结点 
bool DeQueue(linkQueue &Q,int &x)
{
	if(Q.front==Q.rear)
	 return false;
	linkNode *p=Q.front;
	x=p->data;
	Q.front=p->next;
	if(rear==p)//若是最后一个元素出队 
	 {
	   Q.rear=NULL;//修改rear指针为空队列状态 
	   Q.front=NULL;//修改front指针空队列状态 
     }
	free(p); 
	return true; 
	 
	
 }

判断队列（不带头结点）是否为空

bool IsEmpty(linkQueue Q){
	if(Q.front==NULL)
	 return true;
	else
	 return false;
}

双端队列

允许两端插入，两端删除的线性表

队列的应用

（1）树的层次遍历
（2）图的广度优先遍历
（3）操作系统的FCFS（先来先服务）
（4）舞队配对

栈和队列的实现及操作

C/C++/C#相关栏目本月热门文章