栈和队列初学总结

客官°小女子只卖身不卖艺 2022-07-15 14:46 179阅读 0赞

一.栈的顺序存储

#include<iostream>
    #include<cstdlib>
    #include<string>
    typedef char ElemType;
    
    #define MAXSIZE 50
    
    typedef struct
    {
    	ElemType data[MAXSIZE];
    	int top;
    }SqStack;
    
    void InitStack(SqStack *&s)
    {
    	s = (SqStack *)malloc(sizeof(SqStack));
    	s->top = -1;
    }
    
    void DestoryStack(SqStack *&s)
    {
    	free(s);
    }
    
    bool StackEmpty(SqStack *s)
    {
    	return (s->top == -1);
    }
    
    bool Push(SqStack *&s, ElemType e)
    {
    	if (s->top == MAXSIZE - 1)
    		return false;
    	s->top++;
    	s->data[s->top] = e;
    	return true;
    }
    
    bool Pop(SqStack *&s, ElemType &e)//后进先出
    {
    	if (s->top == -1)
    		return false;
    	e = s->data[s->top];//保留被“删除”的数据
    	s->top--;
    	return true;
    }
    
    bool GetTop(SqStack *s, ElemType &e)//元素出栈时，保留出栈元素
    {
    	if (s->top == -1)
    		return false;
    	e = s->data[s->top];
    	return true;
    }
    
    bool symmetry(ElemType str[])
    {
    	int i;
    	ElemType save;
    	SqStack *s;
    	InitStack(s);
    	for (i = 0;str[i] != '\0'; i++)
    	{
    		Push(s,str[i]);
    	}
    	if (StackEmpty(s))
    	{
    		return true;
    		DestoryStack(s);
    	}
    //方法一
    #if(0)
    	{
    		for (i = 0;(i!=s->top)&&(i<s->top); i++)//当字符串个数为奇数时,(i!=s->top);当字符串个数为偶数时,(i<s->top)
    		{
    			GetTop(s, save);//得到栈顶元素后，top没变
    			if (s->data[i] != save)
    			{
    				break;
    			}
    			Pop(s,save);
    		}
    		if (i == s->top||i>s->top)
    		{
    			DestoryStack(s);
    			return true;
    		}
    		else
    		{
    			DestoryStack(s);
    			return false;
    		}
    	}
    	#endif
    
    //方法二
    	for(i=0;str[i]!='\0';i++)
    	{
    		Pop(s,save);//直接用出栈函数，取得top值
    		if(str[i]!=save)
    		{
    			DestoryStack(s);
    			return false;
    		}
    	}
    	DestoryStack(s);
    	return true;
    }
    
    int main(void)
    {
    	char str[MAXSIZE];
    	std::cout<<"请输入一段字符串:\n";
    	std::cin.getline(str,MAXSIZE);
    	if(symmetry(str))
    	{
    		std::cout<<"该串是对称串！\n";
    	}
    	else
    	{
    		std::cout<<"该串不是对称串！\n";
    	}
    	system("pause");
    	return 0;
    }

二.栈的链式存储

#include<iostream>
    #include<cstdlib>
    //#include<string>
    
    typedef char ElemType;
    #define MaxSize 20
    
    typedef struct linknode
    {
    	ElemType data;
    	struct linknode * next;
    }LiStack;
    
    void InitStack(LiStack *&s)
    {
    	s = (LiStack *)malloc(sizeof(LiStack));//该链表头结点无数据
    	s->next = NULL;
    }
    
    void DestroyStack(LiStack *&s)
    {
    	LiStack *p = s, *q = s->next;
    	while (q != NULL)
    	{
    		free(p);
    		p = q;
    		q = p->next;
    	}
    	free(p);
    }
    
    bool StackEmpty(LiStack *s)//判断列表是否为空
    {
    	return(s->next == NULL);
    }
    
    void Push(LiStack *&s, ElemType e)//进栈，头插法，此时“top”即最后进去的那个数，与顺序法一样
    {
    	LiStack *p;
    	p = (LiStack *)malloc(sizeof(LiStack));
    	p->data = e;
    	p->next = s->next;
    	s->next = p;
    }
    
    bool Pop(LiStack *&s, ElemType &e)//后进先出
    {
    	LiStack *p;
    	if (s->next == NULL)//判断链表是否为空，为空则不能再出栈
    	{
    		return false;
    	}
    	p = s->next;
    	e = p->data;//出栈时，要保留出栈的元素
    	s->next = p->next;
    	free(p);
    	return true;
    }
    
    bool GetTop(LiStack *s, ElemType &e)
    {
    	if (s->next == NULL)//若链表为空，则无法提取栈顶元素
    	{
    		return false;
    	}
    	e = s->next->data;
    	return true;
    }
    
    bool Match(char exp[])
    {
    	int i;
    	bool match = true;
    	ElemType save;
    	LiStack *s;
    	InitStack(s);
    	for (i = 0; exp[i] != '\0'; i++)
    	{
    		if (exp[i] == '(')
    		{
    			Push(s, exp[i]);
    		}
    		if (exp[i] == ')')
    		{
    			if (GetTop(s, save) == true)//若此时的栈顶元素没有取到，则说明没有‘(’与')'相匹配
    			{
    				if (save == '(')
    				{
    					Pop(s, save);
    				}
    				else
    				{
    					match = false;
    				}
    			}
    			else match = false;
    		}
    	}
    	if (!StackEmpty(s))
    	{
    		match = false;
    	}
    	return match;
    }
    
    int main(void)
    {
    	char str[MaxSize];
    	std::cout<<"请输入一段字符串:\n";
    	std::cin.getline(str,MaxSize);
    	if(Match(str))
    	{
    		std::cout<<"匹配成功！\n";
    	}
    	else
    	{
    		std::cout<<"匹配失败！\n";
    	}
    	system("pause");
    	return 0;
    }

