数据结构之栈和队列(超详解

一.栈

1.栈的基本概念

2.栈的基本操作

3.栈的储存结构

①栈的顺序储存

(1)基本概念

(2)代码实现

②栈的链式储存

(1)基本概念

(2)代码实现

二.队列

1.队列的基本概念

2.队列的基本操作

3.队列的储存结构

①队列的链式储存

(1)基本概念

编辑 (2)代码实现

②循环队列

(1)基本概念

(2)代码实现

一.栈

1.栈的基本概念

栈是一种常见的数据结构，它是一种“后进先出”（Last In First Out，LIFO）的数据结构，即最后放入栈的元素最先被取出。在计算机中，栈通常由一段连续的内存区域组成，它具有两个基本操作：压栈（Push）和弹栈（Pop）。

压栈将一个元素放入栈顶，弹栈将栈顶元素取出并从栈中删除。

除此之外，栈还具有一个特点：访问栈顶元素的时间复杂度是 O(1)，也就是说，无论栈中有多少元素，访问栈顶元素的时间复杂度都是常数级别的。

2.栈的基本操作

// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

3.栈的储存结构

链式储存的栈相比于顺序储存的栈具有更好的动态性和灵活性，因为链式储存的栈可以动态地扩展或缩小，不需要事先确定储存空间的大小。但是由于链式储存需要使用指针，因此它的空间开销较大，同时由于每个节点都需要动态分配内存，所以它的时间开销也会相对较大。

①栈的顺序储存

(1)基本概念

栈是一种线性数据结构，可以通过数组实现顺序储存。栈的顺序储存特点是使用数组作为底层数据结构，只能从一端插入和删除元素，这一端被称为栈顶。栈的顺序储存还需要记录栈顶指针，用来指向当前栈顶元素的位置。

(2)代码实现

栈的顺序存储结构可描述为：

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top;		// 栈顶
	int _capacity;  // 容量 
}Stack;

基本操作:

#include<stdlib.h>
#include<assert.h>
// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	ps->_a = NULL;
	ps->_capacity = 0;
	//top指向栈顶的下一个元素
	ps->_top = 0;
}
// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->_capacity == ps->_top) {
		ps->_capacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
		STDataType* newnode = (STDataType)realloc(ps->_a,sizeof(STDataType) * ps->_capacity);
		if (newnode==NULL)
		{
			perror("realloc:");
			return;
		}
		ps->_a = newnode;
	}
	ps->_a[ps->_top] = data;
	ps->_top++;
}
// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->_a);
	ps->_top--;
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_a);
	return ps->_a[ps->_top - 1];
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top==0;
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}

代码测试:

#include<stdio.h>
int main()
{
	Stack s;
	StackInit(&s);
	StackPush(&s, 1);
	StackPush(&s, 2);
	StackPush(&s, 3);
	StackPush(&s, 4);
	printf("栈中有%d个数字\n", StackSize(&s));
	
	while (!StackEmpty(&s)) {
		printf("%d\n", StackTop(&s));
		StackPop(&s);
	}
	
	StackDestroy(&s);
	return 0;
}

②栈的链式储存

(1)基本概念

栈的链式储存是将栈中的元素通过链表的方式进行储存。

具体来说，链式储存的栈由两个部分组成：栈顶指针和链表。

其中，栈顶指针指向链表中的第一个元素，每次入栈操作都会将新元素插入到链表头部并更新栈顶指针，而出栈操作则是删除链表头部元素并更新栈顶指针。如果栈为空，则栈顶指针为空指针。

(2)代码实现

栈的链式储存结构可描述为:

/*构造节点*/
typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStackPrt;
/*构造链栈*/
typedef struct LinkStack{
    LinkStackPrt top;
    int count;
}LinkStack;

基本操作:

#include<stdio>
#include<stdlib>
#define OK 1
#define ERROR 0
typedef int SElemType; 
typedef int Status; 

//初始化链栈
Status InitLinkStack(LinkStack **S)
{
	*S = (LinkStack*)malloc(sizeof(LinkStack)); //申请内存空间
	if ((*S) == NULL) //判断申请内存空间是否成功
	{
		printf("申请内存空间失败，初始化失败！\n"); //输出提示语
		return ERROR;
	}
	(*S)->top = NULL; //栈为空时，为NULL,这样最后一个结点的指针域为NULL
	(*S)->count = -1; //链栈为空时，赋值为-1
	printf("初始化成功！\n"); //输出提示语
	return OK;
}

