栈和队列经典笔试题

简介: 栈和队列经典笔试题


安静的夜晚 你在想谁吗

栈和队列的回顾💻

栈🩳

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

一般使用数组实现栈

物理图表示入栈和出栈(后进先出)

队列👟

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

入队列:进行插入操作的一端称为队尾 ;出队列:进行删除操作的一端称为队头。

物理图表示入队和出队(先进先出)

栈和队列经典笔试题🔋

有效的括号🎸

力扣题目链接:有效的括号

给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

下面是几个示例:

题目分析

本题通俗的来讲,就是判断括号是否是匹配的,即括号的类型是否匹配和数量是否匹配。我们可以使用栈的知识来解决这道题:从给定序列的第一个字符开始遍历,如果遍历遇到左括号,就入栈;如果遍历遇到右括号,则先取栈顶元素,再出栈(因为合适的匹配必须是栈),判断栈顶元素与这个右括号是否匹配。

需要注意的点有:尽量每次循环只遍历一个元素或只对一个元素进行判断,这样可以保证数量匹配的正确性。当遍历一个元素不是左括号的时候,就判断栈中是否为空,如果栈为空,则说明数量是不匹配的;如果栈不为空,则要对这个右括号是否和栈顶的左括号匹配进行判断。

其实本题比较复杂的还是结构的问题,毕竟不用C++的,这个栈的功能需要我们自己去实现。

力扣代码(含栈结构)

typedef char STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;
  int capacity;
}ST;
void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
STDataType STtop(ST* ps);
int STsize(ST* ps);
bool STEmpty(ST* ps);
void STInit(ST* ps)
{
  ps->a = NULL;
  ps->top = 0;
  ps->capacity = 0;
}
void STDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}
void STPush(ST* ps, STDataType x)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    int NEWcapacity = (ps->capacity == 0) ? 4 : (ps->capacity * 2);
    //扩容
    STDataType* tmp = realloc(ps->a, sizeof(STDataType) * NEWcapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = NEWcapacity;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
void STPop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  ps->top--;
}
//获取栈顶元素
STDataType STtop(ST* ps)
{
  assert(ps);
  assert(ps->top>0);
  return ps->a[ps->top-1];
}
int STsize(ST* ps)
{
  assert(ps);
  return ps->top;
}
bool STEmpty(ST* ps)
{
  assert(ps);
  return (ps->top == 0);
}
bool isValid(char * s){
    ST st;
    STInit(&st);
    char stack_top;
    while(*s)
    {
      if(*s=='('||*s=='['||*s=='{')
      {
        STPush(&st,*s);
      } 
      else
      {
        if(STEmpty(&st))
        {
          STDestroy(&st);
          return false;
        }
        stack_top=STtop(&st);
        STPop(&st);
        if(*s==')'&&stack_top!='('||
          *s==']'&&stack_top!='['||
          *s=='}'&&stack_top!='{')
          {
            STDestroy(&st);
            return false;
          }
      }
      s++;
    }
    if(!STEmpty(&st))
    {
      STDestroy(&st);
      return false;
    }
    return true;
}

当代码在所有不满足的情况下依旧没有返回 false 的时候,则说明它是满足括号的有效性的。

用队列实现栈 🕯

力扣题目链接:用队列实现栈

你只能使用队列的基本操作 —— 也就是 push to backpeek/pop from frontsizeis empty 这些操作。

你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

范例:

题目分析及思路

队列是先进先出,要实现一个后进先出的栈,一个队列肯定是不行的,必须使用两个队列来互相导着来实现。例如,我现在要对这个数据结构入4个元素:1 2 3 4

队列只能 pop 先 push 的元素,而要达到将最后进入的元素 pop 的目的,就需要另一个队列来帮忙了:先将所有元素都push到队列1,取 队列1 头位置的元素,将它 push 到 队列2 中后,再将 队列1 中这个元素 pop 掉。如此往复,直到 队列1 中只剩下一个元素,这就是栈结构中需要 pop 的元素。

再将最后这个元素pop掉,就相当于将栈结构里的栈顶元素pop掉了。这样就实现了栈的pop功能。

在上面的例子中,我们可以总结出队列实现栈的一般规律:实现push数据,就往空的队列里push;实现pop数据,先将费控队列的前n-1个元素导入空队列,并pop这n-1个元素,最后将剩下的那个元素pop掉即可实现栈的pop功能。

力扣代码(含结构)

typedef int QDataType;
typedef struct QueueNode {
  QDataType data;
  struct QueueNode* next;
}QNode;
typedef struct Queue {
  QNode* head;
  QNode* tail;
  int size;
}Que;
void QueueInit(Que*pq);
void QueueDestroy(Que* pq);
void QueuePush(Que* pq, QDataType x);
void QueuePop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);
void QueueInit(Que* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
void QueueDestroy(Que* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
}
void QueuePush(Que* pq, QDataType x)
{
  assert(pq);
  QNode* nownode = (QNode*)malloc(sizeof(QNode));
  if (nownode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  nownode->data = x;
  nownode->next = NULL;
  if (pq->tail == NULL)
  {
    pq->head = pq->tail = nownode;
  }
  else
  {
    pq->tail->next = nownode;
    pq->tail = nownode;
  }
  pq->size++;
}
void QueuePop(Que* pq)
{
  assert(pq);
  assert(pq->head != NULL);
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
  pq->size--;
}
QDataType QueueFront(Que* pq)
{
  assert(pq);
  assert(pq->head != NULL);
  return pq->head->data;
}
QDataType QueueBack(Que* pq)
{
  assert(pq);
  assert(pq->head!=NULL);
  return pq->tail->data;
  
}
bool QueueEmpty(Que* pq)
{
  assert(pq);
  return pq->head == NULL;
}
int QueueSize(Que* pq)
{
  assert(pq);
  return pq->size;
}
typedef struct {
    Que q1,q2;
} MyStack;
MyStack* myStackCreate() {
    MyStack*pst=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);//->的优先级高于&,其实是&(pst->q1),将定义的结构体变量的地址传过去
    QueueInit(&pst->q2);
    return pst;
}
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}
int myStackPop(MyStack* obj) {
    Que*empty=&obj->q1;
    Que*nonEmpty=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        empty=&obj->q2;
        nonEmpty=&obj->q1;
    }
    //把非空队列的前size-1个元素push到空队列
    while(QueueSize(nonEmpty)>1)
    {
        QueuePush(empty,QueueFront(nonEmpty));
        QueuePop(nonEmpty);
    }
    int top=QueueFront(nonEmpty);
    QueuePop(nonEmpty);
    return top;
}
int myStackTop(MyStack* obj) {
    if(QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q2);
    }
    else
    {
        return QueueBack(&obj->q1);
    }
}
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);}
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}
/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

