数据结构-栈和队列

1、栈(stack)是限定仅在表尾进行插入和删除操作的线性表。 LIFO: Last In First Out 后进先出，　先进后出

栈，它是一个思想，“后进先出，先进后出”

栈顶(Top): 进行插入和删除操作的哪一端

栈底(Bottom):

增、删、改、查
"栈"如下的基本的操作:
		InitStack  初始化一个栈
		DestroyStack 销毁一个栈
		ClearStack 清空一个栈
		StackIsEmpty 判断一个栈是否为空
		StackLength 返回栈中的元素个数，即栈的长度
		GetTop  返回栈顶元素，但不出栈
		
		Pop 出栈，把栈顶元素给干掉
		Push 入栈，把一个元素加入到栈中去
		……

栈的实现:
	顺序栈: SeqStack
		用一组地址连续的存储单元来依次存储栈里面的每个元素有点类似于“数组”


伪代码实现：
typedef int SElemType; //栈中元素的类型
		//typedef void* SElemType; //栈中元素的类型
        #define STACK_MAX_LENGTH 1024
		//SElemType stack[STACK_MAX_LENGTH];
		//int top; //栈顶的下标
		
		typedef struct seqStack
		{
			//SElemType elem[STACK_MAX_LENGTH];
			SElemType *elem;
			int top ; //栈顶的下标
			
			
		}seqStack;

链式栈: LinkedStack
		用链表(单链表/双向链表)来实现
			
			“带头结点的单链表/双向链表”
		
		用一个“数据结点”来保存栈中的元素，
		栈中的元素之间通过链表链起来。
		
		用一个“头结点”去指向“栈顶”

		typedef int SElemType; //栈中元素的类型
		
		typedef struct node
		{
			SElemType data;
			struct node *next;
		}Node;

		struct LinkedStack
		{
			struct node *bottom ;//栈底元素指针，链表中的第一个结点
			struct node *top; //栈顶元素指针，链表中的最后一个结点
			
			int num; //栈中元素个数
			
			
		};

链式栈

LinkedStack.c

#include 
#include 
#include "LinkedStack.h"

LinkedStack InitStack()
{
	LinkedStack s =malloc(sizeof(LinkedStack));
	s->bottom=s->top=NULL;
	s->num=0;
	return s;
}

void DestroyStack(LinkedStack s)
{
	if(s==NULL)
	{
		return;
	}
	
	ClearStack(s);
	free(s);
}

void ClearStack(LinkedStack s)
{
	if(s==NULL||s->bottom==NULL)
	{
		return;
	}
	Node p = s->bottom;
	while(p)
	{
		s->bottom=p->next;
		p->next=NULL;
		free(p);
		p=s->bottom;
	}
	s->top=NULL;
	s->num=0;
}

int StackIsEmpty(LinkedStack s)
{
	if(s==NULL||s->num==0)
	{
		return 1;
	}
	return 0;
}


int StackLength(LinkedStack s)
{
	if(StackIsEmpty(s))
	{
		return 0;
	}
	return s->num;
}

int GetTop(LinkedStack s,SElemType* e)
{
	if(StackLength(s)==0)
	{
		return 0;
	}
	*e=s->top->data;
	return 1;
}

int Pop(LinkedStack s,SElemType* e)
{
	if(StackLength(s)==0)
	{
		return 0;
	}
	*e=s->top->data;
	//删除栈顶的那个结点
	if(s->num==1)
	{
		s->bottom=NULL;
		free(s->top);
		s->top=NULL;
	}
	Node pr = s->bottom;	//指向栈顶元素的前面那一个
	while(pr&&pr->next!=s->top)
	{
		pr=pr->next;
	}
	pr->next=NULL;
	free(s->top);
	s->top=pr;
	s->num--;
	return 1;
}

int Push(LinkedStack s,SElemType e)
{
	if(s==NULL)
	{
		return 0;
	}
	Node p = malloc(sizeof(Node));
	p->data=e;
	p->next=NULL;
	if(s->top==NULL)
	{
		s->top=p;
		s->bottom=p;
	}
	else
	{
		s->top->next=p;
		s->top=p;
	}
	s->num++;
	return 1;
}

int main()
{
	return 0;
}

LinkedStack.h

#ifndef __LINKEDSTACK_H__
#define __LINKEDSTACK_H__

typedef int SElemType; //栈中元素的类型
		
typedef struct node
{
	SElemType data;
	struct node *next;
}*Node;

typedef struct linkedStack
{
	struct node *bottom ;//栈底元素指针，链表中的第一个结点
	struct node *top; //栈顶元素指针，链表中的最后一个结点
	

	int num; //栈中元素个数
	
	

}*LinkedStack;


#endif

相关练习：利用栈求一个表达式的值，表达式的值以字符串的形式写出，如：“1+20*4”=81；

main.c

#include 
#include 
#include "SeqStack.h"

