首页 > 代码库 > 栈和队列

栈和队列

栈和队列

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 = http://www.mamicode.com/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 创建。

栈和队列