【C语言 - 数据结构】浅析栈和队列

简介: 【C语言 - 数据结构】浅析栈和队列

一、栈、队列以及双端队列的概念


1.1栈的概念及结构


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


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


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


image.png


1.2队列的概念及结构


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


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


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


1669439306948.jpg


1.3双端队列的概念及结构


双端队列:是一种线性表,又称为双向队列,所有的插入和删除(通常还有所有的访问)都在表的两端进行。


image.png


二、栈的实现和模拟栈


栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。、


1669439376754.jpg

1669439386909.jpg


2.1 实现一个支持动态增长的栈


头文件:


#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct Stack//动态栈
{
  int *a;
  int top;//栈顶的位置
  int capacity;//容量
}ST;
STDataType StackTop(ST* ps);//返回栈顶的值
void StackInit(ST* ps);//初始化栈
void StackDestory(ST* ps);//销毁栈
void StackPop(ST* ps);//弹出
void StackPush(ST* ps, STDataType x);//插入
bool StackEmpty(ST* ps);//判断栈是否为空。

源文件:


#include"Stack.h"
void StackInit(ST* ps)//栈的初始化
{
  assert(ps);
  ps->a = NULL;//a点的值指向空
  ps->top = 0;//栈底为0
  ps->capacity = 0;//空间为0
}
void StackDestory(ST* ps)
{
  assert(ps);
  free(ps->a);//把a释放掉
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)//入数据
{
  assert(ps);
  //满了就扩容
  if (ps->top == ps->capacity)//如果栈的栈顶恰好和容量相等就扩容
  {
  int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
  if (ps->a == NULL)
  {
    printf("realloc fail\n");
    exit(-1);
  }
  ps->capacity = newCapacity;//新的空间赋给旧的
  }
  ps->a[ps->top] = x;//栈顶插入x;
  ps->top++;//top++
}
void StackPop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  --ps->top;//top--就相当于删除操作
}
bool StackEmpty(ST* ps)
{
  assert(ps);
  //两种写法
  //if (ps->top > 0)
  //{
  //  return false;
  //}
  //else
  //{
  //  return true;
  //}
  return ps->top == 0;
}
STDataType StackTop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  return ps->a[ps->top - 1];//访问栈顶元素(这里因为top我们设为0,所以访问栈顶元素相当于top-1
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}


2.2数组模拟静态栈


1669439532720.jpg

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int stk[N];
int top = - 1;
int main ()
{
    cin >> n;
    while(n --)
    {
        string s;
        cin >> s;
        if(s == "push")
        {
            int a;
            cin >> a;
            stk[++top] = a;
        }
        if(s == "pop")
        {
            top--;
        }
        if(s == "empty")
        {
            if(top >= 0) printf("NO\n");
            else printf("YES\n");
        }
        if(s == "query")
        {
            printf("%d\n", stk[top]);
        }
    }
    return 0;
}


三、 队列的实现(动态)和模拟静态队列


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


1669439558653.jpg


3.1 实现一个支持动态增长的栈


头文件:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;//方便改类型
typedef struct QueueNode//保存每个节点的数据
{
  QDataType data;
  struct QueueNode* next;
}QNode;
typedef struct Queue
{
  QNode* head;
  QNode* tail;
}Queue;
//上面的写法等价于:
//typedef struct Queue
//{
//  QNode* head;
//  QNode* tail;
//};
//
//typedef struct Queue Queue;//
//一般实际情况哨兵位的头节点不存储值,不放数据
void QueueInit(Queue* pq);//队列初始化
void QueueDestory(Queue* pq);//队列销毁
void QueuePush(Queue* pq, QDataType x);//队尾插入
void QueuePop(Queue* pq);//弹出队头
bool QueueEmpty(Queue* pq);//判断是否为空
size_t QueueSize(Queue* pq);//size_t相当于Unsinged int
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);


源文件:


#include"Queue.h"
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
  QNode* next = cur->next;//先记录下一个位置
  free(cur);//free掉cur指针
  cur = next;//cur赋值到下一个位置
  }
  pq->head = pq->tail = NULL;//置空
}
void QueuePush(Queue* pq, QDataType x)//队尾插入//插入int类型的参数
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  assert(newnode);
  newnode->data = x;//新的节点的值被赋与x
  newnode->next = NULL;//新的节点是在队尾,所以指向的下一个位置是空
  if (pq->tail == NULL)//如果链表的第一个值为空,则head = tail = NULL
  {
  assert(pq->head == NULL);
  pq->head = pq->tail = newnode;
  }
  else//尾插
  {
  pq->tail->next = newnode;//先改指向
  pq->tail = newnode;//再改地址
  }
}
void QueuePop(Queue* pq)//弹出队首
{
  assert(pq);
  assert(pq->head && pq->tail);
  if (pq->head->next == NULL)//只有一个节点
  {
  free(pq->head);
  pq->head = pq->tail = NULL;
  }
  else
  {
  QNode* next = pq->head->next;//QNode* next相当于是QDataType的头指针的下一个位置
  free(pq->head);
  pq->head = next;//头往后走
  }
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  //return pq->head == NULL && pq->tail == NULL;
  return pq->head == NULL;//程序调试了快一个小时就是因为pq->head没加后面的== NULL
}
size_t QueueSize(Queue* pq)//size_t相当于Unsinged int
{
  assert(pq);
  QNode* cur = pq->head;
  size_t size = 0;
  while (cur)
  {
  size++;
  cur = cur->next;
  }
  return size;
}
QDataType QueueFront(Queue* pq)//返回队头第一个位的值
{
  assert(pq);
  assert(pq->head);
  return pq->head->data;
}
QDataType QueueBack(Queue* pq)//返回队尾的值
{
  assert(pq);
  assert(pq->tail);
  return pq->tail->data;
}


3.2数组模拟静态队列


1669439620642.jpg

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int q[N];
int n;
int hh ,tt = -1;//hh表示头,tt表示尾
int main ()
{
    cin >> n;
    while(n --)
    {
        string s;
        cin >> s;
        if(s == "push")
        {
            int x;
            cin >> x;
            q[++tt] = x;
        }
        else if(s == "pop")
        {
            hh ++;
        }
        else if(s == "empty")
            {
                if(hh <= tt) printf("NO\n");//尾在逻辑上要比头更前面
                else printf("YES\n");
            }
        else cout << q[hh] << endl;
    }
    return 0;
}


四、leetcode-栈实现队列和用队列实现栈


225. 用队列实现栈 - 力扣(LeetCode)


1669439648911.jpg


代码:

typedef int QDataType;
typedef struct QueueNode//保存每个节点的数据
{
  QDataType data;
  struct QueueNode* next;
}QNode;
typedef struct Queue
{
  QNode* head;
  QNode* tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);//队尾插入
void QueuePop(Queue* pq);
bool QueueEmpty(Queue* pq);
size_t QueueSize(Queue* pq);//size_t相当于Unsinged int
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
  QNode* next = cur->next;//先记录下一个位置
  free(cur);//free掉cur指针
  cur = next;//cur赋值到下一个位置
  }
  pq->head = pq->tail = NULL;//置空
}
void QueuePush(Queue* pq, QDataType x)//队尾插入
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  assert(newnode);
  newnode->data = x;
  newnode->next = NULL;
  if (pq->tail == NULL)//如果链表的第一个值为空,则head = tail = NULL
  {
  assert(pq->head == NULL);
  pq->head = pq->tail = newnode;
  }
  else//尾插
  {
  pq->tail->next = newnode;
  pq->tail = newnode;
  }
}
void QueuePop(Queue* pq)//弹出队首
{
  assert(pq);
  assert(pq->head && pq->tail);
  if (pq->head->next == NULL)//只有一个节点
  {
  free(pq->head);
  pq->head = pq->tail = NULL;
  }
  else
  {
  QNode* next = pq->head->next;//QNode* next相当于是QDataType的头指针的下一个位置
  free(pq->head);
  pq->head = next;//头往后走
  }
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  //return pq->head == NULL && pq->tail == NULL;
  return pq->head == NULL;//程序调试了快一个小时就是因为pq->head没加后面的== NULL
}
size_t QueueSize(Queue* pq)//size_t相当于Unsinged int
{
  assert(pq);
  QNode* cur = pq->head;
  size_t size = 0;
  while (cur)
  {
  size++;
  cur = cur->next;
  }
  return size;
}
QDataType QueueFront(Queue* pq)//返回队头第一个位的值
{
  assert(pq);
  assert(pq->head);
  return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->tail);
  return pq->tail->data;
}
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    assert(pst);
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}
void myStackPush(MyStack* obj, int x) {
    assert(obj);
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}
int myStackPop(MyStack* obj) {
    Queue* emptyQ = &obj->q1;//假设q1为空,q2不为空
    Queue* nonEmptyQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ = &obj->q2;
        nonEmptyQ = &obj->q1;
    }
    //把非空队列的前N个数据导入空队列,剩下一个删掉
    //就实现了后进先出
    while(QueueSize(nonEmptyQ) > 1)
    {
        QueuePush(emptyQ, QueueFront(nonEmptyQ));
        QueuePop(nonEmptyQ);
    }
    int top = QueueFront(nonEmptyQ);//此时那个非空的队列只剩下一个数据
    QueuePop(nonEmptyQ);
    return top;
}
int myStackTop(MyStack* obj) {
    assert(obj);
      if(!QueueEmpty(&obj->q1))//如果q1不为空
    {
     return QueueBack(&obj->q1);  
    }
    else
    {
     return QueueBack(&obj->q2);  
    }
}
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
    assert(obj); 
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    free(obj);
}


