栈和队列详解

2024-08-02 08:08:34 浏览数 (2)

1. 栈

1.1 栈的概念及结构

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈，出数据也在栈顶。

栈的结构栈的结构
1.2 栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小。（如果要用单链表，就是在头上插入删除，因为在尾上删除要找尾的前一个节点，很麻烦）

代码语言：javascript复制
//Stack.h

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int 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);
代码语言：javascript复制
//Stack.c

#include "Stack.h"

void STInit(ST* ps)
{
	assert(ps);

	ps->a = NULL;
	ps->top = 0;//top指向栈顶元素的下一个
	//ps->top = -1;//top指向栈顶元素
	ps->capacity = 0;
}

void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

//栈顶
void STPush(ST* ps, STDataType x)
{
	assert(ps);

	//满了，扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = 0 == ps->capacity ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));

		if (NULL == tmp)
		{
			perror("realloc fail");
			return;
		}

		ps->a = tmp;
		ps->capacity = newcapacity;
	}

	ps->a[ps->top] = x;
	ps->top  ;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	return ps->a[ps->top - 1];
}

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

bool STEmpty(ST* ps)
{
	assert(ps);

	return 0 == ps->top;
}
代码语言：javascript复制
//test.c

#include "Stack.h"

int main()
{
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPush(&s, 5);

	while (!STEmpty(&s))
	{
		int top = STTop(&s);
		printf("%d ", top);
		STPop(&s);
	}

	STDestroy(&s);

	return 0;
}

注：

  1. 栈的用途有很多，只要满足后进先出原则的基本都要用到栈
  2. 在递归改成非递归时，也可以用到栈
  3. 深度优先遍历（dfs）可以用递归，也可以用栈
  4. 这里的栈和之前讲过的内存区域划分里的栈区是两个东西，几乎没有什么关联

2. 队列

2.1 队列的概念及结构

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

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

队列队列

队列的功能：保障公平性的排队（比如抽号机）；广度优先遍历（bfs）

2.2 队列的实现

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

首先定义一下队列节点的结构体：

代码语言：javascript复制
typedef int QDataType;

typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

接着是入队列和出队列：

代码语言：javascript复制
//入队列
void QueuePush(QNode** pphead, QDataType x);
//出队列
void QueuePop(QNode** pphaed);

如果这样写你会发现每次入队列都要找尾，很麻烦，所以我们可以再定义一个尾结点指针：

代码语言：javascript复制
//入队列
void QueuePush(QNode** pphead, QNode** pptail, QDataType x);
//出队列
void QueuePop(QNode** pphaed, QNode** pptail);

当我们传多个参数时，我们可以把它们定义成一个结构体再进行传参：

代码语言：javascript复制
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

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

这样写同时还把二级指针变成了一级指针。

这时有小伙伴就会问了：当时学习单链表的时候为什么就传一个头节点指针，而不传尾节点指针呢？

这是因为单链表不仅要实现尾插，还要实现尾删，有了尾节点依然找不到尾节点的前一个节点来实现尾删的操作，所以就没必要传尾节点的指针了。

而队列只需要实现尾插和头删，有了尾节点指针就可以很好的避免遍历链表找尾的操作，时间复杂度变低了，因此我们要传尾节点指针。

解决了这个问题之后，我们完整的把队列需要实现的功能列出来：

代码语言：javascript复制
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>

typedef int QDataType;

typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	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);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
代码语言：javascript复制
#include "Queue.h"

void QueueInit(Queue* pq)
{
	assert(pq);

	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->phead;

	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

//入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));

	if (NULL == newnode)
	{
		perror("malloc fail");
		return;
	}

	newnode->val = x;
	newnode->next = NULL;

	if (pq->ptail)
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	else
	{
		pq->phead = pq->ptail = newnode;
	}

	pq->size  ;
}

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);

	//0个节点
	//温柔检查
	//if (NULL == pq->phead)
	//{
	//	return;
	//}

	//暴力检查
	assert(pq->phead != NULL);

	//一个节点
	//多个节点
	if (NULL == pq->phead->next)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}

	pq->size--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);

	//暴力检查
	assert(pq->phead != NULL);

	return pq->phead->val;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);

	//暴力检查
	assert(pq->ptail != NULL);

	return pq->ptail->val;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return 0 == pq->size;
}

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}
代码语言：javascript复制
#include "Queue.h"

int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	
	QueueDestroy(&q);

	return 0;
}

3. 栈和队列面试题

  1. 括号匹配问题
括号匹配问题括号匹配问题
代码语言：javascript复制
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void STInit(ST* ps)
{
	assert(ps);

	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void STPush(ST* ps, STDataType x)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		int newcapacity = 0 == ps->capacity ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));

		if (NULL == tmp)
		{
			perror("realloc fail");
			return;
		}

		ps->a = tmp;
		ps->capacity = newcapacity;
	}

	ps->a[ps->top] = x;
	ps->top  ;
}

bool STEmpty(ST* ps)
{
	assert(ps);

	return 0 == ps->top;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	return ps->a[ps->top - 1];
}

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}


