史上最强数据结构----栈和队列相关笔试面试题-6ren

史上最强数据结构----栈和队列相关笔试面试题

转载作者：知者更新时间：2024-03-13 02:27:43

1. 栈和队列面试题

1.1 括号匹配问题

题目：

思路：

首先将所给的字符串进行遍历，如果是左括号就将它压入栈中，根据栈后进先出的特性，然后逐个取出栈中的左括号与后面剩下的右括号进行逐对进行匹配，如果不匹配就返回false，如果都匹配了就返回true。

例如：

代码：

typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶的位置
	int capacity;//容量
}ST;
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 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 : 2 * ps->capacity;
		ps->a = (STDataType*)realloc(ps->a,sizeof(STDataType)*newCapacity);
		if (ps->a == NULL)
		{
			printf("fail malloc\n");
			exit(-1);
		}
		ps->capacity = newCapacity;
	}
	ps->a[ps->top++] = x;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	--ps->top;
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}
int SizeStack(ST* ps)
{
	assert(ps);
	return ps->top;
}
//前面的所有代码就是定义一个栈以及栈的相关函数
bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        if(*s=='['||*s=='('||*s=='{')
        {
            StackPush(&st,*s);
            ++s;
        }
        else
        {
            if(StackEmpty(&st))//当所给的字符串中只有右括号时直接返回false
            {
                StackDestory(&st);
                return false;
            }
            char top = StackTop(&st);//从栈中取一个左括号
            StackPop(&st);//进行出栈操作，让刚才取的字符出栈
            if((*s==']'&&top!='[')
            ||(*s=='}'&&top!='{')
            ||(*s==')'&&top!='('))//两个字符不相匹配的情况下直接返回false
            {
                StackDestory(&st);
                return false;
            }
            else
            {
                ++s;
            }
        }
    }
    //栈为空，说明所有左括号都匹配了
    bool ret =  StackEmpty(&st);//判断是否只有左括号，如果只有左括号此时ret就为false，如果前面都已经匹配完了ret就等于true
    StackDestory(&st);
    return ret;
}

1.2 用队列实现栈

解析上面的实例：

输入的第一行是执行的操作。第二行是执行操作的数据。

输出是对应的返回值。

思路：用两个队列实现栈。

栈的基本结构：

1、入栈，push数据到不为空的队列。

2、出栈，把不为空的队列的数据前N-1导入到另一个空队列，最后剩下的一个删掉。

代码：

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);
size_t QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head =pq->tail = NULL;
}
QNode* BuyQNode(QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("fail malloc\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = BuyQNode(x);
	if (pq->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->tail&&pq->head);
	if (pq->head->next==NULL)//处理只有一个节点的时候
	{
		free(pq->tail);
		pq->tail = pq->head = NULL;
	}
	else//有多个节点
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
size_t QueueSize(Queue* pq)
{
	assert(pq);
	size_t size = 0;
	QNode* cur = pq->head;
	while (cur!= pq->tail->next)
	{
		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;
}
void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head==NULL&&pq->tail==NULL;
}
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    assert(pst);
    QueueInit(&pst->q1);//这一行代码和后面这一行代码等价:QueueInit(&(pst->q1));
    QueueInit(&pst->q2);//这一行代码和后面这一行代码等价: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) {
    assert(obj);
    Queue *emptyQ = &obj->q1;
    Queue*nonEmptyQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ = &obj->q2;
        nonEmptyQ = &obj->q1;
    }
    //把非空队列的前N个数据，导入空队列，剩下一个删掉
    //就实现了后进先出
    while(QueueSize(nonEmptyQ)>1)
    {
        QueuePush(emptyQ,QueueFront(nonEmptyQ));//将非空队列的队头数据push到非空队列中
        QueuePop(nonEmptyQ);//将非空队列的队头数据出队
    }
    QDataType top = QueueFront(nonEmptyQ);
    QueuePop(nonEmptyQ);
    return top;
}

int myStackTop(MyStack* obj) {
    assert(obj);
    
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
   
}
bool myStackEmpty(MyStack* obj) {
    assert(obj);
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    assert(obj);
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    free(obj);
}

1.3 用栈实现队列

思路：

注意：在上面的代码中，在进行出队操作时，只要popST这个栈中有数据，那么我们就不进行倒数据的操作（即将push中的数据倒到popST这个栈中），只有当pop中的数据为空且我们要进行出队时才进行倒数据。

队列结构：

代码：

typedef int STDataType;
//数组栈的实现
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶的位置
	int capacity;//容量
}ST;
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 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 ? 2 : 2 * ps->capacity;
		STDataType*new = (STDataType*)realloc(ps->a,sizeof(STDataType)*newCapacity);
		if (new == NULL)
		{
			printf("fail malloc\n");
			exit(-1);
		}
		ps->a = new;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top++] = x;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	--ps->top;
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}
int SizeStack(ST* ps)
{
	assert(ps);
	return ps->top;
}
void StackInit(ST*ps);
void StackDestory(ST* ps);
void StackPush(ST* ps,STDataType x);
void StackPop(ST* ps);
bool StackEmpty(ST* ps);
int SizeStack(ST* ps);
STDataType StackTop(ST* ps);
typedef struct {
    ST pushST;
    ST popST;
} MyQueue;

