【数据结构】栈和队列

IT编程爱好者

发布于 2023-04-12 14:08:36

1740

发布于 2023-04-12 14:08:36

文章被收录于专栏：C/C++爱好者

数据结构之栈和队列：：

1.栈的实现

栈的概念及结构： 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，进行数据插入和删除的一端。称为栈顶，另一端称为栈底，栈中的数据元素遵守先进后出LIFO(Last in First Out)的原则。压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。出栈：栈的删除操作叫做出栈，出数据也在栈顶。

栈的实现： 栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小。 注：如果用链表实现，建议头部做栈顶，尾部做栈底。 注：栈的后进先出指的是同时在栈里面。

Stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//静态栈
/*#define N 100
typedef int STDataType;
struct Stack
{
	STDataType a[N];
	int top;
};*/
//动态栈
typedef char STDataType;
typedef struct Stack
{
	STDataType * a;
    int top;
	int capacity;
}ST;
void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
//访问栈顶数据
STDataType StackTop(ST* ps);

Stack.c

#include"Stack.h"
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
void Destory(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 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
		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];
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

2.队列的实现

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

队列的实现： 队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。一个入队列顺序对应一个出队列顺序一个入栈顺序对应多个出栈顺序。

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
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);

Queue.c

#include"Queue.h"
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);
	}
	else
	{
		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);
		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);
	/*QNode* cur = pq->head;
	int n = 0;
	while (cur)
	{
		++n;
		cur = cur->next;
	}
	return n;*/
	return pq->size;
}

另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列，如操作系统课程讲解生产者消费者模型时就可以使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

3.栈和队列面试题

1.括号匹配问题

有效的括号
1.左括号入栈
2.右括号 出栈栈顶元素进行比较
将上面的栈拷贝下来
bool isValid(char* s)
{
	ST st;
	StackInit(&st);
	while (*s)
	{
		if (*s == '{' || *s == '[' || *s == '(')
		{
			StackPush(&st, *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;
			}
		}
		++s;
	}
	栈不为空 说明数量不匹配
	bool flag = StackEmpty(&st);
	StackDestory(&st);
	return flag;
}

2.用队列实现栈

用队列实现栈
用两个队列实现一个后入先出的栈
思路：入数据的时候，保持一个为空，出数据的时候，往空的队列导入数据
注：越界的检查是一种抽查，且一般读时不会报错，写的时候要根据编译器的严格程度
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 myStackTop(MyStack* obj)
{
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}
int myStackPop(MyStack* obj)
{
	Queue* empty = &obj->q1;
	Queue* nonEmpty = &obj->q2;
	if (!QueueEmpty(&obj->q1))
	{
		empty = &obj->q2;
		nonEmpty = &obj->q1;
	}
	非空队列前N-1个导入空队列 剩下一个就是栈顶元素
	while (QueueSize(nonEmpty) > 1)
	{
		QueuePush(empty, QueueFront(nonEmpty));
		QueuePop(nonEmpty);
	}
	int top = QueueFront(nonEmpty);
	QueuePop(nonEmpty);
	return top;
}
bool myStackEmpty(MyStack* obj)
{
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj)
{
	QueueDestory(&obj->q1);
	QueueDestory(&obj->q2);
	free(obj);
}

3.用栈实现队列

用栈实现队列
typedef struct
{
	ST pushST;
	ST popST;
}MyQueue;
MyQueue* myQueueCreate()
{
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	StackInit(&obj->pushST);
	StackInit(&obj->popST);
	return obj;
}
void myQueuePush(MyQueue* obj, int x)
{
	StackPush(&obj->pushST, x);
}
void PushSTToPopST(MyQueue* obj)
{
	if (StackEmpty(&obj->popST))
	{
		while (!StackEmpty(&obj->pushST))
		{
			StackPush(&obj->popST, StackTop(&obj->pushST));
			StackPop(&obj->pushST);
		}
	}
}
删除队头元素并返回
int myQueuePop(MyQueue* obj)
{
	PushSTToPopST(obj);
	int front = StackTop(&obj->popST);
	StackPop(&obj->popST);
	return front;
}
返回队头元素
int myQueuePeek(MyQueue* obj)
{
	PushSTToPopST(obj);
	return StackTop(&obj->popST);
}
bool myQueueEmpty(MyQueue* obj)
{
	return StackEmpty(&obj->popST)
		&& StackEmpty(&obj->pushST);
}
void myQueueFree(MyQueue* obj)
{
	StackDestory(&obj->pushST);
	StackDestory(&obj->popST);
	free(obj);
}

4.设计循环队列

设计循环队列
注：back指向队尾的下一个位置 front指向队头
无法区分空和满的解决方法：
1.加一个size size为0即为空 size为k即为满
2.增加一个空间 满的时候永远留一个空位置 长度为4 开5个空间
满了的标志：back位置下一个是front就满了
typedef struct
{
	int* a;
	int front;
	int back;
	int N;//记录能存多少个数据
}MyCircularQueue;
MyCircularQueue* myCircularQueue(int k)
{
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	obj->a = (int*)malloc(sizeof(int) * (k + 1));
	obj->front = obj->back = 0;
	obj->N = k + 1;//队列中的空间个数
	return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
	return obj->front == obj->back;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
	return ((obj->back + 1) % (obj->N)) == (obj->front);
}
//向循环队列插入一个元素 如果成功就返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
	if (myCircularQueueIsFull(obj))
		return false;
	obj->a[obj->back] = value;
	obj->back++;
	//控制如果到空间尾以后 back回到0的位置
	obj->back %= obj->N;
	return true;
}
//向循环队列中删除一个元素 如果成功就返回真
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
	if (myCircularQueueIsEmpty(obj))
		return false;
	obj->front++;
	//控制如果到空间尾以后 back回到0的位置
	obj->front %= obj->N;
	return true;
}
//取队头数据
int myCircularQueueFront(MyCircularQueue* obj)
{
	if (myCircularQueueIsEmpty(obj))
		return -1;
	else
		return obj->a[obj->front];
}
//取队尾数据
int myCircularQueueRear(MyCircularQueue* obj)
{
	/*if (myCircularQueueIsEmpty(obj))
		return -1;
	else if (obj->back == 0)
		return obj->a[obj->N - 1];
	else
		return obj->a[obj->back - 1];*/
	if (myCircularQueueIsEmpty(obj))
		return -1;
	else if (obj->back == 0)
		return obj->a[(obj->back - 1 + obj->N) % obj->N];
}
void myCircularQueueFree(MyCircularQueue* obj)
{
	free(obj->a);
	free(obj);
}

概念选择题：

1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出
栈的顺序是（ ）。
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA
1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出
栈的顺序是（ ）。
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA
3.循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作
后， front=rear=99 ，则循环队列中的元素个数为（ ）
A 1
B 2
C 99
D 0或者100
4.以下( )不是队列的基本运算？
A 从队尾插入一个新元素
B 从队列中删除第i个元素
C 判断一个队列是否为空
D 读取队头元素的值
5.现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设多给一个空间，实际空间大小为N)
A (rear - front + N) % N + 1
B (rear - front + N) % N
C ear - front) % (N + 1)
D (rear - front + N) % (N - 1)
注：(4 - 0 + 5) % 5 front在前 back在后
注：(0 - 4 + 5) % 5 back在前  front在后
答案：
1.B
2.C
3.D
4.B
5.B

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-02-27，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构