BDS之栈与队列

栈

    栈是限定仅在表尾进行插入和删除操作的线性表。可以看做是一种特殊的线性表，它按照先进后出的原则存储数据。更加的抽象的来说，栈具有记录的功能，最典型的栈的应用就是计算机中进程地址区间的栈区，这块区域被组织成栈的结构，供函数调用使用，可以记录函数在调用中相关的一些信息。一般分为顺序栈和链式栈，顺序栈是基于线性顺序表，而链式栈基于链表。                                          

                                                     栈结构示意图 下面看下顺序栈的简单实现：

#define STATCK_INIT_SIZE 10
#define STACK_INCREMENT 2

typedef unsigned int size_t;
struct SqStack
{
	SElemType *base;
	SElemType *top;
	size_t	  stack_size;
};
//初始化
Status init_stack(SqStack* pS)
{
	assert(pS);
	if(!(pS->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)))){
		return ERROR;
	}
	pS->top = pS->base;
	pS->stack_size = STACK_INIT_SIZE;
	return OK;
}
//销毁栈
void destroy_stack(SqStack* pS)
{
	assert(pS);
	free(pS->base);
	pS->top = pS->base = NULL;
	pS->stackSize = 0;
}
//判断栈是否为空
Boolean is_empty(SqStack* pS)
{
	assert(pS);
	if(pS->top == pS->base)
		return TRUE;
	else
		return FALSE;
}
//栈元素个数
size_t get_length(SqStack* pS)
{
	assert(pS);
	return (pS->top - pS->base);
}
//获取栈顶元素
Status get_top(SqStack* pS,SElemType* pe)
{
	assert(pS);
	if(pS->top>pS->base){
		*pe = *(pS->top-1);
		return OK;
	}else{
		return ERROR;
	}		
}
//入栈
void push(SqStack* pS,SElemType e)
{
	assert(pS);
	if(pS->top-pS->base == pS->stack_size){
		pS->base = (SElemType*)realloc(pS->base,(pS->stack_size + STACK_INCREMENT)* \ 
						sizeof(SElemType));
		if(!pS->base)
			return ERROR;
		pS->top = pS->base + pS->stack_size;
		pS->stack_size += STACK_INCREMENT;
	}
	*(pS->top)++ = e;
}
//出栈
Status pop(SqStack* pS,SElemType* pe)
{
	assert(pS);
	if(pS->top == pS->base)
		return ERROR;
	*pe = *--pS->top;
	return OK;

}
void traverse(SqStack* pS,void(* visit)(SElemType))
{
	assert(pS);
	while(pS->top>pS->base)
		visit(*pS->base++);
}
           

可以看到，栈同线性顺序表相比，在内存分配机制上类似，其主要的区别在于存储数的方式不同，它总是通过栈顶来操作数据，所以相比来说操作更加简单。 栈的应用比较广泛，常见的有数制转换，括号匹配检测，迷宫求解，表达式求值等等。

队列

    相比栈，队列是一种先进先出(FIFO)的特殊线性结构，即从队尾插入元素，从队首移除元素。同样地，从实现上来讲可以分为顺序队列和链队列。从结构 上来讲可分为单链队列(基于单链表的链式结构)，循环队列，顺序队列(基于数组)。下图展示了队列结构和循环队列的示意图。

下面是循环队列的简单实现：

#define MAX_QUEUE_SIZE 5
struct sq_queue
{
	QElemType *base;
	int front;
	int rear;
};

Status init_queue(sq_queue* Q)
{
	assert(Q);
	Q->base = (QElemType*)malloc(MAX_QUEUE_SIZE*sizeof(QElemType));
	if(!Q->base)
		return ERROR;
	Q->front = Q->rear = 0;
	return OK;
}

void destroy_queue(sq_queue* Q)
{
	assert(Q);
	if(Q->base){
		free(Q->base);
		Q->base = NULL;
	}
	Q->front = Q->rear = 0;
}

void clear_queue(sq_queue* Q)
{
	Q->front = Q->rear = 0;
}

bool queue_empty(sq_queue Q)
{
	return Q.front == Q.rear ? true : false;
}

bool queue_fill(sq_queue Q)
{
	return (Q.rear+1)%MAX_QUEUE_SIZE == Q.front ? true :false;
}

size_t queue_length(sq_queue Q)
{
	return (Q.rear-Q.front+MAX_QUEUE_SIZE)%MAX_QUEUE_SIZE ;
}
//队尾入列
Status push_back(sq_queue* Q,QElemType e)
{
	assert(Q);
	if(queue_fill(*Q))
		return ERROR;
	*(Q->base+Q->rear)= e;
	Q->rear=(Q->rear+1)%MAX_QUEUE_SIZE;
	return OK;
}
//队头出列
Status pop_front(sq_queue* Q,QElemType* pe)
{
	assert(Q);
	if(queue_empty(*Q))
		return ERROR;
	*pe=*(Q->base+Q->front);
	Q->front = (Q->front+1)%MAX_QUEUE_SIZE;
	return OK;
}

QElemType front(sq_queue Q)
{
	return *(Q.base+Q.front);
}

QElemType back(sq_queue Q)
{
	int idx = (Q.rear-1+MAX_QUEUE_SIZE)%MAX_QUEUE_SIZE;
	return *(Q.base+idx);
}

void traverse(sq_queue Q,void(*vi)(QElemType))
{
	int p = Q.front;
	while(p!=Q.rear)
	{
		vi(*(Q.base+p));
		p=(p+1)%MAX_QUEUE_SIZE;
	}
	printf("\n");
	return ;
}
           

双端队列

        双端队列是一种具有队列和栈性质的数据结构。双端队列中的元素可以从两端弹出，插入和删除操作界定在队列的两边进行。双端队列的简单示意图如下

在前面的循环队列中加入下面的两个方法就实现了双端队列：

//队头入列
Status push_front(sq_queue* Q,QElemType e)
{
	assert(Q);
	if(queue_fill(*Q))
		return ERROR;
	Q->front = (Q->front-1+MAX_QUEUE_SIZE)%MAX_QUEUE_SIZE;
	*(Q->base+Q->front)=e;
	return OK;
}

//队尾出列
Status pop_back(sq_queue* Q,QElemType* pe)
{
	assert(Q);
	if(queue_empty(*Q))
		return ERROR;
	Q->rear = (Q->rear-1+MAX_QUEUE_SIZE)%MAX_QUEUE_SIZE;
	*pe = *(Q->base+Q->rear);
	return OK;
}
           

关于栈和队列，在STL中被实现为stack和deque，其中deque为双端队列，而stack的默认实现基于deque，它并没有自己的任何实现实体，详细可参考<stl_stack.h>和<stl_deque.h>