bool isValid(char* s)
{
	ST st;
	STInit(&st);

	while (*s)
	{
		if ('[' == *s || '(' == *s || '{' == *s)
		{
			STPush(&st, *s);
		}
		else
		{
			//右括号比左括号多
			if (STEmpty(&st))
			{
				STDestroy(&st);//在返回前释放动态申请的空间，防止内存泄漏
				return false;
			}

			char top = STTop(&st);
			STPop(&st);

			//符号不匹配
			if (('[' == top && *s != ']')
				|| ('(' == top && *s != ')')
				|| ('{' == top && *s != '}'))
			{
				STDestroy(&st);//在返回前释放动态申请的空间，防止内存泄漏
				return false;
			}
		}

		  s;
	}

	//左括号比右括号多，栈不为空
	bool ret = STEmpty(&st);
	STDestroy(&st);
	return ret;
}
  1. 用队列实现栈
用队列实现栈用队列实现栈
代码语言：javascript复制
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int QDataType;

typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

void QueueInit(Queue* pq)
{
	assert(pq);

	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->phead;

	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));

	if (NULL == newnode)
	{
		perror("malloc fail");
		return;
	}

	newnode->val = x;
	newnode->next = NULL;

	if (pq->phead)
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	else
	{
		pq->phead = pq->ptail = newnode;
	}

	pq->size  ;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead != NULL);

	if (NULL == pq->phead->next)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	
	pq->size--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead != NULL);

	return pq->phead->val;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail != NULL);

	return pq->ptail->val;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return 0 == pq->size;
}

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}


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


MyStack* myStackCreate()
{
	MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
	QueueInit(&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)
{
	//不为空前n-1导入另一个队列，删掉最后一个
	Queue* pEmptyQ = &obj->q1;
	Queue* pNonEmptyQ = &obj->q2;

	if (!QueueEmpty(&obj->q1))
	{
		pEmptyQ = &obj->q2;
		pNonEmptyQ = &obj->q1;
	}

	//不为空前n-1导入另一个空队列
	while (QueueSize(pNonEmptyQ) > 1)
	{
		int front = QueueFront(pNonEmptyQ);
		QueuePush(pEmptyQ, front);
		QueuePop(pNonEmptyQ);
	}

	int front = QueueFront(pNonEmptyQ);
	QueuePop(pNonEmptyQ);

	return front;
}

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);
}
  1. 用栈实现队列
用栈实现队列用栈实现队列
代码语言：javascript复制
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void STInit(ST* ps)
{
	assert(ps);

	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void STPush(ST* ps, STDataType x)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		int newcapacity = 0 == ps->capacity ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));

		if (NULL == tmp)
		{
			perror("realloc fail");
			return;
		}

		ps->a = tmp;
		ps->capacity = newcapacity;
	}

	ps->a[ps->top] = x;
	ps->top  ;
}

bool STEmpty(ST* ps)
{
	assert(ps);

	return 0 == ps->top;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	return ps->a[ps->top - 1];
}

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}


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 myQueuePeek(MyQueue* obj)
{
	if (STEmpty(&obj->popst))
	{
		//pushst的数据导入到popst
		while (!STEmpty(&obj->pushst))
		{
			int top = STTop(&obj->pushst);
			STPop(&obj->pushst);
			STPush(&obj->popst, top);
		}
	}

	return STTop(&obj->popst);
}

int myQueuePop(MyQueue* obj)
{
	int front = myQueuePeek(obj);
	STPop(&obj->popst);

	return front;
}

bool myQueueEmpty(MyQueue* obj)
{
	return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}

void myQueueFree(MyQueue* obj)
{
	STDestroy(&obj->popst);
	STDestroy(&obj->pushst);
	free(obj);
}

注： 在定义队列结构体时，如果里面定义成ST* pushst ，那么下面的初始化就会出现问题，因为malloc队列结构体的时候只开辟了两个指针的空间，这两个指针是野指针；而如果定义的是ST pushst，那么开辟的就是栈结构体的空间，取它的地址进行初始化是没有问题的。如果要用ST* pushst定义，可以先malloc一块空间给pushst，然后再调用STInit函数。（同理，上面的第二题也是这个道理）

  1. 设计循环队列
设计循环队列（1）设计循环队列（1）
设计循环队列（2）设计循环队列（2）
设计循环队列（3）设计循环队列（3）
代码语言：javascript复制
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct
{
	int* a;
	int front;//指向头
	int rear;//指向尾下一个
	int k;
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k)
{
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	//多开一个解决假溢出问题
	obj->a = (int*)malloc(sizeof(int) * (k   1));
	obj->front = 0;
	obj->rear = 0;
	obj->k = k;

	return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
	return obj->front == obj->rear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj)
{
	//int rearNext = obj->rear   1;
	//if (rearNext == obj->k   1)
	//{
	//	rearNext = 0;
	//}

	//return rearNext == obj->front;

	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;
	}
	else
	{
		return obj->a[obj->front];
	}
}

int myCircularQueueRear(MyCircularQueue* obj)
{
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	else
	{
		return obj->a[(obj->rear - 1   obj->k   1) % (obj->k   1)];
	}
}

void myCircularQueueFree(MyCircularQueue* obj)
{
	free(obj->a);
	obj->a = NULL;
	free(obj);
}

4. 概念选择题

  1. 一个栈的初始状态为空，现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ） A. 12345ABCDE B. EDCBA54321 C. ABCDE12345 D. 54321EDCBA 答案：B
  2. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（ ） A. 1,4,3,2 B. 2,3,4,1 C. 3,1,4,2 D. 3,4,2,1 答案：C
队列 链表 数据 指针 ps

0 人点赞