MyQueue* myQueueCreate() {
    MyQueue * myQueue = (MyQueue*)malloc(sizeof(MyQueue));
    assert(myQueue);
    StackInit(&myQueue->pushST);
    StackInit(&myQueue->popST);
    return myQueue;
}

void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    StackPush(&obj->pushST,x);//入队直接向pushST插入即可
}

int myQueuePop(MyQueue* obj){
    assert(obj);
    if(StackEmpty(&obj->popST))//push为空，就进行倒数据，就符合先进先出的顺序了
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    STDataType ret = StackTop(&obj->popST);//临时保存返回的数据
    StackPop(&obj->popST);
    return ret;
}

int myQueuePeek(MyQueue* obj) {
    assert(obj);
    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);
}

1.4 设计循环队列

为了避免空和满混淆，无法区分，多开一个空间。

1. front = tail时是空

2. tail下一个位置是front时是满

满的两种情况：

1、obj->tail = k && obj->head = 0

2、obj->tail+1 = obj->head

代码：

typedef struct {
    int *a;
    int head;//循环队列的头
    int tail;//循环队列的尾
    int capacity;//循环队列元素的最大数目
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj);//判断循环队列是否为空的声明
bool myCircularQueueIsFull(MyCircularQueue* obj);//判断循环队列是否为满的声明
MyCircularQueue* myCircularQueueCreate(int k) //循环队列的初始化
{
    MyCircularQueue*myCircularQ = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    assert(myCircularQ);
    int *tmp = (int*)malloc(sizeof(int)*(k+1));
    assert(tmp);
    myCircularQ->a = tmp;
    myCircularQ->head = 0;
    myCircularQ->tail = 0;
    myCircularQ->capacity = k;
    return myCircularQ;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //向循环队列插入一个元素，如果成功插入则返回真。
{
    assert(obj);
    if(myCircularQueueIsFull(obj))//满了的情况
    {
        return false;
    }
    obj->a[obj->tail] = value;
    if(obj->tail==obj->capacity)//此时已经到达了开辟数组的最后一个位置，tail再进行++操作后会跳跃到第一个位置
    {
        obj->tail = 0;
    }
    else
    {
        ++obj->tail;
    }
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) //从循环队列中删除一个元素，如果成功删除则返回真。
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))//循环队列中为空的情况
    {
        return false;
    }
    if(obj->head==obj->capacity)//循环队列中的head在开辟的最后的一个空间位置的情况，head要发生跳跃
    {
        obj->head = 0;
    }
    else
    {
        ++obj->head;
    }
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) //从队首获取元素，如果队列为空，返回 -1 。
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))//队列元素为空的情况
        return -1;
    return obj->a[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj)//获取队尾元素，如果队列为空，返回 -1 。
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))//循环队列元素为空的情况
        return -1;
    if(obj->tail==0)//尾在头的时候，就要返回最后一个空间的位置
    {
        return obj->a[obj->capacity];
    }
    else
    {
        return obj->a[obj->tail-1];//正常情况返回tail的前一个位置
    }
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) //判断循环队列是否满
{
    assert(obj);
    return obj->tail==obj->head;//尾下标等于头下标的时候就是空
}

bool myCircularQueueIsFull(MyCircularQueue* obj) //判断循环队列是否满
{
    assert(obj);
    if(obj->tail==obj->capacity && obj->head==0)//判断的是尾下标指向最后一块空间，头下标在最靠前的空间
    {
        return true;
    }
    else
    {
        return obj->tail+1 ==obj->head;
    }
}  

void myCircularQueueFree(MyCircularQueue* obj) //循环队列的销毁
{
    assert(obj);
    free(obj->a);
    free(obj);
}

2. 概念选择题

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

A 12345ABCDE

B EDCBA54321

C ABCDE12345

D 54321EDCBA

2.若进栈序列为 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

解析：C选项中，3出来之后要想出1的话，就必须先出2。

3.循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作后， front=rear=99 ，则循环队列中的元素个数为（ D）

A 1

B 2

C 99

D 0

解析：由前面循环队列的实现，很容易就得知此时元素的个数为0。

4.以下( )不是队列的基本运算？（B）

A 从队尾插入一个新元素

B 从队列中删除第i个元素

C 判断一个队列是否为空

D 读取队头元素的值

5.现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N，实际最多存储N - 1个数据。其队内有效长度为（B）(假设队头不存放数据)

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

B (rear - front + N) % N

C ear - front) % (N + 1)

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

解析：此题要考虑两种情况：

第一种情况：front在rear的前面

第二种情况：front在rear的后面

注意：从最后绕到了最前面其实就相当于在最后面越界继续相加！如下图所示：

综合上面两种情况：最终公式为：

count = (rear - front + N ) % N （为什么第一种也加了N？因为对于front在rear前面的情况来说，是否加N对结果没有任何的影响，因为还要对N进行取模操作）

