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

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

Stack.h


#pragma once
#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 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;
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return 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 : 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];
}
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

栈的初始化：


void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 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 : 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;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL && pq->tail == NULL;
}
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;
    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);
	}
	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;
}
int QueueSize(Queue* pq)
{
	assert(pq);
	/*QNode* cur = pq->head;
	int n = 0;
	while (cur)
	{
		n++;
		cur = cur->next;
	}
	return n;*/
	return pq->size;
}

队列的初始化：


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;
    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);
	}
	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.括号匹配问题


//有效的括号
//将上面的栈拷贝下来
//将栈typedef的数据类型改为char
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.设计循环队列


//设计循环队列
//数组实现：
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++;
	//控制如果到空间尾以后 front回到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 
		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
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，队尾指针为back；循环队列长度为N。其队内有效长度为？(假设多给一个空间，实际空间大小为N)
A (back - front + N) % N + 1
B (back - front + N) % N
C (back - front) % (N + 1)
D (back - 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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/码创造者/article/detail/975668