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

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

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

一.栈


栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出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语言
关键词：
数据结构队列
数据结构栈
数据结构栈队列
数据结构栈和队列
小张在努力写代码
目录
相关文章
1897697198172439
|
3天前
|
Python
数据结构===队列
数据结构===队列
1897697198172439
6 0
HEX9CF
|
3天前
|
C++
【洛谷 P1044】[NOIP2003 普及组] 栈 题解（递归+记忆化搜索）
**NOIP2003普及组栈问题**：给定操作数序列1到n，仅允许push(进栈)和pop(出栈)操作。目标是计算所有可能的输出序列总数。输入包含一个整数n(1≤n≤18)。示例输入3，输出5。当队列空时返回1，栈空则只能入栈，栈非空时可入栈或出栈。AC C++代码利用记忆化搜索求解。
HEX9CF
6 1
未名编程
|
5天前
|
算法
$停车场管理系统 栈与队列
$停车场管理系统 栈与队列
未名编程
5 1
小鼠米奇
|
2天前
|
缓存 调度
栈和队列的区别
栈和队列的区别
小鼠米奇
5 0
游客pnral34kl5xba
|
3天前
|
存储 程序员 编译器
堆和栈的区别
堆和栈的区别
游客pnral34kl5xba
8 0
HEX9CF
|
3天前
|
C++
【洛谷 P1739】表达式括号匹配 题解（栈）
该编程题目要求检查给定的包含字母、运算符和括号的表达式是否括号匹配。输入为一行表达式，以`@`结束。如果括号匹配，输出`YES`，否则输出`NO`。样例包括一个匹配和一个不匹配的表达式。解决方案是使用栈，遇到左括号入栈，遇到右括号时判断栈是否为空，栈空则输出`NO`，否则出栈。当读到`@`时，栈空则输出`YES`，否则输出`NO`。提供的AC代码使用C++实现，通过`stack`处理括号匹配。
HEX9CF
5 0
1897697198172439
|
3天前
|
存储 Java Python
数据结构===栈
数据结构===栈
1897697198172439
5 0
wjq++
|
4天前
|
索引
栈的数组实现
栈的数组实现
wjq++
4 0
西瓜味的敌敌畏
|
6天前
|
存储 缓存 算法
队列和栈
队列和栈
西瓜味的敌敌畏
16 0
Eternity._
|
9天前
数据结构——栈和队列
数据结构——栈和队列
Eternity._
10 1