1. Toy模板网首页
  2. > Toy博客

【数据结构】栈和队列选择题和面试编程题

7月前 作者：x一季花开成海x 分类：Toy博客 阅读(28) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】栈和队列选择题和面试编程题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

一、选择题

二、栈和队列的面试题

  1、括号匹配问题

     1.1 题目说明

     1.2 题目解析

  2、用队列实现栈

     2.1 题目说明

     2.2 题目解析

  3、用栈实现队列

     3.1 题目说明

     3.2 题目解析

一、选择题

1、若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是( C )

A: 1,4,3,2     B: 2,3,4,1      C: 3,1,4,2     D: 3,4,2,1

解析：A：先进1，然后出1，连续进2，3，4，然后出栈就是4,3,2.

           B：先进1,2，然后出2，再进3，然后出3，再进4，然后出4，最后再出1.

           C：先进1,2,3，然后出3，下一个出栈的要么是2，要么是4先进栈，然后4再出栈。

           D：先进1,2,3，然后出3，再进4，然后出4，接着再出2，再出1。

2、一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出 栈的顺序是( B )

A: 12345ABCDE      B: EDCBA54321       C: ABCDE12345       D: 54321EDCBA

3、现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设 队头不存放数据)    ( B )

A：(rear - front + N) % N + 1           B：(rear - front + N) % N

C：(rear - front) % (N + 1)               D：(rear - front + N) % (N - 1)

二、栈和队列的面试题

  1、括号匹配问题

     1.1 题目说明

      题目链接：括号匹配问题

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

      有效字符串需满足：

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

【数据结构】栈和队列选择题和面试编程题,面试,数据结构 

     1.2 题目解析

   思路：先让左括号入栈，当取到右括号时，就用这个右括号和进栈的左括号进行匹配，若能够成功匹配就接着往下，否则就返回false，当全部取完的时候都没有返回false时就返回true. 最后还要考虑栈不为空的情况：(1)如果都是左括号,形如“（（ ”,根本不出栈 ;(2)假如直接是空的字符串或者只有右括号。

typedef char STDataType;
typedef struct Stack
{
	STDataType* a;//数组
	int capacity;
	int top;   //初始为0，表示栈顶位置下一个位置的下标
}ST;

// 初始化栈
void StackInit(ST* ps);
//销毁
void StackDestory(ST* ps);

//入栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//获取栈顶元素
STDataType StackTop(ST* ps);

//获取栈中有效元素个数
int StackSize(ST* ps);

bool StackEmpty(ST* ps);

// 初始化栈
void StackInit(ST* ps)
{
	assert(ps);
	//ps->a = NULL;
	//ps->top = 0;
	//ps->capacity = 0;
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	ps->top = 0;
	ps->capacity = 4;
}
//销毁
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->capacity == ps->top)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}

	ps->a[ps->top] = x;
	ps->top++;
}
//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

//获取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

//获取栈中有效元素个数
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        if(*s == '[' || *s == '{' || *s == '(')
        {
            StackPush(&st,*s);
            s++;
        }
        else
        {
            if(StackEmpty(&st))
            {
                StackDestory(&st);
                return false;
            }
            char top = StackTop(&st);
            StackPop(&st);
            //不匹配
            if((*s == ']' && top != '[')
               || (*s == '}' && top != '{')
               || (*s == ')' && top != '('))
               {
                    StackDestory(&st);
                    return false;
               }
             else//继续
             {
                s++;
             }
        }
    }
    bool ret = StackEmpty(&st);//栈为空，为真(true)
    StackDestory(&st);
    return ret;
}

  2、用队列实现栈

     2.1 题目说明

      题目链接：用队列实现栈

      请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

      实现MyStack类：

  • void push(int x)  将元素 x 压入栈顶。
  • int pop()  移除并返回栈顶元素。
  • int top()  返回栈顶元素。
  • boolean empty()  如果栈是空的，返回 true ；否则，返回 false 。

【数据结构】栈和队列选择题和面试编程题,面试,数据结构

【数据结构】栈和队列选择题和面试编程题,面试,数据结构

     2.2 题目解析

用队列实现栈，队列的功能是先进先出，而栈功能是先进后出。 

思路：所以就要创建两个队列，让其中一个队列为空队列，然后另一个队列插入数据。删除数据时，有数据的队列开始出队列，直接进入另一个空队列中，直到先前有数据的队列出到size=1时，然后再删除数据。如果还要再入数据，就入到有数据的队列，保证另一个队列为空。