int is_digtal(char c)
{
	if(c>='0'&&c<='9')
	{
		return 1;
	}
	return 0;
}
int is_operator(char c)
{
	if(c=='+'||c=='-'||c=='*'||c=='/'||c=='%')
	{
		return 1;
	}
	return 0;
}
int cal(int a,int b,char op)
{
	switch(op)
	{
		case '+':
			return a+b;
		case '-':
			return a-b;
		case '*':
			return a*b;
		case '/':
			return a/b;
		case '%':
			return a%b;
		default:
			printf("Not Support!n");
			exit(-1);
	}
}

int compare(char op1,char op2)
{
	if((op1=='*'||op1=='/'||op1=='%')&&(op2=='+'||op2=='-'))
	{
		return 1;
	}
	return 0;
}

int expression(char* e)
{
	seqStack* s1=InitStack(1024);	//操作数 栈s1
	seqStack* s2=InitStack(1024);	//运算符 栈s2

	while(*e)
	{
		//先找到第一个操作数
		while(!is_digtal(*e))
		{
			e++;
		}
		int s=0;
		int d=0;
		while(is_digtal(*e))
		{
			d=*e-'0';
			s=s*10+d;
			e++;
		}
		//操作数就解析出来，保存在s中,
		//对于操作数则直接入栈
		Push(s1, s);
		//操作数后面可能会有多余的空白符
		while(*e&&!is_operator(*e))
		{
			e++;	//此时字符指针就会指向操作符
		}
		
		int op=*e;
		while(1)
		{
			int op_top;
			GetTop(s2, &op_top);
			if(StackIsEmpty(s2)||compare(op,op_top))
			{
				Push(s2,op);
				break;
			}
			else
			{
				int a,b;
				int op_top;
				Pop(s1,&a);
				Pop(s1,&b);
				Pop(s2,&op_top);
				printf("%d %c %d = %dn",a,op_top,b,cal(a,b,op_top));
				Push(s1,cal(a,b,op_top));
			}
		}
	}
	while(!StackIsEmpty(s2))
	{
		int a,b;
		int op_top;
		Pop(s1,&a);
		Pop(s1,&b);
		Pop(s2,&op_top);
		printf("%d %c %d = %dn",a,op_top,b,cal(a,b,op_top));
		Push(s1,cal(a,b,op_top));
	}
	//最终的结果是保存在s1中
	int r;
	Pop(s1,&r);
	DestroyStack(s1);
	DestroyStack(s2);
	return r;
}
int main()
{
	char* s="1+30*4+6";
	printf("%dn",expression(s));
	return 0;
}

SeqStack.c

#include 
#include 

#include "SeqStack.h"



seqStack* InitStack(int max_len)
{
	seqStack* s = malloc(sizeof(seqStack));

	s->elem = malloc(max_len * sizeof(SElemType));
	s->max_len = max_len;


	s->top = -1;
			// top 保存的栈顶元素的下标
			// top = -1时，表示栈是一个空栈(什么元素都没有)
			// top++
			// elem[top] = e
	
	return s;

}



void DestroyStack(seqStack *s)
{
	if (s == NULL)
	{
		return ;
	}

	if (s->elem)
	{
		free(s->elem);
	}
	
	free(s);

}


void ClearStack(seqStack *s)
{

	if (s)
	{
		s->top = -1;
	}

}



int StackIsEmpty(seqStack *s)
{
	if (s == NULL )
	{
		return 1;
	}


	return  s->top == -1 ? 1 : 0;

}



int StackLength(seqStack *s)
{
	if (s == NULL)
	{
		return 0;
	}


	return s->top + 1;

}


int GetTop(seqStack *s,   SElemType *e)
{
	if (s == NULL || s->top == -1 || e == NULL)
	{
		return  0;
	}

	*e = s->elem[s->top];
	
	return 1;

}


int Pop(seqStack *s,   SElemType *e)
{
	if (s == NULL || s->top == -1 || e == NULL)
	{
		return	0;
	}
	

	*e = s->elem[s->top];
	s->top--; //出栈
	
	return 1;

}



int  Push(seqStack *s,   SElemType e)
{
	if (s == NULL || s->top == s->max_len - 1)
	{
		return 0;
	}

	s->top ++;
	s->elem[s->top] = e;
	
	return 1;

}

SeqStack.h

#ifndef __SEQSTACK_H__
#define __SEQSTACK_H__



typedef int SElemType; //栈中元素的类型
//typedef void* SElemType; //栈中元素的类型


#define STACK_MAX_LENGTH 1024
//SElemType stack[STACK_MAX_LENGTH];
//int top; //栈顶的下标

typedef struct seqStack
{
	//SElemType elem[STACK_MAX_LENGTH];
	SElemType *elem; //指向一组连续的地址空间，用来存放栈中的元素
	int top ; //栈顶的下标

	int max_len; //elem指向的空间最大存放的元素个数
	

}seqStack;


