栈和队列
2016年11月22日
22:36
栈(stack)是后进先出的线性表（LIFO last in first out）
#define STACK_INIT_SIZE = 100;
#define STACKICREMENT 10;
typedef struct
{
SElemType *base; //
SElemType *top; //
int stacksize; //
} SqStack;
void InitStack(SqStack &S)
{
S.base = (SELemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!S.base)
exit;
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
}
void GetTop(SqStack &S, SElemType &e)
{
if (S.top == S.base)
return error;
e = *(S.top - 1);
}
void Push(SqStack &S, SElemType e)
{
//插入e为新的栈元素
if (S.top - S.base >= S.stacksize)
{ //栈满，追加内存空间
S.base = (SElemType *)realloc(S.base, S.stacksize + STACKICREMENT) * sizeof(SElemType);
if (!S.base)
exit;
S.top = S.base + S.stacksize;
S.stacksize += STACK_INIT_SIZE;
}
*S.top++ = e;
}
void Pop(SqStack &S,SElemType &e)
{
//若栈不空，删除栈顶元素用e返回其值，否则返回error
if(S.top == S.base)
return error;
e = *--S.top;
return OK;
}
队列是一种先进先出的线性表，它只允许在表的一段进行插入，在另一端删除元素。在队列中，允许插入的一段叫做队尾（rear），允许删除的一端称为队头（front）。
典型的例子是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果程序都需要通过输出通道输出，那么就要按照请求输出的先后次序排队。
typedef struct QNode
{
QELemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
void InitQueue(LinkQueue &Q)
{
Q.front = Q.rear = (QueuePtr *)malloc(sizeof(QNode));
if(!Q.front)
exit(0);
Q.front->next = NULL;
}
void DestoryQueue(LinkQueue &Q)
{
while(Q.front)
{
Q.rear = Q.front -> next;
free(Q.front);
Q.front = Q.rear;
}
}
void EnQueue(LinkQueue &Q,QElemType e)
{
p = (QueuePtr)malloc(sizeof(QNode));
if(!P)
exit;
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
}
void 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;
free(p);
}
已使用 Microsoft OneNote 2016 创建。