备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】栈和队列（上）

2023-10-10 21
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】栈和队列（上）

一.栈


栈的概念及结构

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

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

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

038ff0726d96496f8ed0f740c61cfb8b.png


栈的实现

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

//静态栈的结构
typedef int STDataType;
#define N 10
typedef struct Stack
{
STDataType _a[N];
int _top; // 栈顶
}Stack;
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;


实际中一般静态栈不实用，所以我们主要实现支持动态增长的栈 

typedef int STDataType;
typedef struct Stack
{
  STDataType* arr;
  int top;
  int capacity;
}Stack;
void StackInit(Stack* ps);
void StackDestory(Stack* ps);
void StackPush(Stack* ps, STDataType x);
void StackPop(Stack* ps);
STDataType StackTop(Stack* ps);
bool StackEmpty(Stack* ps);
int StackSize(Stack* ps);
void StackInit(Stack* ps)
{
  assert(ps);
  ps->arr = NULL;
  ps->capacity = ps->top = 0;
}
void StackDestory(Stack* ps)
{
  assert(ps);
  free(ps->arr);
  ps->arr = NULL;
  ps->capacity = ps->top = 0;
}
void StackPush(Stack* ps, STDataType x)
{
  assert(ps);
  //扩容
  if (ps->capacity == ps->top)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    ps->arr = tmp;
    ps->capacity = newCapacity;
  }
  //压栈
  ps->arr[ps->top] = x;
  ps->top++;
}
void StackPop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  ps->top--;
}
STDataType StackTop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->arr[ps->top - 1];
}
bool StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->top == 0;
}
int StackSize(Stack* ps)
{
  return ps->top; 
}


二.队列


队列的概念及结构

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

290c25174ac74b9b8447a36ee2b36330.png

队列的实现

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

typedef int QDaTaType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDaTaType data;
}QNode;
typedef struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}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);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
void QueueDestory(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* del = cur;
    cur = cur->next;
    free(del);
  }
  pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDaTaType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  if (pq->head == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
  pq->size++;
}
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  if (pq->head->next == NULL)//队列中剩下最后一个节点时
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    QNode* del = pq->head;
    pq->head = pq->head->next;
    free(del);
    del = NULL;
  }
  pq->size--;
}
QDaTaType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
QDaTaType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL && pq->tail == NULL;
}
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}


三.栈和队列面试题


1.括号匹配问题

题目链接

20.有效的括号 - 力扣（LeetCode）

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
        1.左括号必须用相同类型的右括号闭合。
        2.左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：s仅由括号 '()[]{}' 组成


解题思路


创建一个栈，遍历字符串s，遇到左括号就入栈，遇到右括号就pop栈顶元素，与右括号比较，如果不符合就return false，如果栈已经为空，也return false，直到s被遍历完毕，然后判断栈是否为空，也就是判断左括号是否完全被成功匹配，如果栈为空，就return true，否则return false。


代码实现

由于C语言没有内置数据结构的库，因此我们需要自己写一个栈。代码如下

typedef char STDataType;
typedef struct Stack
{
  STDataType* arr;
  int top;
  int capacity;
}Stack;
void StackInit(Stack* ps);
void StackDestory(Stack* ps);
void StackPush(Stack* ps, STDataType x);
void StackPop(Stack* ps);
STDataType StackTop(Stack* ps);
bool StackEmpty(Stack* ps);
int StackSize(Stack* ps);
void StackInit(Stack* ps)
{
  assert(ps);
  ps->arr = NULL;
  ps->capacity = ps->top = 0;
}
void StackDestory(Stack* ps)
{
  assert(ps);
  free(ps->arr);
  ps->arr = NULL;
  ps->capacity = ps->top = 0;
}
void StackPush(Stack* ps, STDataType x)
{
  assert(ps);
  //扩容
  if (ps->capacity == ps->top)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    ps->arr = tmp;
    ps->capacity = newCapacity;
  }
  //压栈
  ps->arr[ps->top] = x;
  ps->top++;
}
void StackPop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  ps->top--;
}
STDataType StackTop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->arr[ps->top - 1];
}
bool StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->top == 0;
}
int StackSize(Stack* ps)
{
  return ps->top; 
}


然后直接调用这个栈的接口实现功能即可，代码如下：

bool isValid(char * s){
    Stack st;
    StackInit(&st);
    while(*s)
    {
        if(*s == '{' || *s == '[' || *s == '(')
        {
            StackPush(&st, *s);
        }
        else
        {
            if(StackEmpty(&st))
                return false;
            char top = StackTop(&st);
            StackPop(&st);
            if ((*s == '}' && top != '{')
      || (*s == ']' && top != '[')
      || (*s == ')' && top != '('))
            {
                return false;
            }
        }
        ++s;
    }
    bool flag = StackEmpty(&st);
    StackDestory(&st);
    return flag;
}


文章标签：
C语言
关键词：
数据结构队列
数据结构栈队列
数据结构栈
数据结构栈和队列
小张在努力写代码
目录
相关文章
誓则盟约
|
4天前
|
存储 算法 调度
数据结构与算法-栈篇
数据结构与算法-栈篇
誓则盟约
12 3
一只大鸽子
|
1天前
数据结构 栈 / 队列(第9天)
数据结构 栈 / 队列(第9天)
一只大鸽子
5 1
csdn-Eternity._
|
1天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列：数据结构探索之旅
【C++进阶】深入STL之 栈与队列：数据结构探索之旅
csdn-Eternity._
11 4
csdn-Eternity._
|
1天前
数据结构——栈和队列
数据结构——栈和队列
csdn-Eternity._
6 1
知更鸟呆呆
|
2天前
|
C语言 C++
【数据结构】C语言实现：栈（Stack）与队列（Queue）
【数据结构】C语言实现：栈（Stack）与队列（Queue）
知更鸟呆呆
8 0
誓则盟约
|
4天前
|
算法 调度 Python
数据结构与算法-队列篇
数据结构与算法-队列篇
誓则盟约
11 3
就学呗
|
4天前
数据结构初阶 队列
数据结构初阶 队列
就学呗
5 0
就学呗
|
4天前
数据结构初阶 栈
数据结构初阶 栈
就学呗
8 1
sky_qiyi
|
9天前
|
算法
数据结构和算法学习记录——栈和队列作业（实现链栈上的进栈、实现链栈上的退栈、实现链队上的入队列）
数据结构和算法学习记录——栈和队列作业（实现链栈上的进栈、实现链栈上的退栈、实现链队上的入队列）
sky_qiyi
11 0
加油，旭杏
|
12天前
|
存储 缓存 算法
【数据结构】栈和队列的模拟实现（两个方式实现）
【数据结构】栈和队列的模拟实现（两个方式实现）
加油，旭杏
13 1