[数据结构与算法]数据结构——栈和队列操作的实现

数据结构——栈和队列操作的实现

栈和队列都是特殊的线性表，其存储结构也分为顺序存储和链式存储。下面的内容主要是以基本算法的实现为主，如有不对或者不妥的地方，还请各位大神指出。

Part 1 栈的操作实现

1.1 顺序栈

关于顺序栈，这里介绍的算法有：初始化顺序栈、销毁顺序栈、清空顺序栈、求顺序栈的长度、判断顺序栈是否为空、元素入栈、元素出栈和获取栈顶元素。

#include <bits/stdc++.h>
#define MAXSIZE 100
#define Status int
#define ERROR -1
#define OK 1
#define OVERFLOW -1
using namespace std;

typedef struct
{
	int a;
}SElemType;
typedef struct
{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;

void Menu()
{
	cout<<"栈（顺序栈）操作的实现"<<endl;
	cout<<"1.初始化一个空栈"<<endl;
	cout<<"2.销毁顺序栈"<<endl;
	cout<<"3.清空顺序栈"<<endl;
	cout<<"4.求栈的长度"<<endl;
	cout<<"5.判断栈是否为空"<<endl;
	cout<<"6.元素入栈"<<endl;
	cout<<"7.元素出栈"<<endl;
	cout<<"8.获取栈顶元素"<<endl;
	cout<<"0.退出"<<endl;
	cout<<"请选择操作：";
}

Status InitStack(SqStack &S)
{
	S.base=new SElemType[MAXSIZE];
	if (!S.base)
		return ERROR;
	S.top=S.base;
	S.stacksize=MAXSIZE;
	return OK;
}

bool StackEmpty(SqStack S)
{
	if (S.top==S.base)
		return true;
	else
		return false;
}

int StackLength(SqStack S)
{
	return S.top-S.base;
}

Status ClearStack(SqStack &S)
{
	if (S.base)
		S.top=S.base;
	return OK;
}

Status DestroyStack(SqStack &S)
{
	if (S.base)
	{
		delete S.base;
		S.stacksize=0;
		S.base=S.top=NULL;
	}
	return OK;
}

Status Push(SqStack &S,SElemType e)
{
	if (S.top-S.base==S.stacksize)
		return ERROR;
	*S.top++=e;
	return OK;
}

Status Pop(SqStack &S,SElemType &e)
{
	if (S.top==S.base)
		return ERROR;
	e=*--S.top;
	return OK;
}

SElemType GetTop(SqStack S,SElemType &e)
{
	if (S.top==S.base)
		e.a=ERROR;
	e=*(S.top-1);
	return e;
}

void PrintStack(SqStack S)
{
	SElemType e;
	cout<<"\n当前栈中元素为：";
	while (!StackEmpty(S))
	{
		cout<<GetTop(S,e).a<<" ";
		Pop(S,e);
	}
	cout<<endl; 
}

int main()
{
	while (true)
	{
		system("cls");
		SqStack S;
		SElemType e;
		Menu();
		int x;
		cin>>x;
		switch (x)
		{
			case 1:
				if (InitStack(S)==1)
					cout<<"\n初始化顺序栈成功！\n"<<endl;
				else
					cout<<"\n初始化顺序栈失败！\n"<<endl;
				break;
			case 2:
				DestroyStack(S);
				cout<<"\n销毁顺序栈成功！\n"<<endl;
				break;
			case 3:
				ClearStack(S);
				cout<<"\n清空顺序栈成功！\n"<<endl;
				break;
			case 4:
				cout<<"\n当前顺序栈长度为："<<StackLength(S)<<"\n"<<endl;
				break;
			case 5:
				if (StackEmpty(S)==true)
					cout<<"\n顺序栈为空！\n"<<endl;
				else
					cout<<"\n顺序栈非空！\n"<<endl;
				break;
			case 6:
				cout<<"\n输入压入栈中元素：";
				cin>>e.a;
				if (Push(S,e)==1)
				{
					cout<<"\n元素插入成功！\n"<<endl;
					PrintStack(S);
				}
				else
					cout<<"\n插入失败！\n"<<endl;
				break;
			case 7:
				if (Pop(S,e)==1)
				{
					cout<<"\n删除栈顶元素成功！\n"<<endl;
					PrintStack(S);
				}
				else
					cout<<"\n删除元素失败！\n"<<endl;
				break;
			case 8:
				if (GetTop(S,e).a!=-1)
					cout<<"\n栈顶元素为："<<GetTop(S,e).a<<"\n"<<endl;
				else
					cout<<"\n栈顶元素不存在！\n"<<endl;
				break;
			case 0:
				exit(0);
		}
		system("pause");
	}
	return 0;
}

1.2 链栈

链栈并不经常用，这里实现以下算法：初始化链栈、判断链栈是否为空、元素入栈、元素出栈和获取栈顶元素。

#include <bits/stdc++.h>
#define Status int
#define ERROR -1
#define OK 1
#define OVERFLOW -1
using namespace std;

typedef struct
{
	int a;
}SElemType; 
typedef struct StackNode
{
	SElemType data;
	struct StackNode *next;
}StackNode,*LinkStack;

void Menu()
{
	cout<<"栈（链栈）操作的实现"<<endl;
	cout<<"1.初始化一个空栈"<<endl;
	cout<<"2.判断栈是否为空"<<endl;
	cout<<"3.元素入栈"<<endl;
	cout<<"4.元素出栈"<<endl;
	cout<<"5.获取栈顶元素"<<endl;
	cout<<"0.退出"<<endl;
	cout<<"请选择操作：";
}

Status InitStack(LinkStack &S)
{
	S=NULL;
	return OK;
}

bool StackEmpty(LinkStack S)
{
	if (S==NULL)
		return true;
	else
		return false;
}

Status Push(LinkStack &S,SElemType e)
{
	LinkStack p=new StackNode;
	p->data=e;
	p->next=S;
	S=p;
	return OK;
}

Status Pop(LinkStack &S,SElemType &e)
{
	if (S==NULL)
		return ERROR;
	e=S->data;
	LinkStack p=new StackNode;
	p=S;
	S=S->next;
	delete p;
	return OK;
}

SElemType GetTop(LinkStack S)
{
	if (S==NULL)
		S->data.a=ERROR;
	return S->data;
}

void PrintStack(LinkStack S)
{
	SElemType e;
	cout<<"当前栈中元素为：";
	while (!StackEmpty(S))
	{
		cout<<GetTop(S).a<<" ";
		Pop(S,e);
	}
	cout<<endl;
}

int main()
{
	while (true)
	{
		system("cls");
		LinkStack S;
		SElemType e;
		Menu();
		int x;
		cin>>x;
		switch (x)
		{
			case 1:
				if (InitStack(S)==1)
					cout<<"\n初始化链栈成功！\n"<<endl;
				else
					cout<<"\n初始化链栈失败！\n"<<endl;
				break;
			case 2:
				if (StackEmpty(S)==true)
					cout<<"\n链栈为空！\n"<<endl;
				else
					cout<<"\n链栈非空！\n"<<endl;
				break;
			case 3:
				cout<<"\n输入压入栈中元素：";
				cin>>e.a;
				if (Push(S,e)==1)
				{
					cout<<"\n元素插入成功！\n"<<endl;
					PrintStack(S);
				}
				else
					cout<<"\n插入失败！\n"<<endl;
				break;
			case 4:
				if (Pop(S,e)==1)
				{
					cout<<"\n删除栈顶元素成功！\n"<<endl;
					PrintStack(S);
				}
				else
					cout<<"\n删除元素失败！\n"<<endl;
				break;
			case 5:
				if (GetTop(S).a!=-1)
					cout<<"\n栈顶元素为："<<GetTop(S).a<<"\n"<<endl;
				else
					cout<<"\n栈顶元素不存在！\n"<<endl;
				break;
			case 0:
				exit(0);
		}
		system("pause");
	}
	return 0;
}

1.3 栈的应用——表达式求值

表达式求值问题是栈的一个最常见的应用，具体的原理在这里不做描述。在下面的代码中，输入的所有数字符、运算符都要在一行内进行输入，否则原栈会把回车键也算在内，影响最终的结果。输入‘#’表示结束。

#include <bits/stdc++.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define ERROR -1
#define OK 1
typedef int Status;
typedef char ElemType;
typedef struct
{
	ElemType *base;
	ElemType *top;
	int stacksize;
}SqStack;

Status InitStack(SqStack &S)
{
	S.base=new ElemType[STACK_INIT_SIZE];
	if (!S.base)
		return ERROR;
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return OK;
}

ElemType GetTop(SqStack s)
{
	ElemType e;
	if(s.top==s.base)
		e=ERROR;
	e=*(s.top-1);
	return e;
}
Status Push(SqStack &s,ElemType e)
{
	if(s.top-s.base>=s.stacksize)
	{
		s.base=(ElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(ElemType));
		if(!s.base)
			return ERROR;
		s.top=s.base+s.stacksize; 
		s.stacksize+=STACKINCREMENT;
	}
	*s.top++=e;
	return OK;
}
Status Pop(SqStack &s,ElemType &e)
{
	if(s.top==s.base)
		return ERROR;
	e=*--s.top;
	return OK;
}

Status In(ElemType c)
{
    if(c=='+'||c=='-'||c=='*'||c=='/'||c=='#'||c=='('||c==')'||c=='['||c==']')
        return 1;
    else
        return 0;
}

char Precede(ElemType a,ElemType b)
{
    if(a=='+'||a=='-')
	{
        if(b=='+'||b=='-'||b=='>'||b=='#'||b==')'||b==']')
            return '>';
        else
			return '<';
    }
    if(a=='*'||a=='/')
	{
        if(b=='('||b=='[')
            return '<';
        else
			return '>';
    }
    if(a=='('){
        if(b==')')
            return '=';
        else
			return '<';
    }
    if(a=='[')
	{
        if(b==']')
            return '=';
        else
			return '<';
    }
    if(a=='#')
	{
        if(b=='#')
            return '=';
        else
			return '<';
    }
}

ElemType Operate(ElemType a,ElemType x,ElemType b)
{
	switch (x)
	{
		case '+':
			return a+b;
    	case '-':
			return a-b;
    	case '*':
        	return a*b;
    	case '/':
        	return a/b;
	}
}

ElemType EvaluateExpression()
{
	SqStack OPTR,OPND;
	char c,x;
	InitStack(OPTR);
	Push(OPTR,'#'); 
	InitStack(OPND);
	c=getchar();
	while(c!='#'||GetTop(OPTR)!='#')
	{
		if(!In(c))
		{
			Push(OPND,c-'0');
			c=getchar();
		}
		else
		{
			switch(Precede(GetTop(OPTR),c))
			{
				case '<':
					Push(OPTR,c);
					c=getchar();
					break;
				case '=':
					Pop(OPTR,x);
					c=getchar();
					break;
				case '>':
					Pop(OPTR,x);
					ElemType a,b;
					Pop(OPND,b);
					Pop(OPND,a);
					Push(OPND,Operate(a,x,b));
					break;
			}
		}
	}
	return GetTop(OPND);
}
int main()
{
	printf("%d\n",EvaluateExpression());
	return 0;
}

Part 2 队列的操作实现

2.1 顺序队列

关于顺序队列，这里主要实现循环队列的算法，循环队列相较于普通的队列，能够很好的使用队列中的空间。这一部分有以下的算法实现：初始化顺序队列、求顺序队列的长度、元素入队列、元素出队列和获取队头元素。

#include <bits/stdc++.h>
#define MAXSIZE 100
#define Status int 
#define OK 1
#define ERROR -1
using namespace std;

typedef struct
{
	int a;
}QElemType;
typedef struct
{
	QElemType *base;
	int front;
	int rear;
}SqQueue;

void Menu()
{
	cout<<"队列（顺序队列）操作的实现"<<endl;
	cout<<"1.初始化一个空队列"<<endl;
	cout<<"2.求队列的长度"<<endl;
	cout<<"3.元素入队列"<<endl;
	cout<<"4.元素出队列"<<endl;
	cout<<"5.获取队头元素"<<endl;
	cout<<"0.退出"<<endl;
	cout<<"请选择操作：";
}

Status InitQueue(SqQueue &Q)
{
	Q.base=new QElemType[MAXSIZE];
	if (!Q.base)
		return ERROR;
	Q.front=0;
	Q.rear=0;
	return OK;
}

int QueueLength(SqQueue Q)
{
	return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

Status EnQueue(SqQueue &Q,QElemType e)
{
	if ((Q.rear+1)%MAXSIZE==Q.front)
    	return ERROR;
	Q.base[Q.rear]=e;
	Q.rear=(Q.rear+1)%MAXSIZE;
	return OK;
}

Status DeQueue(SqQueue &Q,QElemType &e)
{
	if (Q.front==Q.rear)
		return ERROR;
	e=Q.base[Q.front];
	Q.front=(Q.front+1)%MAXSIZE;
	return OK;
}

QElemType GetHead(SqQueue Q)
{
	if (Q.front!=Q.rear)
		return Q.base[Q.front];
}

void PrintQueue(SqQueue Q)
{
	QElemType e;
	cout<<"\n当前队列元素为：";
	while (Q.front!=Q.rear)
	{
		DeQueue(Q,e);
		cout<<e.a<<" ";
	}
	cout<<endl;
}

int main()
{
	while (true)
	{
		system("cls");
		SqQueue Q;
		QElemType e;
		Menu();
		int x;
		cin>>x;
		switch (x)
		{
			case 1:
				if (InitQueue(Q)==1)
					cout<<"\n初始化队列成功！\n"<<endl;
				else
					cout<<"\n初始化队列失败！\n"<<endl;
				break;
			case 2:
				cout<<"\n当前队列长度为："<<QueueLength(Q)<<"\n"<<endl;
				break;
			case 3:
				cout<<"\n输入进入队中元素：";
				cin>>e.a;
				if (EnQueue(Q,e)==1)
				{
					cout<<"\n元素插入成功！\n"<<endl;
					PrintQueue(Q);
				}
				else
					cout<<"\n插入失败！\n"<<endl;
				break;
			case 4:
				if (DeQueue(Q,e)==1)
				{
					cout<<"\n删除元素成功！\n"<<endl;
					PrintQueue(Q);
				}
				else
					cout<<"\n删除元素失败！\n"<<endl;
				break;
			case 5:
				cout<<"\n队头元素为："<<GetHead(Q).a<<"\n"<<endl;
				break;
			case 0:
				exit(0);
		}
		system("pause");
	}
	return 0;
}

2.2 链队列

链队列相比较于顺序队列，多了一组结构体，其基本的操作可以与线性表中的链表相对应，这里实现以下的几个算法：初始化一个链队列、销毁链队列、判断链队列是否为空、获取队头元素、元素入队和元素出队。

#include <bits/stdc++.h>
#define Status int 
#define OK 1
#define ERROR -1
using namespace std;

typedef struct
{
	int a;
}QElemType;
typedef struct QNode
{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

void Menu()
{
	cout<<"队列（链队）操作的实现"<<endl;
	cout<<"1.初始化一个空队列"<<endl;
	cout<<"2.销毁队列"<<endl;
	cout<<"3.判断链队是否为空"<<endl;
	cout<<"4.获取队头元素"<<endl;
	cout<<"5.元素入队"<<endl;
	cout<<"6.元素出队"<<endl;
	cout<<"0.退出"<<endl;
	cout<<"请选择操作：";
}

Status InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
	if (!Q.front)
		return ERROR;
	Q.front->next=NULL;
	return OK;
}

Status DestroyQueue(LinkQueue &Q)
{
	while (Q.front)
	{
		Q.rear=Q.front->next;
		delete Q.front;
		Q.front=Q.rear;
	}
	return OK;
}

bool QueueEmpty(LinkQueue Q)
{
	return Q.front==Q.rear;
}

Status GetHead(LinkQueue Q,QElemType &e)
{
	if (Q.front==Q.rear)
		return ERROR;
	e=Q.front->next->data;
	return OK;
}

Status EnQueue(LinkQueue &Q,QElemType e)
{
	QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
	if (!p)
		return ERROR;
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return OK;
}

Status DeQueue(LinkQueue &Q,QElemType &e)
{
	if (Q.front==Q.rear)
		return ERROR;
	QueuePtr p=new QNode;
	p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if (Q.rear==p)
		Q.rear=Q.front;
	delete p;
	return OK;
}

void PrintQueue(LinkQueue Q)
{
	QNode *p=Q.front->next;
	cout<<"\n当前队列元素为：";
	while (p) 
	{
		cout<<p->data.a<<" ";
		p=p->next;
	}
	cout<<endl;
}

int main()
{
	while (true)
	{
		system("cls");
		LinkQueue Q;
		QElemType e;
		Menu();
		int x;
		cin>>x;
		switch (x)
		{
			case 1:
				if (InitQueue(Q)==1)
					cout<<"\n初始化队列成功！\n"<<endl;
				else
					cout<<"\n初始化队列失败！\n"<<endl;
				break;
			case 2:
				if (DestroyQueue(Q)==1)
					cout<<"\n销毁队列成功！\n"<<endl;
				else
					cout<<"\n销毁队列失败！\n"<<endl;
				break;
			case 3:
				if (!QueueEmpty(Q))
					cout<<"\n链队列为空！\n"<<endl;
				else
					cout<<"\n链队列不为空！\n"<<endl;
				break; 
			case 4:
				if (GetHead(Q,e)==1) 
					cout<<"\n队头元素为："<<e.a<<"\n"<<endl;
				else
					cout<<"\n获取队头元素失败！\n"<<endl;
				break;
			case 5:
				cout<<"\n输入进入队中元素：";
				cin>>e.a;
				EnQueue(Q,e);
				cout<<"\n元素插入成功！\n"<<endl;
				PrintQueue(Q);
				break;
			case 6:
				if (DeQueue(Q,e)==1)
				{
					cout<<"\n删除元素成功！\n"<<endl;
					PrintQueue(Q);
				}
				else
					cout<<"\n删除元素失败！\n"<<endl;
				break;
			
			case 0:
				exit(0);
		}
		system("pause");
	}
	return 0;
}

Part 3 递归

递归算法是这一章里一个比较重要的算法，其基本的思想为：自己调用自己。下面举几个比较简单的例子，带大家感受一下递归算法及其操作的过程。

1.斐波那契数列

long Fib(long n)
{
	if (n<=2)
		return 1;
	else
		return Fib(n-1)+Fib(n-2);
}

在这一段算法中，可以完整的实现斐波那契数列的通式：Fib(n)=Fib(n-1)+Fib(n-2)。该递归算法的特点是：从n开始，一层一层进行运算，最后将所得到的数据依次相加，得到最后的答案。

2.Hanoi塔问题

void move(char x, char y)
{
	printf("%c--->%c",x,y);
}
void Hanoi(int n,char A,char B,char C)
{
	if(n==1)
  		move(A,C);
  	else
  	{
  		hanoi(n-1,A,C,B);
  		move(A,C);
  		hanoi(n-1,B,A,C);
  	}
}

这一段代码的意思相信大家都明白，一个简单的递归算法实现了Hanoi塔问题的答案，主要的步骤就是：
hanoi(n-1,A,C,B); move(A,C); hanoi(n-1,B,A,C);
这三句话展示了Hanoi塔的算法步骤，经过move函数的输出，大家就会明白每一步的操作过程。