栈和队列 - HelloWorld开发者社区

栈原理

栈（stack）又名堆栈，是一种只能在表尾进行插入和删除操作的线性表。能够进行操作的这一端被称为栈顶，相对地，把另一端称为栈底。 ::: warning 栈内元素操作时先进后出，类似于电梯上下成员，最后进去的人最先出来。 ::: 栈和队列向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。如上图，top代表栈顶，栈S是一个结构体。S.top=-1时栈为空，当入栈第一个元素时，S.data[++S.top]=1，S.top前置++后数组下标变为0，依次向下可以入栈后面的元素。栈和队列上图中x表示要出栈的值（栈顶的那个值），S.data[S.top]=4，出栈后元素下标-1，变为S.top- -，下次要出栈的值变为3，即S.data[S.top- -]=3。 S.top是数组的下标，最大值为maxsize-1。

初始化栈及入栈出栈

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 50
typedef int Elemtype;
typedef struct
{
    Elemtype data[MaxSize];
    int top;  //始终指向栈顶的变量
}SqStack;

//初始化栈
void InitStack(SqStack& S)
{
    S.top = -1;  //使得栈为空即为初始化栈，栈空即为S.top = -1
}

//判断栈是否为空
bool StackEmpty(SqStack S)
{
    if (-1 == S.top)  //定义指针时候才可以使用->
    {
        return true;
    }
    else
    {
        return false;
    }
}

//入栈
bool Push(SqStack& S, Elemtype x)  
{
    if (S.top == MaxSize - 1)  //栈满
    {
        return false;
    }
    S.data[++S.top] = x;
    return true;
}

//获取栈顶元素
bool GetTop(SqStack S, Elemtype &x)  //x需要引用&，原因是要对x赋值传递出去
{
    if (-1 == S.top)  //栈不能为空
    {
        return false;
    }
    /*或者使用嵌套调用如下：
    if (StackEmpty(S))
    {
        return false;
    }*/
    x = S.data[S.top];  //拿到栈顶元素
    return true;
}

//弹栈（即出栈）
bool Pop(SqStack &S, Elemtype &x)
{
    if (StackEmpty(S))  //栈不能为空
    {
        return false;
    }
    x = S.data[S.top];  //拿到栈顶元素
    x = S.data[S.top--];  //元素出栈
    return true;
}

int main()
{
    SqStack S;  //定义一个栈
    InitStack(S);
    bool flag;
    flag = StackEmpty(S);  //判断栈是否为空
    if (flag)
    {
        printf("stack is empty\n");
    }

    Push(S, 3);  //入栈元素3
    Push(S, 4);  //入栈元素4
    Push(S, 5);  //入栈元素5
    Elemtype m;
    flag = GetTop(S, m);  //获取栈顶元素
    if (flag)
    {
        printf("get top element %d\n", m);  //打印栈顶元素
    }
    flag = Pop(S, m);  //弹出栈顶元素
    if (flag)
    {
        printf("pop element %d\n", m);  //打印弹出元素
    }
    return 0;
}

stack is empty
get top element 5
pop element 5

栈和队列 弹栈的作用是将S.top- -，上述代码中S.top指向4，即数组下标为1的位置，下次再有入栈的元素会覆盖掉数组下标为2的元素5。 ::: warning 弹栈不改变栈元素，只是改变了栈顶指针S.top指向的位置。 :::

队列原理

FIFO：全称First in, First out，先进先出。队列简称队，只允许在表的一端进行插入，另一端进行删除。队列中插入元素称为入队（进队），删除元素称为出队（离队）。栈和队列

数组实现循环队列

栈和队列循环队列可以使用数组或链表实现，这里使用数组。 如上图，Q.front=Q.rear时，队列为空。每次入队一个元素，rear+1；每次出队一个元素，front+1。 当放到元素f时，需要模上数组长度（(Q.rear)%MaxSize=Q.front），然后把数组下标Q.rear置为0。 如果f后继续放g，此时队列头Q.front和队列尾Q.rear相等，都指向下标为1的位置，相等会认为是循环队列为空，所以不能放入g。 循环每次空出一个位置，如果rear+1=front，表示rear追上front，判断循环队列已经放满。栈和队列 ::: warning 循环队列为空时不一定下标为0，只要Q.front=Q.rear队列就为空。 ::: Q.front指向的元素就是要出队的元素。 上图中如果Q.front指向数组下标5的元素，Q.front+1变为6，Q.front%MaxSize变为0，即Q.front又从0开始向后循环。