![Center][]

三.队列的顺序存储

#include<iostream>
    #include<cstdlib>
    
    typedef char ElemType;
    
    #define MaxSize 50
    
    typedef struct
    {
    	ElemType data[MaxSize];
    	int front, rear;
    }SqQueue;
    
    void InitQueue(SqQueue *&q)
    {
    	q = (SqQueue *)malloc(sizeof(SqQueue));
    	q->front = q->rear = -1;
    }
    
    void DestroyQueue(SqQueue *&q)
    {
    	free(q);
    }
    
    bool QueueEmpty(SqQueue *q)
    {
    	return (q->front == q->rear);//顺序表为空的条件
    }
    
    bool enQueue(SqQueue *&q,ElemType e)
    {
    	if(q->rear==MaxSize-1)//队列上溢的条件
    	{
    		return false;
    	}
    	q->rear++;//数组尾下标+1
    	q->data[q->rear]=e;
    	return true;
    }
    
    bool deQueue(SqQueue *&q,ElemType &e)
    {
    	if(q->front==q->rear)
    	{
    		return false;
    	}
    	q->front++;
    	e=q->data[q->front];
    	return true;
    } 
    
    int main(void)
    {
    	system("pause");
    	return 0;
    }

四.队列的链式存储

#include<iostream>
    #include<cstdlib>
    
    typedef int ElemType; 
    
    typedef struct qnode
    {
    	ElemType data;
    	struct qnode * next;
    }Qnode;						//链表数据节点类型定义
    
    typedef struct 
    {
    	Qnode *front;//通过front、rear指挥链表的排列
    	Qnode *rear;
    }LiQueue;
    
    void InitQueue(LiQueue *&q)
    {
    	q=(LiQueue*)malloc(sizeof(LiQueue));
    	q->front=q->rear=NULL;//头尾‘指挥’的初始化
    }
    
    void DestroyQueue(LiQueue *&q)
    {
    	Qnode *p=q->front,*r;
    	if(p!=NULL)
    	{
    		r=p->next;
    		while(r!=NULL)
    		{
    			free(p);
    			p=r;
    			r=p->next;
    		}
    	}
    	free(p);
    	free(q);
    }
    
    bool QueueEmpty(LiQueue *q)
    {
    	return(q->rear==NULL);//判断链表是否为空的条件
    }
    
    void enQueue(LiQueue *&q,ElemType e)
    {
    	Qnode *p;
    	p=(Qnode*)malloc(sizeof(Qnode));//分配好空间以后，就把结构体中相应的值初始化
    	p->data=e;
    	p->next=NULL;
    	if(q->rear==NULL)//若链队为空，则新节点既是队首节点又是队尾节点
    	{
    		q->front=q->rear=p;//该链表头节点有数
    	}
    	else
    	{
    		q->rear->next=p;
    		q->rear=p;
    	}
    }
    
    bool deQueue(LiQueue *&q,ElemType &e)
    {
    	Qnode *t;
    	if(q->rear=NULL)//队列为空
    	{
    		return false;
    	}
    	t=q->front;//第一个数据节点
    	if(q->front==q->rear)//队列中只有一个节点时，链表的front可以存数！！！
    	{
    		q->front=q->rear=NULL;
    	}
    	else
    	{
    		q->front=q->front->next;//首先让front指向要被‘删除’数的后一个数，不给它‘出现’的机会，然后存在被删除数，最后释放‘该’内存
    	}
    	e=t->data;
    	free(t);
    	return true;
    }
    
    int main(void)
    {
    	system("pause");
    	return 0;
    }