//建立链栈
Status CreateLinkStack(LinkStack *S)
{
	int i = 0;
	SElemType e;
	StackNode *N;
	printf("请输入元素(每个元素之间空格分开，最后一个元素输入后直接换行)：");
	do
	{
		scanf("%d", &e);
		N = (StackNode*)malloc(sizeof(StackNode)); //创建结点申请内存空间
		if (N == NULL) //判断申请内存空间是否成功
		{
			printf("申请内存空间失败，无法继续创建结点！"); //输出提示语
			return ERROR;
		}
		N->data = e; //将e的值赋值给结点N的数据域
		N->next = S->top; //由于链栈的栈顶在链头，所以入栈操作，插入的新结点的指针域要指向原来的栈顶
		S->top = N; //将N结点成为栈顶
		S->count++; //链栈长度加一
	} while(getchar()!='\n'); //判断为换行时 输入结束
	printf("所有元素入栈成功！\n");
	return OK;
}

//压栈(与链表的头插操作相似)
Status Push(LinkStack *S, SElemType e){
    LinkStackPrt p = (LinkStackPrt)malloc(sizeof(StackNode));
    p->data = e;
    p->next = S->top;    //把当前的栈顶元素赋值给新节点的直接后继
    S->top = p; //将新的结点S赋值给栈顶指针
    S->count++;
    return OK;
}

//判断栈是否为空
bool StackEmpty(LinkStack *S)
{
	if (S->count == -1) //判断是否为空栈
	{
		return true;
	}
	return false;
}

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
//弹栈(与链表的头删操作相似)
Status Pop(LinkStack *S, SElemType *e){
    LinkStackPrt p;
    if(StackEmpty(S)){
        return ERROR;
    }
    *e = S->top->data;
    p = S->top; //将栈顶结点赋值给p
    S->top = S->top->next;  //使得栈顶指针下移一位，指向后一结点
    free(p);    //释放结点p
    S->count--;
    return OK;
}

//输出链栈的元素个数
Status LengthLinkStack(LinkStack *S)
{
	if (S->count == -1) //判断链栈是否为空栈
	{
		printf("链栈为空栈，元素个数为零！\n"); 
		return ERROR;
	}
	printf("链栈的元素个数为：%d\n", S->count + 1); 
	return OK;
}

//输出栈顶元素
Status OutTop(LinkStack *S)
{
	if (S->count == -1) //判断链栈是否为空栈
	{
		printf("链栈为空栈，没有栈顶元素！\n"); //输出提示语
		return ERROR;
	}
	printf("链栈的栈顶元素为：%d\n", S->top->data); //输出链栈栈顶元素的值
	return OK;
}
//输出链栈各个元素
Status OutValue(LinkStack *S)
{
	StackNode *N;
	int i = 1;
	if (S->count == -1) //判断是否为空栈
	{
		printf("链栈为空栈，没有元素可输出！\n"); //输出提示语
		return ERROR;
	}
	N = S->top; //将栈顶指针赋值给N
	do
	{
		printf("第%d个元素为：%d\n", i++, N->data);
		N = N->next; //N指向下一个结点
	} while (N != NULL);
	printf("所有元素按照从栈顶到栈底的顺序完毕！\n"); //输出提示语
	return OK;
}
//销毁链栈
Status ClearStack(LinkStack *S)
{
	StackNode *N;
	if (S->count == -1) //判断链栈是否为空栈
	{
		printf("链栈为空栈，不用清空，请勿重复执行此功能！\n");
		return ERROR;
	}
	do
	{
		N = S->top; 
		S->top = N->next; //栈顶指针指向N结点的下一个结点 
		free(N); //释放N所指向的内存空间
	} while (S->top != NULL); //最后一个结点的指针域指向NULL
	free(S->top); //释放最后一个结点
	S->count = -1; //链栈长度置为-1
	printf("链栈清空成功！\n"); //输出提示语
	return OK;
}

代码测试:


int main()
{
	LinkStack *S;
	SElemType e;
	
    InitLinkStack(&S);//初始化链栈
	CreateLinkStack(S); //建立链栈
	LengthLinkStack(S);  //输出链栈的元素个数
	OutTop(S); //输出链栈栈顶元素

	//插入指定元素到栈顶
	printf("要插入的元素的值为：");
	scanf("%d", &e);
	Push(S, e);
	
    //删除栈顶元素
	if (Pop(S, &e))
	{
		printf("删除成功！\n删除的栈顶元素的值为：%d\n", e);
	}
	
    OutValue(S);  //输出链栈各个元素
	ClearStack(S);  //清空链栈
	//链栈是否为空
	if (StackEmpty(S))
	{
		printf("栈为空栈！\n");
	}
	else
	{
		printf("栈不为空！\n");
	}
			
	free(S);//释放S
	return 0;
}

二.队列

1.队列的基本概念

队列是一种常用的数据结构，它具有先进先出（FIFO）的特点。

1. 队头：队列的第一个元素。
2. 队尾：队列的最后一个元素。
3. 入队：将一个元素加入到队列的末尾。
4. 出队：从队列的头部删除一个元素。
5. 队列长度：队列中元素的个数。

2.队列的基本操作

