提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

循环队列出队-栈和队列的实现

2023-02-18 16:47:34 时间

  栈和队列

  栈 定义和特点

  栈是一种线性结构，限定在表尾进行插入和删除的线性表。

  常规来讲，我们将栈的表尾端定义为栈顶，表头端定义为栈底。

  此外，当返回栈顶元素时循环队列出队，最后插入的元素会被返回，因此，栈的特点是“后进先出”

  表示和实现

  栈支持的操作有：

  插入、删除、返回栈顶元素、计算栈中元素个数、判断栈是否为空

  同时，还要注意栈的初始化和销毁

  顺序栈

  顺序栈是指用顺序存储结构实现的栈：数组

  设置一个栈的结构体，包含动态开辟的数组存放元素，一个维护数组大小，一个top指针表示栈顶元素在表中的位置 （栈顶的）坐标-1

   int ;

   struct

  {

   * a;

  int top;

  int ;

  }Stack;

  接下来对这个栈进行初始化

   void StackInit(Stack*ps）

    {
        assert(ps);
        STDataType* p=(STDataType*)malloc(sizeof(STDataType)*SIZE); 
        //创建SIZE个元素大小的数组
        if (p == NULL) {
            perror("malloc fail\n");
            exit(-1);
        }ps->a = p;
        ps->top=0;
        ps->capacity=SIZE;
        
    }

  下面进行元素入栈操作，即将给定的元素尾插到数组中

   void StackPush(Stack* ps, STDataType x)

    {
        assert(ps);
        //先判定栈是否已满，满则扩容
        if(StackSize(ps)==ps->capacity)
        {
            STDataType* p=(STDataType*)realloc(ps->a,ps->capacity*2* sizeof(STDataType)); 
            if (p != NULL) {
                ps->a = p;
                ps->capacity *= 2;
            }
            else {
                
                perror("realloc fail");
                exit(-1);
            }
        }ps->a[ps->top++]=x;
    }

  元素的出栈操作为从栈顶删除元素,直接改变栈顶元素位置即可

   void StackPop(Stack* ps)

    {
        assert(ps);
        assert(!StackEmpty(ps));
        //确保栈不为空
        ps->top--;
    }

  返回栈顶元素

   STDataType StackTop(Stack* ps)

    {
        assert(ps);
        assert(!StackEmpty(ps));
        return ps->a[ps->top - 1];
    }

  下面分别列出判空和计算栈中元素个数的操作

   bool StackEmpty(Stack*ps)

    {
        assert(ps);
        return ps->top==0;
    }
    int StackSize(Stack*ps)
    {
        assert(ps);
        return ps->top;
    }

  最后别忘了销毁栈，否则内存会泄漏

   void StackDestory(Stack* ps)

    {
        assert(ps);
        free(ps->a);
        ps->a=NULL;
        ps->capacity = ps->top = 0;
    }

  链式栈

  链式栈是指用链式结构实现的栈，通常创建一个个结点，链接。

  由于链表的头删和头插比较容易实现，故链式栈的栈顶为链表的表头。

  实现过程如下：

  首先定义结点结构体，与单链表创建类似：

   int ;

   struct

  {

   data;

  struct * next;

  };

  链栈的初始化就是创造一个空栈，主函数处创建一个栈顶指针*head，初始化函数就是将栈顶指针置空，表示空栈

   void InitStack(StackNode** ps)

    {
        *ps = NULL;
    }

  入栈时，创建结点，头插在栈顶，同时修改栈顶指针

   void StackPush(StackNode** ps, ElemType x)

    {
        struct StackNode* newnode = BuyNode(x);
        //创建结点
        newnode->next = *ps;
        //头插
        *ps = newnode;
        //修改栈顶指针
    }

  出栈先判空，若不空，则头删

   void StackPop(StackNode** ps)

    {
        assert(*ps);
        struct StackNode* newhead = (*ps)->next;
        free(*ps);
        *ps = newhead;
    }

  返回栈顶元素和销毁

   ElemType StackTop(StackNode* ps)

    {
        assert(ps);
        return ps->data;
    }
    //链式栈的销毁需要一个一个free
    void StackDestory(StackNode* ps)
    {
        assert(ps);
        while (ps)
        {
            struct StackNode* cur = ps;
            ps=ps->next;
            free(cur);
        }
    }

  队列 定义和特点

  队列和栈的特性相反，是一种“先进先出”的线性表。

  队列只允许元素在队头删除，在队尾插入。因此，最早进入队列的元素最早出队。

  循环队列

  循环队列是队列的一种顺序表示循环队列出队，使用数组实现，同时需要两个指针分别指向队头和队尾。

  由于队列的特性，先进先出，当有元素入队的时候队尾指针+1，出队时队头指针+1。而会存在一种队列未满（队头删除了一些元素），尾指针指向数组边界，新元素无法入队的情况，如下图所示：

  故需要将顺序空间更改为环状空间，即使用循环队列：

  头、尾指针取模运算，在顺序表内以头尾相衔接的模式移动。

  新位置下标=（旧位置下标+1）%数组容量

  为方便判断队满和队空，需要少用一个元素的空间

  队空的条件：

  队满的条件：(rear+1)%数组容量front

   typedef struct {

        int* a;
        int front;
        int rear;
        int size;
    } MyCircularQueue;
    //创建一个容量大小为K的循环队列
    MyCircularQueue* myCircularQueueCreate(int k)
    {
        //创建队列
        MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
        //队列初始化
        obj->a=(int*)malloc(sizeof(int)*(k+1));
        obj->rear=obj->front=0;
        obj->size=k+1;
        return obj;
    }
    //判断队满
    bool myCircularQueueIsFull(MyCircularQueue* obj) 
    {
        return obj->front==obj->((rear+1)%(obj->size));
    }
    //入队，成功返回true
    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
    {
        if(!myCircularQueueIsFull(obj))
        {
            obj->a[obj->rear]=value;
            rear=(rear+1)%(obj->size);
            return true;
        }return false;
    }
    //判空
    bool myCircularQueueIsEmpty(MyCircularQueue* obj)
    {
        return obj->front==obj->rear;
    }
    //出队
    bool myCircularQueueDeQueue(MyCircularQueue* obj)
    {
        if(!myCircularQueueIsEmpty(obj))
        {
            obj->front=(obj->front+1)%(obj->size);
            return true;
        }
        return false;
    }
    //返回队首元素
    int myCircularQueueFront(MyCircularQueue* obj) 
    {
        if(!myCircularQueueIsEmpty(obj))
        {
            return obj->a[obj->front];
        }
    }
    //返回队尾元素
    int myCircularQueueRear(MyCircularQueue* obj) {
        if (myCircularQueueIsEmpty(obj))
        {
            return -1;
        }
        else
        {
            //return obj->a[obj->rear-1]错误，如果此时rear=0,-1会非法访问
            return obj->a[(obj->rear + obj->size-1) % (obj->size)];
        }
    }
    //销毁
    void myCircularQueueFree(MyCircularQueue* obj) {
        //分批次销毁，动态开辟的栈和数组都要销毁
        free(obj->a);
        free(obj);
    }

  链式队列

  一个队列需要由头尾指针和若干结点组成，为方便管理，设置两个结构体

   int ;

  //队列的链式结点

   struct

  {

   data;

  struct * next;

  };

  //队列结构

   struct Queue

  {

  * head;

  * tail;

  int size; //方便计算元素个数

  }Queue;

  接下来实现队列的操作

   //队列初始化

    void QueueInit(Queue* p)
    {
        assert(p);
        p->head = NULL;
        p->tail = NULL;
        p->size = 0;
    }
    //入队
    void Enqueue(Queue* p, QueueType x)
    {
        QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
        if (newnode == NULL)
        {
            perror("malloc fail\n");
            exit(-1);
        }newnode->data = x;
        newnode->next = NULL;
        //尾插到队列尾指针操作
        if (QueueEmpty(p))
        {
            p->head = p->tail = newnode;
        }
        else {
            p->tail->next = newnode;
            p->tail = newnode;
        }p->size++;
    }
    //出队
    void Dequeue(Queue* p)
    {
        assert(p);
        assert(!QueueEmpty(p));
        if (p->head == p->tail)
        {
            free(p->head);
            p->head = p->tail = NULL;
        }
        else {
            QueueNode* del = p->head;
            p->head = p->head->next;
            free(del);
        }
        p->size--;
        
    }
    //返回队头元素
    QueueType QueuePeek(Queue* p)
    {
        assert(p);
        assert(!QueueEmpty(p));
        return p->head->data;
    }
    //返回队尾元素
    QueueType QueueBack(Queue* p)
    {
        assert(p);
        assert(!QueueEmpty(p));
        return p->tail->data;
    }
    //计算队列元素个数
    int QueueSize(Queue* p)
    {
        assert(p);
        return p->size;
    }
    //判空
    int QueueEmpty(Queue* p)
    {
        assert(p);
        return p->head == NULL;
    }
    //销毁队列
    void QueueDestory(Queue* p)
    {
        assert(p);
        QueueNode* cur = p->head;
        while (cur)
        {
            QueueNode* del = cur;
            cur = cur->next;
            free(del);
        }p->head = p->tail = NULL;
        p->size = 0;
        
    }

本文共 1002 个字数,平均阅读时长 ≈ 3分钟

相关文章