![Center 1][]

五.循环列表的链式存储

#include<iostream>
    #include<cstdlib>
    
    typedef int ElemType;
    
    typedef struct qnode
    {
    	ElemType data;
    	struct qnode *next;
    	struct qnode *rear;
    }LinkList;
    
    void InitQueue(LinkList *&rear)//初始化队运算算法
    {
    	rear=NULL;//队列链表的初始化都是对尾(首)‘指挥官’
    }
    
    void enQueue(LinkList *&rear,ElemType x)//进队运算算法
    {
    	LinkList *p;
    	p=(LinkList *)malloc(sizeof(LinkList));
    	p->data=x;//该链表的头节点也是有值的
    	if(rear==NULL)//原链表为空
    	{
    		p->next=p;//构成循环链表
    		rear=p;
    	}
    	else
    	{
    		p->next=rear->next;//将*p节点插到*rear节点之后
    		rear->next=p;
    		rear=p;
    	}
    }
    
    bool deQueue(LinkList *&rear,ElemType &x)
    {
    	LinkList *q;
    	if(rear==NULL)//删除链表之前，检查该链表是否为空
    	{
    		return false;
    	}
    	//原队中只有一个节点，没有选择，只能删他
    	else if(rear->next==rear)//循环链表的特征
    	{
    		x=rear->data;
    		free(rear);//释放完rear的空间后，需对rear赋值
    		rear=NULL;
    	}
    	else//原队中有两个或两个以上的节点
    	{
    		q=rear->next;//从'头'开始删
    		x=q->data;
    		rear->next=q->next;//较常用
    		free(q);
    	}
    	return true;
    }
    
    bool queueEmpty(LinkList *rear)//判断链表是否为空
    {
    	return(rear==NULL);
    }
    
    int main(void)
    {
    	system("pause");
    	return 0;
    }

![Center 2][]

六.环形队列的顺序存储

#include<iostream>
    #include<cstdlib>
    
    typedef char ElemType;
    #define MaxSize 20
    
    typedef struct
    {
    	ElemType data[MaxSize];
    	int front,rear;
    }SqQueue;
    
    void InitQueue(SqQueue *&q)
    {
    	q=(SqQueue *)malloc(sizeof(SqQueue));
    	q->front=q->rear=0;//与单顺序表不同
    }
    
    void DestroyQueue(SqQueue *&q)
    {
    	free(q);
    }
    
    bool QueueEmpty(SqQueue *q)
    {
    	return(q->front==q->rear);
    }
    
    bool enQueue(SqQueue *&q,ElemType e)
    {
    	if((q->rear+1)%MaxSize==q->front)//判断队列表是否上溢,(q->rear+1)%MaxSize是为了让q->rear可以重新回到0下标，实现循环，循环表中的front下标中还是不‘存在’数
    	{
    		return false;
    	}
    	q->rear=(q->rear+1)%MaxSize;//尾坐标先+1,再存数
    	q->data[q->rear]=e;
    	return true;
    }
    
    bool deQueue(SqQueue *&q,ElemType &e)
    {
    	if(q->front==q->rear)//判断队列是否下溢
    	{
    		return false;
    	}
    	q->front=(q->front+1)%MaxSize;//同样地，先头坐标+1
    	e=q->data[q->front];//存在'消失'的数字
    	return true;
    }
    
    int main(void)
    {
    	system("pause");
    	return 0;
    }
    //当判断上溢时，需要判断rear的前面一个，即rear+1是否和front相等(所以就需要用到(q->rear+1)%MaxSize),如果相等则溢出，因为front坐标所指‘不放’数字；
    //当判断下溢时，需要判断rear是否与front相等，若相等，则相当于front把rear里的最后一个数也给'灭'了；
    //上溢出，rear'追'front;下溢出，front'追'rear;

![Center 3][]

[Center]: /images/20220715/8489964b0d1e4a3c972d6a00c81067aa.png
[Center 1]: /images/20220715/9f2acce45c3d4807b4361add2827bb79.png
[Center 2]: /images/20220715/0f7dfc28b47f4e5b8f40f14a383992d4.png
[Center 3]: /images/20220715/55353db0a4fd42d6aed770bc52ee6883.png