队列链式存储栈和队列队列尾部插入，头部删除。 front指向链表头第一个元素的位置，rear指向链表尾最后一个元素后面一个可以存放元素的位置。有元素入队后rear向后+1，需要判断是否超出MaxSize，如果超过MaxSize，需要回到开头（位置0）。代码是：Q.rear = (Q.rear + 1) % MaxSize。

循环队列代码：

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 5

typedef int Elemtype;
typedef struct
{
    Elemtype data[MaxSize];
    Elemtype front, rear;
}SqQueue;

//初始化循环队列
void InitQueue(SqQueue &Q)
{
    Q.front = Q.rear = 0;  //循环队列初始化是将队列头尾都指向0号元素
}

//判断是否为空队列
bool IsEmpty(SqQueue Q)
{
    return Q.front = Q.rear;
}

//入队
bool EnQueue(SqQueue& Q, Elemtype x)
{
    if ((Q.rear + 1) % MaxSize == Q.front)  //判断队列是否已满，已满不能入队
    {
        return false;
    }
    Q.data[Q.rear] = x;  //入队。rear始终指向队尾可以存放元素的位置
    Q.rear = (Q.rear + 1) % MaxSize;  //判断rear+1后是否超出MaxSize，如果超出rear要回到起始位置0
    return true;
}

//出队
bool DeQueue(SqQueue& Q, Elemtype& x)
{
    if (Q.rear == Q.front)  //判断队列是否为空
    {
        return false;  //队列为空时无法出队
    }
    x = Q.data[Q.front];  //队列从头部出队，尾部入队
    Q.front = (Q.front + 1) % MaxSize;  //判断front+1后是否超出MaxSize，如果超出front要回到起始位置0
}
int main()
{
    SqQueue Q;
    InitQueue(Q);  //初始化循环队列
    bool ret;
    ret = IsEmpty(Q);
    if (ret)
    {
        printf("SqQueue is Empty\n");
    }
    else
    {
        printf("SqQuene is not Empty\n");
    }
    EnQueue(Q, 3);
    EnQueue(Q, 4);
    EnQueue(Q, 5);
    ret = EnQueue(Q, 6);
    ret = EnQueue(Q, 7);
    if (ret)
    {
        printf("EnQueue success\n");
    }
    else
    {
        printf("EnQueue failed\n");
    }
    Elemtype element;  //存储出队元素
    ret = DeQueue(Q, element);
    if (ret)
    {
        printf("DeQueue success\n");
    }
    else
    {
        printf("DeQueue failed\n");
    }
    ret = EnQueue(Q, 7);
    if (ret)
    {
        printf("EnQueue success\n");
    }
    else
    {
        printf("EnQueue failed\n");
    }
    return 0;

执行结果如下：栈和队列上述代码第一次末尾入队元素7时，超出MaxSize值，无法入队，在出队队首的一个元素后，元素7入队成功，在主函数结束时打断点查看调试信息，可以看到元素7成功入队，front+1指向队列下标1处，rear模MaxSize后指向下标0处。此时(rear+1)%MaxSize=front，循环列表放满。

链表实现普通队列：链表实现的普通队列可以有很长，不考虑链表填满的问题。 ::: tip 出队过程中，front从指向头节点开始，每次出队节点都是Q.front->next，即front指向出队节点的前一个，rear指向出队节点的后一个。 :::

::: warning front始终指向头节点，data域不放数据。rear始终指向链表尾，next域置为NULL。 ::: 链表实现的普通队列代码：

#include <stdio.h>
#include <stdlib.h>

typedef int Elemtype;
typedef struct LinkNode
{
    Elemtype data;
    struct LinkNode* next;
}LinkNode;

typedef struct
{
    LinkNode* front, * rear;  //链表头、链表尾（队头、队尾）
}LinkQueue;  //队列先进先出（队头出队尾进）

//队列初始化，使用带头节点的链表实现
void InitQueue(LinkQueue& Q)
{
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));  //开辟空间是头节点
    Q.front->next = NULL;
}

//入队
void EnQueue(LinkQueue& Q, Elemtype x)  //入队时从队列尾部入队，Q会改变
{
    LinkNode* pnew = (LinkNode*)malloc(sizeof(LinkNode));
    pnew->data = x;
    pnew->next = NULL;  //入队的节点next置为NULL，否则需要遍历链表时无法找到链表结束位置
    Q.rear->next = pnew;  //队尾插入，原队列尾部节点的next指向新入队的节点
    Q.rear = pnew;  //rear指向新的队列尾部
}

