栈和队列

栈

  • 栈: 限定仅在表尾进行插入和删除操作的线性表
  • 栈顶/栈底: 允许进行插入、删除操作的表尾端称为栈顶，表头端称为栈底
  • 进栈/入栈: 栈的插入操作通常称为进栈或入栈
  • 出栈/退栈: 栈的删除操作通常称为退栈或出栈
  • 空栈: 不含元素的空表称为空栈

栈的特点

  • FILO: First In Last Out (先进后出)

队列

  • 队列: 只能在表的一端进行插入,而在另一端删除元素的线性表
  • 队尾队头: 允许插入的一端称为队尾允许删除的一端称为队头
  • 入队列: 队列的插入操作通常称为入队列
  • 出队列: 队列的删除操作通常称为出队列
  • 空队列: 当队列中没有数据元素时，称为空队列

队列的特点

  • FIFO: First In First Out (先进先出)

栈与队列

栈、队列是一种特殊（操作受限）的线性表区别: 仅在于运算规则不同

线性表 栈 队列
逻辑结构 一对一 一对一 一对一
存储结构 顺序表、链表 顺序栈、链栈 顺序队列、链队列
运算规则 随机、顺序存取 后进先出 先进先出
插入操作 Insert(L,i, x)1≤i≤n+1 Insert(S,n+1, x) Insert(Q,n+1, x)
删除操作 Delete(L,i)1≤i≤n Delete(S,n) Delete(Q,1)

栈的顺序存储

1
2
3
4
5
typedef struct {
    SElemType *base;    // 栈底指针
    SElemType *top;     // 栈顶指针
    int stacksize;      // 当前已分配的存储空间
}SqStack;

入栈

  1. 若栈满则追加存储空间；
  2. 若栈不满，则在栈顶指针指示的位置插入元素e，最后将栈顶指针增1。
1
2
3
4
5
6
7
8
Status Push(SqStack &S, SElemType e){
    // 判满
    if(S.top - S.base >= S.stacksize){
        return ERROR;
    }
    *S.top++ = e;  // => *S.top = e; S.top++;
    return OK;
}

出栈

1)若栈为空，返回错误；
2)若栈不空，先将栈顶指针减1，然后删除栈顶指针指示的元素。

1
2
3
4
5
6
7
8
Status Pop(SqStack &S, SElemType e){
    // 判空
    if(S.top == S.base){
        return ERROR;
    }
    e = --*S.top;
    return OK;
}

顺序栈的总结

  • 栈是操作受限的线性结构，可以用线性表实现栈的操作，用顺序表实现顺序栈的操作时应将顺序表的表尾作为栈顶。
  • 所有操作(除了遍历)的时间复杂度都是：O(1)。

栈的链式存储

1

取栈顶

  1. 首先判断栈是否为空，若栈为空，则返回ERROR；
  2. 若栈不空则取S指向的栈顶元素，返回OK。
1
2
3
4
5
6
7
Status GetTop(LinkStack S, ElemType &e){
    if(S == NULL){
        return ERROR;
    }
    e = S->data;
    return OK;
}

入栈

  1. 首先申请结点空间，建立新结点；
  2. 然后将新结点插入到链栈中作为新的栈顶元素；
  3. 最后移动栈顶指针到新的栈顶。
1
2
3
4
5
6
7
8
9
10
Status Push(LinkStack &S, ElemType e){
    // 建立结点
    p = (LinkStack) malloc (sizeof(LNode));
    if(!p) exit(OVERFLOW);
    p->data = e;
    // 插入栈顶
    p->next = S;
    S = p;
    return OK;
}

出栈

  1. 若栈为空，返回错误；
  2. 若栈不空，用e取出栈顶元素的值，保存栈顶元素的位置;
  3. 移动栈顶指针S到新的栈顶元素;
  4. 释放结点的内存空间，并返回OK。
1
2
3
4
5
6
7
8
Status Pop(LinkList &S, ElemType &e){
    if(S==NULL) return ERROR;
    e = S->data;
    p = S;
    S = S->next;
    free(p);
    return OK;
}

链栈的总结

  • 栈是操作受限的线性结构，可以用线性表实现栈的操作，用链表实现链栈的操作时应将链表的表头作为栈顶。
  • 所有操作(除了遍历)的时间复杂度都是：O(1)。

队列的链式存储

1
2
3
4
5
6
7
8
9
10
11
// 结点类型
typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode, *QueuePtr;

// 链队列类型
typedef struct {
    QueuePtr front; // 队头指针
    QueuePtr rear; // 队尾指针
}LinkQueue;

入队列

  1. 申请新元素的结点空间，若申请不成功则退出，若申请成功，则结点的数据域为e,指针域为空；
  2. 将新生成的结点链接到队尾之后，作为新的队尾
  3. 队尾指针移向新的队尾结点，返回OK。
1
2
3
4
5
6
7
8
9
10
Status EnQueue(LinkQueue &Q, QElemType e){
    // 申请内存，生成新的结点
    p = (QueuePtr) malloc (sizeof(QNode));
    if(!p) exit(OVERFLOW);
    p->data = e;
    p-next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}

出队列

  1. 若队列为空，则返回错误；
  2. 若队列不空，则删除队头元素，若此时队头恰是队尾，让队尾指针重新指向头结点
1
2
3
4
5
6
7
8
9
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;
    free(p);
    return OK;
}

链队列的总结

  • 链队列的操作即为单链表的插入和删除操作的特殊情况，只是尚需修改尾指针或头指针。
  • 所有操作(除了遍历)的时间复杂度都是：O(1)。

循环队列

1
2
3
4
5
typedef struct {
    QElemType *base;
    int front; // 头指针
    int rear; // 尾指针
}

入队 : Q.rear = (Q.rear + 1) % MAXQSIZE;
出队 : Q.front = (Q.front + 1) % MAXQSIZE;
队满 : (Q.rear + 1) % MAXQSIZE == Q.front;
队空 :

入队列

  1. 若队列满则返回错误
  2. 若队列不满,插入元素e到队尾指向的单元
  3. 队尾指针增1
1
2
3
4
5
6
7
8
Status EnQueue(SqQueue &S, QElemType e){
    if((Q.rear + 1) % MAXQSIZE == Q.front){
        return ERROR;
    }
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    return OK;
}

出队列

  1. 若队列为空，返回错误
  2. 若队列不空，删除队头元素，用e返回其值
  3. 队头指针增1，返回OK
1
2
3
4
5
6
7
8
Status DeQueue(SqQueue &Q, QElemType &e){
    if(Q.front == Q.rear){
        return ERROR;
    }
    e = Q.rear[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    return OK;
}

求长度

1
2
3
Status QueueLength(SqQueue &S){
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

循环队列总结

  • 队列是操作受限的线性结构，其操作在队列的两端进行，特别需要注意队空和队满的条件。
  • 所有操作(除了遍历)的时间复杂度都是：O(1)。