【数据结构】栈和队列

博主：本当迷
发布时间：2021 年 09 月 28 日
979 次浏览
暂无评论
5117字数
分类：数据结构

## 栈

### 栈的定义：

栈：限定仅在表尾进行插入和删除操作的线性表（先进后出）

* 栈的插入操作叫：进栈（push）
* 栈的删除操作叫：出栈（pop）

### 栈的抽象数据类型：

```
ADT栈（srack）
Data
	同线性表。元素具有相同的类型，相邻元素具有前驱和后继
Operation
	InitStack(*S);//初始化操作，建立一个空栈S
	DestroyStack(*S);//若栈存在，则销毁它
	ClearStack(*S);//将栈清空
	StackEmpty(S);//若栈为空，返回true,否则返回false
	GetTop(S, *e);//若栈存在且非空，用e返回S栈顶元素
	Push(*S, e);//若栈S存在，插入新元素e到栈S中成为栈顶元素
	pop(*S，*e);//删除栈S中的栈顶元素，并且用e返回其值
	StackLength(S);//返回栈S的元素个数
endADT
```

### 栈的顺序存储结构

#### 代码示例：

```cpp
#include<stdio.h>
#include<stdlib.h>

#define ERROR  0
#define OK 1
#define MAXSIZE 20

typedef int SElemType;
typedef int Statue;

typedef struct
{
	SElemType date[MAXSIZE];
	int top;	//用于栈顶指针
}SqStack;

Statue Push(SqStack* S, SElemType e)//进栈
{
	if (S->top == MAXSIZE)
	{
		return ERROR;
	}
	S->date[S->top++] = e;
	return OK;

}

Statue Pop(SqStack* S, SElemType* e)
{
	if (S->top == 0)
	{
		return ERROR;
	}
	*e = S->date[S->top--];
	return OK;
}
Statue Gettop(SqStack* S)//返回栈顶元素
{
	if (S->top == 0)
		return -1;
	int e = S->top;
	return e;
}

int main()
{
	SqStack *L;
	L = (SqStack*)(malloc(sizeof(SqStack)));
	L->top = 0;

for (int i = 1; i < 10; i++)//进栈
	{
		Push(L, i);
	}
	printf("栈顶元素为：%d\n", Gettop(L));

int n;
	Pop(L, &n);//出栈

printf("栈顶元素为：%d\n", Gettop(L));
	return 0;
}

```

### 栈的链式存储结构

#### 代码示例：

```cpp
#include<stdio.h>
#include<stdlib.h>

#define ERROR  0
#define OK 1
#define MAXSIZE 20

typedef int SElemType;
typedef int Statue;

typedef struct StackNode
{
	SElemType data;
	struct StackNode* next;
}LinkStackPtr;

typedef struct
{
	LinkStackPtr *top;
	int count;	//用于栈顶指针
}SqStack;

Statue Push(SqStack* S, SElemType e)
{
	LinkStackPtr* s = (LinkStackPtr*)(malloc(sizeof(LinkStackPtr)));
	s->data = e;
	s->next = S->top;
	S->top = s;
	S->count++;
	return OK;
}

Statue Pop(SqStack* S, SElemType *e)
{
	if (S->top == 0)
	{
		return ERROR;
	}
	*e = S->top->data;
	S->top = S->top->next;
	S->count--;
	return OK;
}

int Gettop(SqStack* S)
{
	return S->top->data;
}

int main()
{
	SqStack* L;
	L = (SqStack*)(malloc(sizeof(SqStack)));
	L->count = 0;
	for (int i = 1; i < 10; i++)//进栈
	{
		Push(L, i);
	}

printf("栈顶元素为：%d\n", Gettop(L));

int e;
	Pop(L, &e);//出栈

printf("栈顶元素为：%d\n", Gettop(L));
	return 0;
}

```

## 队列

### 定义：

只允许在一段进行插入操作，而另一端进行删除操作的线性表！（先进先出）

* 队头：允许删除的那一端
* 队尾：允许插入的那一端

### 队列的抽象数据类型

```
ADT 队列（Queue）
Data
	同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系
Operation
	Initlist（*Q）;//初始化操作，建立一个空队列Q
	DestoyQueue（*Q）;//若队列Q存在，则销毁它
	ClearQueue（*Q）;//将队列清空
	QueueEmpty（Q）;//若队列为空，返回true ,否则返回false
	GetHead（Q,*e）;//若队列存在非空，用e返回队列Q的队头元素
	EnQueue（*Q,e）;//若队列Q存在，插入新元素e到队列Q中成为队尾元素
	DeQueue（*Q，*e）;//删除队列Q中队头元素，并用e返回其值
EndADT
```