因此，我们需要自己先创建一个队列，然后再用队列实现栈。 【数据结构】栈和队列选择题和面试编程题,面试,数据结构

typedef int	QDataType;
// 链式结构：表示队列
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;
// 队列的结构
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

// 初始化队列
void QueueInit(Queue* pq);
// 销毁队列
void QueueDestroy(Queue* pq);

// 队尾入队列
void QueuePush(Queue* pq, QDataType x);
// 队头出队列
void QueuePop(Queue* pq);

// 获取队列头部元素
QDataType QueueFront(Queue* pq);
// 获取队列队尾元素
QDataType QueueBack(Queue* pq);

// 获取队列中有效元素个数
int QueueSize(Queue* pq);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq);

// 初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
// 销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
		//del = NULL;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

// 队尾入队列
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->tail == 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);
	}
	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;
}

// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{
	int size = 0;
	return pq->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL && pq->tail == NULL;
}



typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

//需要自己创建结构体，并进行初始化
MyStack* myStackCreate() {
    MyStack*obj = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }
    //非空队列的前n-1个数据倒入空队列
    while(QueueSize(nonemptyQ) > 1)
    {
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        QueuePop(nonemptyQ);
    }
    int top = QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);
    return top;
}

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->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) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

  3、用栈实现队列

     3.1 题目说明

      题目链接：用栈实现队列

      请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

      实现MyStack类：

  • void push(int x)  将元素 x 压入栈顶。
  • int pop()  移除并返回栈顶元素。
  • int top()  返回栈顶元素。
  • boolean empty()  如果栈是空的，返回 true ；否则，返回 false 。

【数据结构】栈和队列选择题和面试编程题,面试,数据结构

【数据结构】栈和队列选择题和面试编程题,面试,数据结构

     3.2 题目解析

思路：用两个栈实现队列，一个pushst栈，一个popst栈。只要插入数据，我们就将数据放到pushst栈中，想要删除数据，就可以直接删除popst栈中的数据，如果popst栈为空，就将pushst栈的全部数据放到popst栈中，直到popst栈为空时，再将pushst栈中的数据倒入到popst栈中。

【数据结构】栈和队列选择题和面试编程题,面试,数据结构

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;//数组
	int capacity;
	int top;   //初始为0，表示栈顶位置下一个位置的下标
}ST;

// 初始化栈
void StackInit(ST* ps);
//销毁
void StackDestory(ST* ps);

//入栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//获取栈顶元素
STDataType StackTop(ST* ps);

//获取栈中有效元素个数
int StackSize(ST* ps);

bool StackEmpty(ST* ps);

// 初始化栈
void StackInit(ST* ps)
{
	assert(ps);
	//ps->a = NULL;
	//ps->top = 0;
	//ps->capacity = 0;
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	ps->top = 0;
	ps->capacity = 4;
}
//销毁
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->capacity == ps->top)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}

	ps->a[ps->top] = x;
	ps->top++;
}
//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

//获取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

//获取栈中有效元素个数
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

typedef struct {
    ST pushst;
    ST popst;
} MyQueue;

bool myQueueEmpty(MyQueue* obj);
int myQueuePeek(MyQueue* obj);

//需要自己创建结构体，并进行初始化
MyQueue* myQueueCreate() {
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&pq->pushst);
    StackInit(&pq->popst);
    return pq;
}

void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    StackPush(&obj->pushst,x);
}

int myQueuePop(MyQueue* obj) {
    assert(obj);
    assert(!myQueueEmpty(obj));

    int peek = myQueuePeek(obj);
    StackPop(&obj->popst);
    return peek;
}