3. 栈和队列的用途

栈：用来解决括号匹配，逆波兰表达式的求解，递归改非递归等等。

队列：公平排队，广度优先遍历等等。

文章推荐： Double-Check 的单例

文章推荐： Java-Freemarker

文章推荐： IntelliJ IDEA 远程debug调试

文章推荐： .gitignore教程

数据结构-栈
栈一种常见的特殊线性数据结构，其特殊之处在于其操作顺序，下面会详细介绍，也正因为其特性，因此栈可以轻松解决表达式求值、括号匹配、递归算法、回溯算法等等问题。 01、定义栈的特殊性表现为操作受
擅长处理临时数据的结构——栈
目录实践1 —— 从字符串中移除星号栈和数组存储数据的方式一样，它们都只是元素的列表。不同之处在于栈的以下3个限制：数据只能从栈末插入；数据只
java数据结构基础:栈
准备工作工具：idea+jdk8 技术要求：java基础语法编码环节首先，我们得先确定下来，用什么数据来模拟栈的操作。由于是一个一个的元素放入栈里面，我们可以考虑用数组来实现。
Python数据结构与算法（3.1）——栈
0. 学习目标栈和队列是在程序设计中常见的数据类型，从数据结构的角度来讲，栈和队列也是线性表，是操作受限的线性表，它们的基本操作是线性表操作的子集，但从数据类型的角度来讲，它们与线性表又有着巨大的不
java - 栈、堆和递归
在可以使用递归(在堆栈中存储状态)和对象创建(在堆中创建新对象)的场景中。问题在对象创建和递归之间进行选择时应考虑哪些参数？我的研究得出以下结论(需要验证这一点) 当可用内存较少时:使用递归可
c - 栈、堆中的内存是如何排列的？
下面是我编写的用于检查内存对齐的示例程序。 Pavan@Pavan-pc:~/working_dir/pavan/C$ cat mem3.c #include #include
iphone - UINavigationController 栈
Instapaper 和 Twitterrific 等应用启动的 View 不是其导航堆栈的 Root View 。我们知道这一点，因为初始 View 已经有一个后退按钮。 Instapaper 推出
android - Activity 栈
有没有办法在调试或正常运行期间的某个时刻可视化 Activity 堆栈？最佳答案您可以通过 Activity 管理器获取一些有用的信息。 ActivityManager manag
创建一个基本的协议(protocol)栈
我想编写一个应用层协议(protocol)，在发送 GET 请求时使用 TCP 返回特定的 ASCII 文本。我读了第一HTTP specification和 the SMTP specificati
JAVA中堆、栈，静态方法和非静态方法的速度问题
1、堆和栈的速度性能分析堆和栈是jvm内存模型中的2个重要组成部分，自己很早以前也总结过堆和栈的区别，基本都是从存储内
算法系列15天速成第十天栈
一：概念栈，同样是一种特殊的线性表，是一种last in first out（lifo)的形式，现实中有很多这样的例子，
java中stack(栈)的使用代码实例
java中stack类继承于vector,其特性为后进先出(lastinfirstout). 入栈和出栈实例图: 实例图的java代码实例: ?
Java实现单链表、栈、队列三种数据结构
1、单链表 1、在我们数据结构中，单链表非常重要。它里面的数据元素是以结点为单位，每个结点是由数据元素的数据和下一个结点的地址组成，在java集合框架里面 LinkedList、Ha
Python编程实现双链表，栈，队列及二叉树的方法示例
本文实例讲述了Python编程实现双链表，栈，队列及二叉树的方法。分享给大家供大家参考，具体如下： 1.双链表 ?
assembly - ARM中的SP(栈)和LR是什么？
我一遍又一遍地阅读定义，但我仍然不明白ARM中的SP和LR是什么？我了解PC(它显示下一条指令的地址)，SP和LR可能类似，但我只是不明白它是什么。你能帮我一下吗？编辑:如果你能用例子来解释它，那就
java - 数组链表栈
我必须使用索引 0 作为堆栈的顶部，并且在实现此操作时遇到问题。我得到了所有 null，但输出 100、200 和 300 是我得到的唯一数字。我忽略的实现有什么问题吗？ push 方法应该实现 Ar
java - 汉诺塔与 Java 栈
我正在用 Java 解决汉诺塔问题。我选择使用 Stacks 作为钉子，除了 move 方法之外，一切都正常。我有规范和 JUnit 测试类，目前通过了 7 项测试中的 6 项，但在移动测试中失败了。
c++ - 关于内存管理、栈、堆的问题
这个问题在这里已经有了答案: 关闭 11 年前。 Possible Duplicate: Does this type of memory get allocated on the heap or
ios - 导航 Controller 栈
首先，抱歉我的英语不好。我将尝试解释我的问题: 我有一个 RootViewController(基于导航的项目)。因此，它显示了表格 View ，当用户选择表格的一行 (didSelectRowAtI
java - OOP 和堆/栈
我有一个看起来像这样的类 class A { int b; void B() { int c; } } int main() { A asdf;

知者

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城