用栈实现队列🔭

力扣题目链接:用栈实现队列

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。

范例:

题目分析及思路

题目要求只使用栈的基本操作实现一个队列,这就需要两个栈进行‘合作’来完成。

例如,现在要往队列中 push 四个数据1,2,3,4。

创建两个栈,一个pushst,一个popst,如图,先将这四个数据push到 pushst 这个栈中。

现在,如果要实现队列的 pop 操作,就要将数据1 删除,但栈只能pop栈顶元素,所以只能先将pushst中的‘上面’的三个数据先导过来(取栈顶元素,再pop),然后数据1 就变成了 pushst 的栈顶元素,直接pop即可。

接下来,如果队列还需要 pop 数据的话,只需要在 popst 中 pop 即可。

如果要 push 数据,直接push 到pushst中,再次push后,如果要pop数据,需要将popst中的数据pop完后(直接取栈顶元素),将 pushst 中新push 的 n-1 个数据先导过去,再用上面的方式(出popst中的数据即可)。

总结:定义两个栈,队列需要push数据的时候,先往pushst中push数据(此时栈popst中为空),首次需要pop数据的时候,先将pushst中push的n-1个数据导入popst中,然后将最后一个元素pop掉,这就是队列要pop的头。当将n-1个数据导入popst中后,如果队列再要pop数据,就直接使用栈 popst 进行pop数据,入数据的时候就继续在pushst中压栈,当popst中的数据pop完了直接还要pop的话,就需要再将pushst中的n-1个元素导过去,如此往复…

力扣代码(含结构)

typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;//栈顶位置
  int capacity;//栈空间大小
}ST;
void STInit(ST* ps);
void STPush(ST* ps,STDataType x);
void STPrint(ST* ps);
void STPop(ST* ps);
void STDestroy(ST* ps);
STDataType STTop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
void STInit(ST* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}
void STPush(ST* ps, STDataType x)
{
  assert(ps);
  if (ps->capacity==ps->top)
  {
    int newcapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(ps->a));
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    ps->capacity = newcapacity;
    ps->a = tmp;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
void STPrint(ST* ps)
{
  assert(ps);
  int i = 0;
  for (i = 0; i < ps->top; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}
void STPop(ST* ps)
{
  assert(ps);
  assert(ps->top>0);
  (ps->top)--;
}
void STDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
STDataType STTop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
bool STEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}
typedef struct {
    ST pushst;
    ST popst;
} MyQueue;
MyQueue* myQueueCreate() {
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    STInit(&obj->pushst);
    STInit(&obj->popst);
    return obj;
}
void myQueuePush(MyQueue* obj, int x) {
    STPush(&obj->pushst,x);
}
int myQueuePop(MyQueue* obj) {
    int front=myQueuePeek(obj);
    STPop(&obj->popst);
    return front;
}
int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->popst))
    {
        while(STSize(&obj->pushst)>0)
        {
            STPush(&obj->popst,STTop(&obj->pushst));
            STPop(&obj->pushst);
        }
    }
    return STTop(&obj->popst);
}
bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->popst)&&STEmpty(&obj->pushst);
}
void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->pushst);
    STDestroy(&obj->popst);
    free(obj);
}

设计循环队列🧼

力扣题目链接:设计循环队列

范例:

个人理解:当我们使用数组(顺序表)来实现队列的时候,随着出数据的时候队头不断前移,那么队列的容量(队头到队尾)将会越来越小,如下图:

所以可以采用循环队列的方式来维持队列容量的恒定。

此题需要的空间固定为k,并且要将这些空间重复利用,所以采用用数组实现最为合适。

思路

开辟数组空间的时候‘多开一个’,利用数组的下标来控制队尾和队头的位置。

比如,当队列的长度为4的时候,就开辟5块空间的地址,最后一块空间用来把握队列长度来防止越界。当队头和队尾相等的时候,说明队列为空;当(队尾+1)%(k+1)等于队头的时候,说明队头和队尾之间只有一块空间的地址,说明队列已满。

力扣代码

typedef struct {
        int*a;
        int k;
        int front;
        int rear;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->k=k;
    obj->front=obj->rear=0;
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear+1)%(obj->k+1)==obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->rear]=value;
    obj->rear++;
    obj->rear%=obj->k+1;
    return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    obj->front++;
    obj->front%=obj->k+1;
    return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[(obj->rear+obj->k)%(obj->k+1)];
}
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    obj->a=NULL;
    free(obj);
    obj=NULL;
}
/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/
相关文章
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
4天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
99 5
|
3月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
73 0
|
3月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
332 9
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
55 1
|
3月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
116 21

热门文章

最新文章