栈的相关概念

• 栈（stack）是一个特殊的线性表，是限定在仅在一端进行插入和删除操作的线性表，
• 又称==后进先出==（Last In First Out）的线性表，简称==LIFO==结构。
• 表尾称为栈顶（Top）；标头称为栈底（Base），
• 插入元素到栈顶（即表尾）的操作，称为入栈；从栈顶删除最后一个元素的操作，称为出栈。

顺序栈的表示及实现

栈的抽象数据类型的类型定义

ADT Stack {
	数据对象:
	D={ai,i=1,2,3,...}
	数据关系:
	R1 = {<ai-1,ai>}
	约定an端为栈顶，a1端为栈底。
	基本操作
}ADT Stack

顺序栈的表示

利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端。

#define MAXSIZE 100
typedef struct {
	SElenType *base;  //栈底指针
	SElenType *top;   //栈底指针
	int stacksize;    //栈可用最大容量
}SqStack;

顺序表的基本操作

顺序栈的初始化

//构造一个空栈
Status InitStack(SqStack & S) {
	S.base = new SElemType[MAXSIZE];
	//S.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType));
	if(!S.base) return ERROR;  //存储分配失败
	S.top = S.base;    //栈顶指针等于栈底指针
	S.stacksize = MAXSIZE;
	return OK;
}

判断栈是否为空

//若栈为空，返回TRUE;否则返回FALSE
Status StackEmpty(SqStack S){
	if(S.top == S.base)
		return TRUE;
	else
		return FALSE;
}

顺序栈的入栈

/**
1.判断是否栈满，
2.元素e压入栈顶，
3.栈顶指针加1
*/
Status Push(SqStack &S,SElemType e){
	if(S.top-S.base == S.stacksize)  //栈满
		return;
	*S.top = e;
	S.top++;
}

顺序栈的出栈

/**
1.判断是否栈空，
2.取出栈顶元素e，
3.栈顶指针减1
*/
Status Pop(SqStack &S,SElemType &e){
	if(S.top == S.base)  //栈满
		return;
	--S.top;
	e=*S.top;
	return OK;
}

链栈的表示

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

链栈的入栈

Status Push(LinkStack &S,SElemType e){
	p = new StackNode;  //生成新结点p
	p->data = e;
	p->next = S;   //将新结点插入栈顶
	S = p;           //修改栈顶指针
	return OK;
}

链栈的出栈

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

队列的基本表示及操作

顺序队列

#define MAXSIZE 100
typedef struct {
	QElenType *base;  //初始化的动态分配空间
	int front;   //头指针
	int rear;    //尾指针
}SqQueue;

循环队列的初始化

Status InitQueue(SqQueue &Q){
	Q.base = new QElemType[MAXSIZE];   //分配数组空间
	//Q.base = (QElemType*)malloc(MAXSIZE*sizeof(QElemType));
	if(!Q.base) return ERROR;  //存储分配失败
	Q.front = Q.rear = 0;
	return OK;
}

求循环队列的长度

int QueueLength(QsQueue 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;
}

链队列

链队列的类型定义

#define MAXSIZE 100
typedef struct QNode{
	QElemType data;
	struct QNode *next;
}QNode.*QueuePtr;

typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

链队列初始化

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

链队列入队

Status EnQueue（LinkQueue &Q,QElemType e）{
	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;
	p = Q.front->next;
	e = p->data;
	Q.front->next = p->next;
	if(Q.rear == p) Q.rear = Q.front;
	delete p;
	return OK;
}