//对头
int myQueuePeek(MyQueue* obj) {
    assert(obj);
    assert(!myQueueEmpty(obj));

    //pushst中的数据倒入popst中
    if(StackEmpty(&obj->popst))
    {
        while(!StackEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->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);
}

本文要是有不足的地方，欢迎大家在下面评论，我会在第一时间更正。

【数据结构】栈和队列选择题和面试编程题,面试,数据结构

老铁们，记着点赞加关注!!! 

 文章来源地址https://www.toymoban.com/news/detail-520690.html

到了这里，关于【数据结构】栈和队列选择题和面试编程题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构选择题练习知识点整理【3】

    n 个点连通且无环的简单无向图为连通图，连通则至少有n-1条边，无环则只有n-1条边。n个点连通且无环的简单无向图有n-1条边，非零个数为2(n-1)，零元素个数为n^2-2(n-1)。得出零元素个数为n²-2n+2。 算术表达式 中缀、前缀、后缀的互相转换 中-前 从右到左 数字入栈，碰见运算

    2024年02月06日
    浏览(38)
  • 学堂在线THU-C++数据结构(上)-邓俊辉 选择题

    学堂在线THU-C++数据结构(上)-邓俊辉 选择题

    CTRL+F可进行页面搜索~૮꒰ ˶• ༝ •˶꒱ა The reverse number of a sequence is defined as the total number of reversed pairs in the sequence, and the total number of element comparisons performed by the insertion sort in the list of size n is: 一个序列的逆序数定义为该序列中的逆序对总数，规模为n的列表中插入排序进行

    2024年02月13日
    浏览(26)

  • 大数据题目集——选择题

    1：IBM提出的大数据的5V特点包括： ( ) 、高速、低价值密度、真实性。 大量、多样 2：大数据是由结构化数据、半结构化数据和 ( )数据组成的。 非结构化 3：Hadoop是一个数据管理系统，作为( ) 的核心，汇集了结构化和非结构化的数据。 数据分析 4：Hadoop是一个大规模( )，拥有

    2024年02月08日
    浏览(26)
  • 【数据结构】栈和队列(队列篇）

    【数据结构】栈和队列(队列篇）

    上期我们已经学习了数据结构中的栈，这期我们开始学习队列。 目录 1.队列的概念及结构 2.队列的实现 队列结构体定义 常用接口函数 初始化队列 队尾入队列 队头出队列 获取队列头部元素、 获取队列队尾元素 获取队列中有效元素个数 检测队列是否为空 销毁队列 3.循环队

    2024年02月13日
    浏览(33)

  • 大数据中的HBase的选择题

    (单选题)下列关于BigTable的描述,哪个是错误的? A. 爬虫持续不断地抓取新页面,这些页面每隔一段时间地存储到BigTable里 B. BigTable是一个分布式存储系统 C. BigTable起初用于解决典型的互联网搜索问题 D. 网络搜索应用查询建立好的索引,从BigTable得到网页 正确答案: A:爬虫持续不断地

    2024年02月04日
    浏览(31)
  • [数据结构】栈和队列

    [数据结构】栈和队列

    目录 1.栈 1.1概念 1.2 栈的使用 1.3.栈的模拟实现 2.队列 2.1概念 2.2队列的使用 2.3队列的模拟实现 2.4 循环队列 2.5双端队列   栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素

    2024年02月07日
    浏览(30)
  • 数据结构【栈和队列】

    数据结构【栈和队列】

    一、栈 1.定义：只允许一端进行插入和删除的线性表，结构与手枪的弹夹差不多，可以作为实现递归函数（调用和返回都是后进先出）调用的一种数据结构； 栈顶：允许插入删除的那端； 栈底：固定的，不允许插入或删除； 空栈：不含元素； 2.特点：后进先出； 3.操作：入

    2024年02月15日
    浏览(32)
  • 数据结构：栈和队列

    数据结构：栈和队列

    朋友们、伙计们，我们又见面了，本期来给大家解读一下栈和队列方面的相关知识点，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！ C 语 言 专 栏：C语言：从入门到精通 数据结构专栏：数据结构 个 人 主 页 ：  stackY、 目录 前言：  1.栈 1.1栈的

    2024年02月06日
    浏览(30)
  • 数据结构——栈和队列

    数据结构——栈和队列

    目录  一.前言 二.前文回顾 三.栈 3.1 栈的概念及结构 3.2 栈的实现 3.2.1 初始化函数 3.2.2 销毁函数 3.2.3 入栈函数 3.2.4 出栈函数 3.2.5 计算大小函数 3.2.6 空栈函数 3.2.7 获取栈顶函数  3.2.8 小测试 3.3 全部代码 四.栈的练习 4.1 有效的括号 五.队列 5.1队列的概念及结构 5.2 队列的实

    2024年01月25日
    浏览(33)
  • 数据结构 | 栈和队列

    数据结构 | 栈和队列

    … 📘📖📃本文已收录至：数据结构 | C语言 更多知识尽在此专栏中! 栈（Stack） 又名堆栈，它是一种运算受限的线性表，限定仅在表尾进行插入和删除操作的线性表。 队列（Queue） 也是一种特殊的线性表，特殊之处在于它只允许在表的前端（Front）进行删除操作，而在表的

    2024年01月23日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包