232. 用栈实现队列 - 力扣(LeetCode)栈是后进先出


思路:设计两个栈,一个栈专门用来入数据,一个栈专门用来出数据。

1669439684975.jpg

typedef int STDataType;
typedef struct Stack//动态链表
{
  int *a;
  int top;//栈顶的位置
  int capacity;//容量
}ST;
STDataType StackTop(ST* ps);
void StackInit(ST* ps);//初始化栈
void StackDestory(ST* ps);
void StackPop(ST* ps);
void StackPush(ST* ps, STDataType x);
bool StackEmpty(ST* ps);
void StackInit(ST* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->top = 0;
  ps->capacity = 0;
}
void StackDestory(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)//入数据
{
  assert(ps);
  //满了就扩容
  if (ps->top == ps->capacity)
  {
  int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
  if (ps->a == NULL)
  {
    printf("realloc fail\n");
    exit(-1);
  }
  ps->capacity = newCapacity;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
void StackPop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  --ps->top;
}
bool StackEmpty(ST* ps)
{
  assert(ps);
  //两种写法
  //if (ps->top > 0)
  //{
  //  return false;
  //}
  //else
  //{
  //  return true;
  //}
  return ps->top == 0;
}
STDataType StackTop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  return ps->a[ps->top - 1];//访问栈顶元素
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
typedef struct
{
    ST pushST;
    ST popST;
} MyQueue;
MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    assert(obj);
    StackInit(&obj->pushST);//&符要加,要改变结构体里面的内容
    StackInit(&obj->popST);
    return obj;
}
void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    StackPush(&obj->pushST, x);
}
int myQueuePop(MyQueue* obj) {
    assert(obj);
    //如果popST为空, 把pushST的数据拿过来,就符合先进先出的顺序了
    if(StackEmpty(&obj->popST))//如果ST Pop为空就执行
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);//把pushST里的数据删掉
        }
    }
    int front = StackTop(&obj->popST);//记录栈顶的数据
    StackPop(&obj->popST);
    return front;
}
int myQueuePeek(MyQueue* obj) {
    assert(obj);
    //如果popST为空, 把pushST的数据拿过来,就符合先进先出的顺序了
    if(StackEmpty(&obj->popST))//如果ST Pop为空就执行
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);//把pushST里的数据删掉
        }
    }
    return StackTop(&obj->popST);
}
bool myQueueEmpty(MyQueue* obj) {
        assert(obj);
    return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);
}
void myQueueFree(MyQueue* obj) {
    assert(obj);
    StackDestory(&obj->pushST);
    StackDestory(&obj->popST);
    free(obj);
}
相关文章
|
2月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
68 1
|
12天前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
128 75
|
12天前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
34 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
12天前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
35 9
|
12天前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
29 7
|
2月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
87 5
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
82 1
|
C语言
C语言队列实现
一,简介 开发环境是VC6.0,实现了一个基于C语言的队列。 主要功能,入队、出队、显示当前队列元素。
134 0
|
12天前
|
存储 算法 C语言
【C语言程序设计——函数】素数判定(头歌实践教学平台习题)【合集】
本内容介绍了编写一个判断素数的子函数的任务,涵盖循环控制与跳转语句、算术运算符(%)、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码,测试说明提供了输入输出示例,最后给出通关代码和测试结果。 任务核心:编写判断素数的子函数并在主函数中调用,涉及循环结构和条件判断。
51 23
|
12天前
|
算法 C语言
【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数(头歌实践教学平台习题)【合集】
本文档介绍了如何编写两个子函数,分别求任意两个整数的最大公约数和最小公倍数。内容涵盖循环控制与跳转语句的使用、最大公约数的求法(包括辗转相除法和更相减损术),以及基于最大公约数求最小公倍数的方法。通过示例代码和测试说明,帮助读者理解和实现相关算法。最终提供了完整的通关代码及测试结果,确保编程任务的成功完成。
43 15

热门文章

最新文章