队列通常包含两个基本操作：入队和出队。入队将元素加入到队列的末尾，而出队则从队列的头部删除元素。除此之外，队列还包括判空和判满等操作。


// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

3.队列的储存结构

①队列的链式储存

(1)基本概念

链队列:采用链式存储结构实现的队列。通常链队列用单链表来表示。一个链队列显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。这里和线性表的单链表一样，为了操作方便起见，给链队列添加一个头结点，并令头指针始终指向头结点。

(2)代码实现

存储结构:

// 链式结构：表示队列 
typedef struct QListNode
{
	QDataType _data;
	struct QListNode* _next;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
	int size;
}Queue;

基本操作:

#include<assert.h>
#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
// 初始化队列 
void QueueInit(Queue* q)
{
	q->_front = NULL;
	q->_rear = NULL;
	q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc:");
		return;
	}
	newnode->_data = data;
	newnode->_next = NULL;
	if (q->_front == NULL)
	{
		q->_front = q->_rear = newnode;
	}
	else
	{
		q->_rear->_next = newnode;
		q->_rear = newnode;
	}
	q->size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{
	if (!QueueEmpty(q))
	{
		q->_front = q->_front->_next;
	}
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q && q->_front);
	return q->_front->_data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q && q->_rear);
	return q->_rear->_data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
	if (q->size==0)
	{
		return true;
	}
	return false;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	while (q->_front)
	{
		QNode* p = q->_front;
		q->_front = q->_front->_next;
		free(p);
		p = NULL;
	}
	q->_front = q->_rear = NULL;
}

代码测试:

int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	printf("有%d个元素\n", QueueSize(&q));

	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
    QueueDestroy(&q);
	return 0;
}

②循环队列

(1)基本概念

循环队列:是将数组的首尾相连，组成的一个特殊结构。头、尾指针以及队列元素之间的关系不变，只是在循环队列中，头、尾指针“依环状增1"的操作可用“模”运算来实现。通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式“循环”移动。

(2)代码实现

储存结构:

typedef struct {
    int* st;
    int length, top, tail;
} MyCircularQueue;

基本操作:


#include <stdio.h>
#include <stdlib.h>
 
#define OK 1
#define ERROR 0
#define OVERFLOW -1
 
#define MAXSIZE 7
                        
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
//循环队列的创建
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*) malloc(sizeof(MyCircularQueue));
    obj->st = (int*) malloc(sizeof(int) * k);
    obj->top = 0;
	obj->tail = 0;
    obj->length = k;
    return obj;
}
//循环队列入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) return false;
    obj->st[obj->top] = value;
    obj->top = (obj->top + 1) % obj->length;
    return true;
}
//循环队列出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) return false;
    obj->tail = (obj->tail + 1) % obj->length;
    return true;
}
//求队头元素
int myCircularQueueFront(MyCircularQueue* obj) {
    return myCircularQueueIsEmpty(obj) ? -1 : obj->st[obj->tail];
}
//求队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    return myCircularQueueIsEmpty(obj) ? -1 : obj->st[(obj->top + obj->length - 1) % obj->length];
}
//循环队列的判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->top == obj->tail;
}
//循环队列的判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->top + 1) % obj->length == obj->tail;
}
//销毁
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->st);
    free(obj);
}

代码测试:


int main() {
    MyCircularQueue *sq;
 
    //循环队列的创建 
	sq=myCircularQueueCreate(MAXSIZE);
	//入队 
    myCircularQueueEnQueue(sq, 1);
    myCircularQueueEnQueue(sq, 2);
    myCircularQueueEnQueue(sq, 3);
    myCircularQueueEnQueue(sq, 4);
    int rEnQueue = myCircularQueueEnQueue(sq, 5);
    if (rEnQueue == OK) {
        printf("向循环队列入队成功！\n");
    } else {
        printf("向循环队列入队失败！\n");
    }

    //输出链表元素
    DisplayQueue(sq);
    printf("\n");
    //出队 
    int rDeQueue = myCircularQueueDeQueue(sq);
    if (rDeQueue == OK) {
        printf("向循环队列出队成功！\n");
    } 
    else {
       printf("向循环队列出队失败！\n");
    }
    
    //输出链表元素
    DisplayQueue(sq);
    printf("\n");
    
    //求队头元素
    int topData = myCircularQueueFront(sq);
    printf("向循环队列获取队头元素：%d\n", topData);
    //求队尾元素
    int tailData = myCircularQueueRear(sq);
    printf("向循环队列获取队头元素：%d\n", tailData);
    //判空
    bool ClearStatus = myCircularQueueIsEmpty(sq);
    if (ClearStatus == true) {
            printf("循环队列为空！\n\n");
    }
    else {
           printf("循环队列不为空！\n\n");
    }
    
    //销毁 
    myCircularQueueFree(sq);
    return 1;
}