seqStack* InitStack(int max_len);


void DestroyStack(seqStack *s);




void ClearStack(seqStack *s);


int StackIsEmpty(seqStack *s);



int GetTop(seqStack *s,   SElemType *e);

int Pop(seqStack *s,   SElemType *e);



int  Push(seqStack *s,   SElemType e);


int is_digtal(char c);
int is_operator(char c);
int cal(int a,int b,char op);
int compare(char op1,char op2);
int expression(char* e);




#endif

2、队列(Queue)是一种先进先出(FIFO: First In First Out)的线性表。

它只允许在表的一端进行插入，而在另外一端删除元素。

队尾(rear): 允许插入元素的一端

队头(front): 允许删除元素的一端。

“队列思想”：　先进先出。“排队论”
队列操作:
	InitQueue: 分配并初始化一个队列
	DestroyQueue: 销毁一个队列
	ClearQueue: 清空队列 -> 变成一个空队列
	QueueIsEmpty: 判断一个队列是否为空
	QueueLength: 返回队列中元素的个数，即队列的长度
	GetHead:  返回值队列队头元素，但不出队
	EnQueue:入队
	DeQueue: 出队

实现队列这种数据结构：

	顺序队列:
		用一组地址连续的存储空间来存储队列中的元素。
		“循环队列”
		
		数据结构
			typedef int QElemType; //队列元素的类型
			
			typedef struct SqQueue
			{
				QElemType *data ; //指向一段连续的存储单元
								 //用来存储队列中的元素
				
				int rear; //队尾下标，下一个入队元素的下标
				int front; //队头下标，下一个出队元素的下标　
				
				int max_len; //表示data指向的存储空间最大的元素个数
				
				int avail_len; //表示当前队列中的元素个数
							//avail_len == 0 => 队列为空
							//avail_len == max_len =>队列为满
							
				
			}SqQueue;


链式队列
		用头结点的单链表/双向链表
typedef int QElemType; //队列元素的类型
		
typedef struct QNode
{
	QElemType data;
			
	struct QNode *next;
}QNode;

typedef struct LinkedQueue
{
	struct QNode *first; //指向队头元素结点
	struct QNode *last;  //指向队尾元素结点
			
	int num; //队列中元素的个数
			
	
}LinkedQueue;

SqQueue.c

#include 
#include 
#include "sqQueue.h"

SqQueue InitSqQueue(int max_len)
{
	SqQueue q = malloc(sizeof(SqQueue));
	q->avail_len=0;
	q->rear=0;
	q->front=0;
	q->max_len=max_len;
	return q;
}

void DestroySqQueue(SqQueue q)
{
	if(q==NULL)
	{
		return 0;
	}
	if(q->data)
	{
		free(q->data);
	}
	q->data=NULL;
	q->front=q->rear=0;
	q->max_len=0;
	free(q);
}

int ClearSqQueue(SqQueue q)
{
	if(q==NULL)
	{
		return;
	}
	q->rear=q->front=0;//进行逻辑上的一个清空
	q->avail_len=0;
	return 1;
}

int SqQueueEmpty(SqQueue q)
{
	if(q==NULL||q->data==NULL)
	{
		return 1;
	}
	return (q->avail_len==0)?1:0;
}
int SqQueueLength(SqQueue q)
{
	if(q==NULL||q->data==NULL)
	{
		return 0;
	}
	return q->avail_len;
}

int EnQueue(SqQueue q,QElemType e)
{
	if(q==NULL||q->data==NULL||q->avail_len==q->max_len)
	{
		return 0;
	}
	q->data[q->rear]=e;
	q->rear++;
	if(q->rear==q->max_len)
	{
		q->rear=0;
	}
	q->avail_len++;
	return 1;
}

int DeQueue(SqQueue q,QElemType* e)
{
	if(q==NULL||q->data==NULL||q->avail_len==0)
	{
		return 0;
	}
	*e = q->data[q->front];
	q->front++;
	if(q->front==q->max_len)
	{
		q->front=0;
	}
	q->avail_len--;
	return 1;
	
}

int GetHead(SqQueue q,QElemType *e)
{
	if(q==NULL||q->data==NULL||q->avail_len==0)
	{
		return 0;
	}
	*e=q->data[q->front];
	return 1;
}

int main()
{
	return 0;
}

SqQueue.h

#ifndef __SQQUEUE_H__
#define __SQQUEUE_H__

typedef int QElemType;	//队列元素的类型
typedef struct sqQueue
{
	QElemType* data;	//指向一段连续的存储单元，用来存储队列中的元素
	int rear;//队尾下标，下一个入队元素的下标
	int front;//队头下标，下一个出队元素的下标
	int max_len;//表示data指向的存储空间最大的元素个数
	int avail_len;//表示当前队列中的元素个数
				//avail_len==0=>队列为空
				//avail_len==max_len=>队列为满
}*SqQueue;


#endif

数据结构-栈和队列

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