//出队
bool DeQueue(LinkQueue& Q, Elemtype& x)  //元素出队时链表Q会改变，取出出队元素，x会改变，使用&
{
    if (Q.front == Q.rear)  //front和rear都指向头节点时队列为空
    {
        return false;
    }
    //Q.front->next = Q.front->next->next;
    //free(Q.front->next);
    //Q.front->next = NULL;
    x = Q.front->next->data;
    LinkNode* p = Q.front->next;
    Q.front = p->next;
    if (Q.rear == p)  //当链表中只剩下一个节点时，该节点被删除（出队）时要改变rear
    {
        Q.rear = Q.front;
    }
    free(p);
    p = NULL;
    return true;
}

int main()
{
    LinkQueue Q;
    InitQueue(Q);  //初始化队列
    EnQueue(Q, 3);
    EnQueue(Q, 4);
    EnQueue(Q, 5);
    EnQueue(Q, 6);
    EnQueue(Q, 7);
    EnQueue(Q, 3);
    EnQueue(Q, 9);
    bool ret;
    Elemtype element;
    ret = DeQueue(Q, element);
    if (ret)
    {
        printf("DeQueue success element = %d\n", element);
    }
    else 
    {
        printf("DeQueue falied");
    }
    return 0;
}

题目解读

栈和队列上图是一个空的循环队列，队列中的节点data域为空，next域指向自己，起始时front和rear都指向该空闲节点。（循环队列没有固定的头节点）当入队一个新节点pnew时，front指向空闲节点不变，rear的next域由指向空闲节点变为指向新节点pnew：rear->next=pnew，rear指向新的队列尾部节点：rear=pnew或rear=rear->next，新节点的next域指向空闲节点：rear->next=front，此时循环队列是填满状态。要求出队元素的空间可重复使用，即每次malloc开辟的空间在使用完毕后不会free，使用循环队列。要求占用空间只增不减，即不能使用数组形式，定义数组时数组所占空间就已经确定了。（链式存储结构使用链表，顺序存储结构使用数组。）栈和队列入队时，先判断队列是否已满，已满则在rear后开辟新节点，rear->next由front指向新节点，入队元素保存在rear指向节点的data域，rear=rear->next。未满则在新节点放在rear->next位置上，rear指向新节点，rear=rear->next。出队时，先判断队列是否为空，不为空时front指向的节点出队，front=front->next。代码实现：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef int Elemtype;
typedef struct LNode {
    Elemtype data;
    struct LNode* next;
}LNode, * LinkList;

//入队
void EnQueue(LinkList front, LinkList& rear, Elemtype value)
{
    LinkList pnew;
    if (rear->next == front)  //队列已满
    {
        pnew = (LinkList)malloc(sizeof(LNode));  //申请空间存放入队元素
        rear->data = value;  //根据题目要求将入队元素直接放在rear的data域中
        rear->next = pnew;  //做分隔
        //rear = rear->next;
        //rear->next = front;
        pnew->next = front;
        rear = pnew;
    }
    else
    {
        rear->data = value;
        rear = rear->next;
    }
}

//出队
void DeQueue(LinkList& front, LinkList rear)
{
    if (front == rear)
    {
        printf("队列为空\n");
    }
    else
    {
        //循环队列空间可以重复使用，出队时不会释放空间
        printf("出队的值为%d\n", front->data);
        front = front->next;
    } 
}

//循环队列操作的总流程
void CircleQueue(LinkList& front, LinkList& rear)
{
    //假设带头节点的链表
    front = (LinkList)malloc(sizeof(LNode));  //申请空间使rear和front都指向这个头节点
    rear = front;
    rear->next = front;  //构建循环队列
    //入队
    EnQueue(front, rear, 3);
    EnQueue(front, rear, 4);
    //出队
    DeQueue(front, rear);
    DeQueue(front, rear);
    DeQueue(front, rear);
}

int main()
{
    LinkList front, rear;
    CircleQueue(front, rear);
    return 0;
}

出队的值为3
出队的值为4
队列为空

栈原理

初始化栈及入栈出栈

队列原理

数组实现循环队列

题目解读

Android进阶之旅-(NDK实战篇之C/C++进阶)

Android进阶之旅-(NDK实战篇之数据结构算法进阶)

热门文章