1.栈的表示和实现

1.1栈的概念及结构

栈:一种特殊的线性表,其只允许在固定的一段进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵循后进先出LIFO(Last In First Out)的原则

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶

出栈:栈的删除操作叫做出栈。入数据也在栈顶

栈有两种实现方式:数组、链表

  • 数组:相当于之前顺序表的尾插,尾插用尾去做了栈顶,非常合适。唯一缺陷就是:空间不够需要增容
  • 链表

    • 单链表:使用单链表就优点不合适了,除非将链表的链尾当作栈底、链头当栈顶。栈顶插入就等于链表头插入O(1)
    • 双链表:如果用尾做栈顶,那么就要用双向链表更好。效率O(1)


**但一般栈的实现都会使用数组来实现**(数组的cpu缓存命中要略高一些(**预加载**))

image-20220103100304255

声名:

#define _CRT_SECURE_NO_WARNINGS 1
#ifndef _TEST_H
#define _TEST_H
//栈的链式存储结构;
typedef struct Node  //创建一种类型的节点;
{
    int data;
    struct Node * pnext;
}NODE, *PNODE;
typedef struct Stack  //创建一个栈类型,里面含有两个指针,一个指向栈顶,一个指向栈底
{
    PNODE ptop;
    PNODE pBottom;
}STACK, *PSTACK;

void init(PSTACK ps);//初始化栈
void push(PSTACK ps, int val);//压栈
void traverse(PSTACK ps);//遍历栈
bool empty(PSTACK ps);//判断栈是否为空
bool pop(PSTACK ps, int * pval);//出栈
void clear(PSTACK ps);//清空栈
#endif  //_TEST_H

具体实现:

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <stdbool.h>
#include "test.h"
int main()
{
    //int val;//保存出栈的元素
    STACK S;//定义一个栈变量
    init(&S);//初始化这个栈
    push(&S, 1);//压栈
    push(&S, 2);
    push(&S, 3);
    push(&S, 4);
    push(&S, 5);
    push(&S, 6);
    traverse(&S);//遍历
    /*if (pop(&S, &val))//出栈
    {
        printf("出栈成功!出栈元素为%d \n", val);
        printf("-------------------------------------------------------\n");
    }
    else
    {
        printf("出栈失败!\n");
    }*/
    //traverse(&S);
    clear(&S);//清空
    printf("-------------------------------------------------------\n");
    printf("清空后栈中元素为:");
    printf("栈中元素为:\n");
    traverse(&S);
    //free(S);//销毁栈
    system("pause");
    return 0;
}
void init(PSTACK ps)
{
    ps->ptop = (PNODE)malloc(sizeof(NODE));//创建一个空栈
    if (NULL == ps->ptop)
    {
        printf("success\n");
        exit(-1);
    }
    else
    {
        ps->pBottom = ps->ptop;//栈底指针跟栈顶指针都指向这个新建的空节点
        ps->ptop->pnext = NULL;
    }
}
void push(PSTACK ps, int val)//压栈
{
    PNODE pNew = (PNODE)malloc(sizeof(NODE));//新建一个节点
    pNew->data = val;//新节点数据域等于val
    pNew->pnext = ps->ptop;//新节点指针域指向栈顶指针所指向的节点,就是前面栈底跟栈顶同时指向的空节点,这样就实现压栈了
    ps->ptop = pNew;//然后栈顶元素上移,始终指向就是最后入栈的节点
}
void traverse(PSTACK ps)//遍历
{
    PNODE p = ps->ptop;//遍历是从栈顶依次输出,所以创建一个指针,指向栈顶指针所指向的节点
    while (p!=ps->pBottom)//当p所指向的节点不是栈底指针指向的节点时
    {
        printf("%d\n", p->data);//输出p所指向的节点的数据域的值
        p = p->pnext;//然后指针p重新指向下一个节点
    }
}
//bool pop(PSTACK ps, int * pval)//出栈一个元素
//{
//    if (empty(ps))//先判断栈是否为空
//    {
//        return false;
//    }
//    else//不为空时
//    {
//        PNODE r = ps->ptop;//创建一个新的指针r,指向栈顶指针所指向的节点
//        *pval = r->data;//将该节点的数据域赋值给val
//        ps->ptop = r->pnext;//栈顶指针重新指向r所指向的下一个节点,
//        free(r);//释放r所指向的节点,就是刚才的栈顶节点
//        r = NULL;//清空
//        return true;
//    }
//}
bool empty(PSTACK ps)//判断栈是否为空
{
    if (ps->ptop == ps->pBottom)
        return true;
    else
        return false;
}
void clear(PSTACK ps)//清空栈内元素
{
    if (empty(ps))
    {
        return ;
    }
    else
    {
        PNODE p = ps->ptop;//创建一个指针,指向当前栈顶指针指向的节点
        PNODE q = NULL;//创建一个中间指针
        while (p!=ps->pBottom)//当p所指向的节点不是栈底指针所指向的节点时
        {
            q = p->pnext;//先将p所指向的下一个节点赋给q
            free(p);//然后删除该节点
            p = q;//然后将q指向的节点赋给p,也就是p重新指向了p的下一个节点
        }
        ps->ptop = ps->pBottom;//循环完了之后,栈底指针跟栈底指针指向同一个节点
    }
}

2.队列

2.1队列的概率及结构

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First in First Out)

入队列:进行插入操作的一端称为队尾

出队列:进行删除操作的一端称为队头

image-20220112134057908

2.2队列的实现

队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数据的结构,出队列在数组头上出数据,效率会比较低。

记住两个公式:队列中,队列满的条件是:(rear+1)%QueueSize=front;

​ 队列长度公式是:(rear-front+QueueSize)%QueueSize。

image-20220112134300107

#pragma once
#include <stdio.h>
#include <stdbool.h>
#include<assert.h>
#include<stdlib.h>
typedef int QDataType;

typedef struct QueueNode {
    
    struct QueueNode* next;
    QDataType data;
}QNode;

typedef struct Queue { //这样的好处就是消除二级指针
    QNode* tail;
    QNode* head;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
//规定:队尾入
void QueuePush(Queue* pq, QDataType x);
//队头出
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);

3.栈和队列OJ题

1.括号匹配问题。(力扣搜索)

2.用队列实现栈。

3.用栈实现队列。

最后修改:2022 年 03 月 02 日
如果觉得我的文章对你有用,请随意赞赏