数据结构与算法简单了解（栈与队列）

栈

栈的定义

• 栈是限定仅在表尾进行插入与删除操作的线性表
• 我们把允许插入和删除的一端叫做栈顶，另一端叫做栈底，空栈是不含有任何数据元素的栈，栈又是后进先出的线性表
• 插入：进栈
• 删除：出栈

栈的出入变化

• 只要记住栈顶元素总是比其他元素先出栈就行了

栈的存储结构

1. 顺序存储结构
2. 链式存储结构

栈的顺序的存储结构

如果栈长度为MAX，空栈top（栈顶指针）为-1，满栈是MAX-1

栈的结构

typedef int Type   //Type类型根据实际情况定 
typedef struct
{
	Type data[10];
	int top;        //栈顶指针 
}SqStack;

进栈操作

Status Push(SqStack *s,Type e)
{
	if(s->top==9)   //栈满 
	{
		return ERROR;
	}
	s->top++;    //栈顶指针加一 
	s->data[s->top]=e;   //将新插入元素赋值给栈顶空间 
	return OK;
}

出栈操作

Status Pop(SqStack *s,Type *e)
{
	if(s->top==-1)   //栈满 
	{
		return ERROR;
	}
	*e=s->data[s->top];//将要删除的栈顶指针元素赋值给e 
	s->top--;    //栈顶指针减一 
	return OK;
} 

两栈共享空间

• 两栈相当于两个杯子，东西从杯底向杯口前进，东西就是栈顶指针
• 两个指针之间相差1，即top1+1=top2

typedef int Type   //Type类型根据实际情况定 
typedef struct
{
	Type data[10];
	int top1;        //栈1栈顶指针
	int top2;        //栈2栈顶指针
}SqStack;

Status Push(SqStack *s,Type e，int select)
{
	if(s->top1+1==s->top2)   //栈满 
	{
		return ERROR;
	}
	if(select==1)  //判断是栈1还是栈2中有东西进栈 
	{
		s->data[++s->top1]=e;
	}
	else if(select==2)
	{
		s->data[--s->top2]=e;
	} 
	return OK;
}

Status Pop(SqStack *s,Type *e，int select)
{
	if(select==1)  //判断是栈1还是栈2中有东西进栈 
	{
		if(s->top1==-1)
		{
			return ERROR;
		}
		*e=s->data[s->top1--];
	}
	else if(select==2)
	{
		if(s->top2==10)
		{
			return ERROR;
		}
		*e=s->data[s->top2++];
	} 
	return OK;
} 

栈的链式存储结构

栈的结构

typedef struct Node
{
    int data;
    struct Node *next;
}Node;
 
typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
}LinkStack;

进栈操作

int Push(LinkStack *S, int e)
{
    Node *st = (Node *)malloc(sizeof(Node));
    st->data = e;
    st->next = S->top;  //把当前的栈顶元素赋值给新结点的直接后继
    S->top = st;        //将新的结点st赋值给栈顶指针
    S->count++;
    return OK;
}

出栈操作

int Pop(LinkStack *S, int *e)
{
    Node *p;
 
    *e = S->top->data;
    p = S->top;                 //将栈顶结点赋值给p
    S->top = S->top->next;      //使得栈顶指针下移一位，指向后一结点
    free(p);                    //释放结点p
    S->count--;
    
    return OK;
}

队列

队列的定义

• 队列是只允许在一端进行插入操作，而另一端进行删除操作的线性表
• 队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队头
• 队列引入了一个队头指针front，队尾指针rear，front=rear时，队列为空队列，但这样会出现假溢出，所以产生了循环队列

循环队列

循环队列的定义

头尾相接的顺序存储队列叫做循环队列

循环队列满与空的判别

1. 设置一个标志变量，当front= =rear，则flag=0时队列空，当front==rear，且flag=1时队列满
2. 队列空时，条件是front==rear，队列满时，可以保留一个空间（这表示队列满时，数组还有一个空闲空间）

循环队列结构

typedef int Type
typedef struct
{
	Type data[MAX];
	int front;
	int rear;
} SqQueue;

Status InitQueue(SqQueue *Q)
{
	Q->front=0;
	Q->rear=0;
	return OK;
}

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

Status EnQueue(SqQueue *q,Type e)
{
	if((Q->rear+1)%MAX==Q->front)
	{
		return ERROR;
	}
	Q->data[Q->rear]=e;
	Q->rear=(Q->rear+1)%MAX;
	return OK;
}

Status DeQueue(SqQueue *q,Type *e)
{
	if(Q->rear==Q->front)
	{
		return ERROR;
	}
	*e=Q->data[Q->front];
	Q->front=(Q->front+1)%MAX;
	return OK;
}

队列的链式存储结构

• 队列的链式存储结构，可以尾进头出

队列的结构

typedef int Type

typedef struct Node
{
	Type data;
	struct Node *next;
} Node,*QueuePtr;

typedef struct
{
	QueuePtr front,rear;
} LinkQueue;

入队操作

Status EnQueue(LinkQueue *q,Type e)
{
	QueuePtr s=(QueuePtr)malloc(sizeof(Node))
	s->data=e;
	s->next=NULL;
	q->rear->next=s;//把拥有元素e新结点s赋值给原队尾结点的后继
	q->rear=s; //将s结点设为队尾结点
	return OK;
}

出队操作

Status DeQueue(LinkQueue *q,Type *e)
{
	QueuePtr p;
	if(q-front==q->rear)
	{
		return ERROR;
	}
	p=q->front->next;  //将要删除的队头结点暂存给p
	*e=p-data;         //将要删除的队头结点的值赋值给e
	q->front->next=p->next; //将原队头结点后继p->next赋值给头结点后继
	if(q->rear==p)  //若队头是队尾，则删除后将rear指向头结点
	{
		q->rear=q->front;
	}
	free(p);
	return OK;
}

栈和队列的应用

马踏棋盘

问题描述

将马放在国际象棋8×8棋盘某个方格中，马按走棋规则进行移动，要求每个方格只进入一次，走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线将数字1,2，…，64依次填入一个8×8的方阵并输出。

思路

递归

栈

文中源代码

源代码地址

• 
  简单栈
• 
  简单队列
• 
  马踏棋盘