### 循环队列的顺序存储：

#### 定义：

我们把队列的头尾相连的顺序存储结构称为循环队列

### 队列满的条件：

（rear + 1） % QueueSize == front

### 计算队列长度公式：

（rear - front + QueueSize）%QueueSize

### 代码示例：

```cpp
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
#define OK 1
#define ERROR 0

typedef int QElemType;
typedef int Status;

typedef struct
{
	QElemType data[MAXSIZE];
	int front;
	int rear;
}sqQueue;

Status InitQueue(sqQueue* Q)//初始化队列
{
	Q->front = 0;
	Q->rear = 0;
	return OK;
}

int QueueLength(sqQueue *Q)
{
	return(Q->rear - Q->front + MAXSIZE) % MAXSIZE;
}

Status EnQueue(sqQueue* Q, QElemType e)//入队插入操作
{
	if ((Q->rear + 1) % MAXSIZE == Q->front)
	{
		return ERROR;
	}
	Q->data[Q->rear] = e;
	Q->rear = (Q->rear + 1) % MAXSIZE;
	return OK;
}

Status DeQueue(sqQueue* Q, QElemType* e)//出队删除操作
{
	if (Q->front == Q->rear)
	{
		return ERROR;
	}

*e = Q->data[Q->front];
	Q->front = (Q->front + 1) % MAXSIZE;
	return OK;
}

void print_queue(sqQueue* L)
{
	sqQueue* p = L;
	int i = 0;
	while (p->front + i != L->rear)
	{
		printf("%d ", p->data[p->front + i]);
		i++;
	}
	printf("\n");
}
int main()
{
	sqQueue* que;
	que = (sqQueue*)(malloc(sizeof(sqQueue)));
	InitQueue(que);
	for (int i = 1; i < 5; i++)
	{
		EnQueue(que, i);
	}

int e;
	DeQueue(que, &e);
	printf("删除元素为：%d\n", e);
	print_queue(que);
	return 0;
}
```

### 队列的链式存储：

#### 链式存储结构为：

```cpp
typedef int QElemType;

typedef struct QNode//结点结构
{
	QElemType data;
	struct QNode *Next;

}QNode, *QueuePtr;

typedef struct//队列的链表结构
{
	QueuePtr front, rear;//队头，队尾指针

}LinkQueue;

```

#### 入队操作：

```cpp
Status EnQueue(LinkQueue *Q, QElemType e)
{
	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
	if(!s)
		exit(OVERFLOW);//存储分配失败
	s->data = e;
	s->next = NULL;
	Q->rear->next = s;//把拥有元素e的新节点s赋值给原队尾结点的后继
	Q->rear = s;//把当前的s设置成队尾结点，rear指向s
	return OK;
}
```

#### 出队操作：

```cpp
Status DeQueue(LinkQueue *Q, QElemType *e)
{
	QueuePtr p;
	if(Q->front == Q->rear)
		return ERROR;
	p = Q->front->next;//将欲删除的队头结点暂存给p
	*e = p->data;//将将欲删除的队头结点的值赋给e
	Q->front->next = p->next;//将原队头结点的后继p->next赋值给头结点后继
	if(Q->rear == p)//若队头就是队尾，则删除后将rear指向头结点
		Q->rear = Q->front;
	free(p);
	return OK;
}
```

队列的链式存储我就不实现了，知道基本原理就行！

#### 原理：

入队：从队尾入队

出队：从队头出队

最后修改：2021 年 09 月 28 日

如果文章有用，请随意打赏。

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

【数据结构】栈和队列

本当迷 • 2021 年 09 月 28 日

## 栈

### 栈的定义：

栈：限定仅在表尾进行插入和删除操作的线性表（先进后出）

* 栈的插入操作叫：进栈（push）
* 栈的删除操作叫：出栈（pop）

### 栈的抽象数据类型：

### 栈的顺序存储结构

#### 代码示例：

```cpp
#include<stdio.h>
#include<stdlib.h>

#define ERROR  0
#define OK 1
#define MAXSIZE 20

typedef int SElemType;
typedef int Statue;

typedef struct
{
	SElemType date[MAXSIZE];
	int top;	//用于栈顶指针
}SqStack;

Statue Push(SqStack* S, SElemType e)//进栈
{
	if (S->top == MAXSIZE)
	{
		return ERROR;
	}
	S->date[S->top++] = e;
	return OK;

}

int main()
{
	SqStack *L;
	L = (SqStack*)(malloc(sizeof(SqStack)));
	L->top = 0;

for (int i = 1; i < 10; i++)//进栈
	{
		Push(L, i);
	}
	printf("栈顶元素为：%d\n", Gettop(L));

int n;
	Pop(L, &n);//出栈

printf("栈顶元素为：%d\n", Gettop(L));
	return 0;
}

```

