数据结构之栈与队列的实现与详细解析

个人主页：点我进入主页

专栏分类：C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶

C语言刷题       数据结构初阶

欢迎大家点赞，评论，收藏。

一起努力，一起奔赴大厂。

目录

1.前言

2.栈

2.1栈的概念与性质

2.2栈的实现

3.队列

3.1队列的概念

3.2队列的实现

4.练习

4.1编程

4.2概念

1.前言

        在前面我们写了关于链表和顺序表的内容，我们很容易知道顺序表相当于数组，链表是不连续的空间连在一起，顺序表和链表是我们学习数据结构的一个重要的基础，今天我们主要讲解的是两个重要的结构栈和队列，这两个结构既可以使用顺序表实现也可以使用链表实现，顺序表和链表哪一个更好呢？这需要我们知道栈和队列是如何进行数据的存储的，这与他们数据存储的性质有关，接下来让我们看看栈与队列的具体实现吧。

2.栈

2.1栈的概念与性质

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

栈满足数据的先进后出的原则，例如我们让1，2，3，4，5依次入栈，我们出栈先出栈的是数字5。既然栈是先进后出我们用数组进行数据的存储还是用链表进行数据的存储呢，先进后出也就是说我们呢访问需要栈知道栈顶的位置，但是我们在数据入栈时链表相对来说比较困难，所有我们在选择栈的存储时一半使用数组。

2.2栈的实现

        在栈的操作中，我们包括栈的初始化，入栈，出栈，栈空，增容，取栈顶元素，栈中元素个数，遍历，释放空间这几个操作。

void InItStack(Stack* s)
{
    assert(s);
    s->capacity = 4;
    s->top = -1;
    s->data = (char*)malloc(sizeof(char) * s->capacity);
}
void CheckCapacity(Stack* s)
{
    assert(s);
    if (s->top + 1 == s->capacity)
        s->capacity += 2;
    char* p = (char*)realloc(s->data, sizeof(char) * s->capacity);
    if (p == NULL)
    {
        perror("realloc fail");
        return;
    }
    else
        s->data = p;
}
void StackPush(Stack* s, char ch)
{
    assert(s);
    CheckCapacity(s);
    s->data[++s->top] = ch;
}
bool StackEmpty(Stack* s)
{
    assert(s);
    if (s->top == -1)
        return true;
    return false;
}
char StackPop(Stack* s)
{
    assert(s);
    if (!StackEmpty(s))
    {
        s->top--;
        return s->data[s->top + 1];
    }
    return '1';
}
void StackDestory(Stack* s)
{
    assert(s);
    free(s->data);
}
int StackSize(Stack* s)
{
    assert(s);
    return s->top + 1;
}
int StackTopdata(Stack* s)
{
    assert(s);
    return s->data[s->top];
}

        在函数实现时我们有几点需要注意，首先我们需要将栈顶初始化为-1，主要原因是如果我们初始化为0的话，栈为空判断起来比较麻烦，初始化为-1就很容易判断。还有就是当我们操作执行完后我们需要将空间进行释放。

3.队列

3.1队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

3.2队列的实现

        在队列的操作中我们包括对队列的初始化，队列节点的创建，出队，入队，取队顶元素，对空，遍历，队列元素个数，释放空间。

typedef struct QNode {
	int data;
	struct QNode* next;
}QNode;
typedef struct Queue {
	struct QNode* head;
	struct QNode* tail;
}Queue;
void QueueInit(Queue* q)
{
	assert(q);
	q->head = NULL;
	q->tail = NULL;
}
QNode* QueueCreate(Queue* q, int x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void QueuePush(Queue* q, int x)
{
	QNode* newnode = QueueCreate(q, x);
	if (q->head == NULL)
	{
		q->head = newnode;
		q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
}
bool QueueEmpty(Queue* q)
{
	return q->head == NULL;
}
int QueuePop(Queue* q)
{
	assert(q);
 
	if (!QueueEmpty(q))
	{
		int data = q->head->data;
		if (q->head == q->tail)
		{
 
			free(q->head);
			q->head = q->tail = NULL;
		}
		else
		{
			QNode* cur = q->head->next;
			free(q->head);
			q->head = cur;
		}
		return data;
	}
}
int QueueSize(Queue* q)
{
	int count = 0;
	QNode* cur = q->head;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}
void QueueDestory(Queue* q)
{
	assert(q);
	if (!QueueEmpty(q))
	{
		QNode* cur = q->head->next;
		QNode* prev = q->head;
		while (prev)
		{
			free(prev);
			prev = cur;
			if (cur)
			{
				cur = cur->next;
			}
		}
	}
}
void QueuePrint(Queue* q)
{
	assert(q);
	QNode* cur = q->head;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
}
int top(Queue* q)
{
	assert(q);
	if (!QueueEmpty(q))
	{
		return q->head->data;
	}
}

        在队列中我们需要注意几点，我们在传参数时传的是一级指针，我们在前面写链表时我们都是传的二级指针，而且我们也是对头指针进行操作，为什么会传一级指针呢？这主要就是我们创建了两个结构体，第一个结构体储存数据，第二个结构体储存头尾指针，我们传的时第二个结构体的地址，传结构体当然是一级指针了为什么在前面我们使用了二级指针呢？这主要是我们返回值是void类型，我们知道函数在进行传参时会将传送的参数拷贝一份，这一份也就是我们在函数中进行操作的数据，我们对指针内容进行修改，如果修改的不是头指针，不会出现任何问题，但是我们一旦修改头指针的位置，那么就会出现错误。

4.练习

4.1编程

1. 括号匹配问题。OJ链接
2. 用队列实现栈。OJ链接
3. 用栈实现队列。OJ链接
4. 设计循环队列。OJ链接

4.2概念

1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出
栈的顺序是（ ）。
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA
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
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。其队内有效长度为？(假设
队头不存放数据)
A (rear - front + N) % N + 1
B (rear - front + N) % N
C ear - front) % (N + 1)
D (rear - front + N) % (N - 1)