### 栈的链式存储结构

#### 代码示例：

```cpp
#include<stdio.h>
#include<stdlib.h>

#define ERROR  0
#define OK 1
#define MAXSIZE 20

typedef int SElemType;
typedef int Statue;

typedef struct StackNode
{
	SElemType data;
	struct StackNode* next;
}LinkStackPtr;

typedef struct
{
	LinkStackPtr *top;
	int count;	//用于栈顶指针
}SqStack;

Statue Push(SqStack* S, SElemType e)
{
	LinkStackPtr* s = (LinkStackPtr*)(malloc(sizeof(LinkStackPtr)));
	s->data = e;
	s->next = S->top;
	S->top = s;
	S->count++;
	return OK;
}

Statue Pop(SqStack* S, SElemType *e)
{
	if (S->top == 0)
	{
		return ERROR;
	}
	*e = S->top->data;
	S->top = S->top->next;
	S->count--;
	return OK;
}

int Gettop(SqStack* S)
{
	return S->top->data;
}

int main()
{
	SqStack* L;
	L = (SqStack*)(malloc(sizeof(SqStack)));
	L->count = 0;
	for (int i = 1; i < 10; i++)//进栈
	{
		Push(L, i);
	}

printf("栈顶元素为：%d\n", Gettop(L));

int e;
	Pop(L, &e);//出栈

printf("栈顶元素为：%d\n", Gettop(L));
	return 0;
}

```

## 队列

### 定义：

只允许在一段进行插入操作，而另一端进行删除操作的线性表！（先进先出）

* 队头：允许删除的那一端
* 队尾：允许插入的那一端

### 队列的抽象数据类型

### 循环队列的顺序存储：

#### 定义：

我们把队列的头尾相连的顺序存储结构称为循环队列

### 队列满的条件：

（rear + 1） % QueueSize == front

### 计算队列长度公式：

（rear - front + QueueSize）%QueueSize

### 代码示例：

```cpp
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
#define OK 1
#define ERROR 0

typedef int QElemType;
typedef int Status;

typedef struct
{
	QElemType data[MAXSIZE];
	int front;
	int rear;
}sqQueue;

Status InitQueue(sqQueue* Q)//初始化队列
{
	Q->front = 0;
	Q->rear = 0;
	return OK;
}

int QueueLength(sqQueue *Q)
{
	return(Q->rear - Q->front + MAXSIZE) % MAXSIZE;
}

Status EnQueue(sqQueue* Q, QElemType e)//入队插入操作
{
	if ((Q->rear + 1) % MAXSIZE == Q->front)
	{
		return ERROR;
	}
	Q->data[Q->rear] = e;
	Q->rear = (Q->rear + 1) % MAXSIZE;
	return OK;
}

Status DeQueue(sqQueue* Q, QElemType* e)//出队删除操作
{
	if (Q->front == Q->rear)
	{
		return ERROR;
	}

*e = Q->data[Q->front];
	Q->front = (Q->front + 1) % MAXSIZE;
	return OK;
}

int e;
	DeQueue(que, &e);
	printf("删除元素为：%d\n", e);
	print_queue(que);
	return 0;
}
```

### 队列的链式存储：

#### 链式存储结构为：

```cpp
typedef int QElemType;

typedef struct QNode//结点结构
{
	QElemType data;
	struct QNode *Next;

}QNode, *QueuePtr;

typedef struct//队列的链表结构
{
	QueuePtr front, rear;//队头，队尾指针

}LinkQueue;

```

#### 入队操作：

#### 出队操作：

队列的链式存储我就不实现了，知道基本原理就行！

#### 原理：

入队：从队尾入队

出队：从队头出队

【数据结构】栈和队列

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【修仙之路】JAVA学习路线

对于异或运算的初步认识与auto用法

【JAVA经典例题】生产者/消费者问题

最近某音挺火的代码实现爱心形状

再见Swagger！拥抱smart-doc无侵入生成接口文档

C语言-文件使用方式与打开关闭文件操作

阿里云maven2022最新仓库

【css】盒子模型入门

C语言-二维数组求平均成绩

【java】通过反射创建Class实例的4种方式

【数据结构】栈和队列

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【数据结构】栈和队列

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款