数据结构第二部分——栈和队列(C语言版)

数据结构第二部分——栈和队列(C语言版)

1、基本概念

• 栈：只能在一端进行插入或删除的线性表，这一端称为栈顶，另一端称为栈底。栈的特点是 先进后出（FILO），就像一个车队开进了一个死胡同，最先开进的车只有等后边的车全部出去，它才能出去。

• 队列：它是一种操作受限的线性表，限制为仅允许在一端插入，另一端删除，插入的一端称为队尾，删除的一端称为队头。他的特点为 先进先出（FIFO）。

2、存储结构

• 顺序栈定义

typedef struct
{
	int data[maxSize];
	int top;
}SqStack;
1
2
3
4
5

• 链栈结点定义

typedef struct LNode
{
	int data;//数据域
	struct LNode *next;//指针域
}LNode;
1
2
3
4
5

• 顺序队列定义

typedef struct
{
	int data[maxSize];
	int front;
	int rear;
}SqQueue;
1
2
3
4
5
6

• 链队定义

//队结点类型
typedef struct QNode
{
	int data;
	struct QNode *next;
}QNode;
//链队类型
typedef struct
{
	QNode *front;
	QNode *rear;
}LiQueue;
1
2
3
4
5
6
7
8
9
10
11
12

3、顺序栈操作

//初始化栈
void initStack(SqStack &st)
{
	st.top = -1;
}
//判断栈空
int isEmpty(SqStack st)
{
	if(st.top == -1)
		return 1;
	else
		return 0;
}
//进栈
int push(SqStack &st,int x)
{
	if(st.top == maxSize-1)//栈满了，不能进栈
		return 0;
	++(st.top);
	st.data[st.top] = x;
	return 1;
}
//出栈
int pop(SqStack &st,int &x)
{
	if(st.top == -1)//栈空不能出栈
		return 0;
	x = st.data[st.top];
	--(st.top);
	return 1;
}

//实际使用时的简单写法
int stack[maxSize];
int top = -1;
stack[++top] = x;
x = stack[top--];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

4、链栈操作

//初始化
void initStack(LNode *&lst)
{
	lst = (LNode*)malloc(sizeof(LNode));//制造一个头结点
	lst->next = NULL;
}
//判断栈空
int isEmpty(LNode *lst)
{
	if(lst -> next == NULL)
		return 1;
	else
		return 0;
}
//进栈
void push(LNode *lst,int x)
{
	LNode *p;
	p = (LNode*)malloc(sizeof(LNode));
	p -> next = NULL;

	p->data=x;
	p->next = lst->next;
	lst->next=p;
}
//出栈
int pop(LNode *lst,int &x)
{
	LNode *p;
	if(lst->next == NULL)
		return 0;
	
	p=lst->next;
	x=p->data;
	lst->next=p->next;
	free(p);
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

5、循环队列

• 在顺序队中,通常让队尾指针rear指向刚进队的元素位置，让队首指针font指向刚出队的元素位置。因此,元素进队的时候，rear要向后移动；元素出队的时候，front也要向后移动。经过一系列的出队和进队操作以后，两个指针最终会达到数组末端maxSize-1处。虽然队中已经没有元素,但仍然无法让元素进队,这就是所谓的“假溢出”。
• 要解决这个问题，可以把数组弄成一个环，让rear和front沿着环走，这样就永远不会出现两者来到数组尽头无法继续往下走的情况，这样就产生了循环队列。
  
  一般情况下，front=(front+1)%maxSize，可以看出，循环队列必须损失一个存储空间，如果下图中的空白处也存入元素，则队满的条件也成了 front==rear，和队空条件相同了。
  

//初始化队列
void initQueue(SqQueue &qu)
{
	qu.front = qu.rear = 0;
}
//判断队空
int isQueueEmpty(SqQueue qu)
{
	if(qu.front == qu.rear)
		return 1;
	else
		return 0;
}
//进队
int enQueue(SqQueue &qu,int x)
{
	if((qu.rear+1)%maxSize == qu.front)
		return 0;
	qu.rear = (qu.rear+1)%maxSize;
	qu.data[qu.rear] = x;
	return 1;
}
//出队
int deQueue(SqQueue &qu,int &x)
{
	if(qu.front == qu.rear)
		return 0;
	qu.front = (qu.front+1) % maxSize;
	x = qu.data[qu.front];
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

6、链队

• 链队就是采用链式存储结构存储队列，链队的特点是不存在队满，除非内存满了。
• 链队队空状态：lqu->rear == NULL 或者 lqu->front == NULL.
• 入队操作：lqu->rear->next = p；lqu->rear = p；
• 出队操作：p=lqu->front；lqu->front = p->next；x = p->data；free§；
  

7、共享栈和双端队列

• 共享栈：相比于普通的顺序栈，共享栈主要是为了提高内存的利用率和减少溢出的可能性而设计
• 双端队列：是一种插入和删除操作在两端均可进行的线性表。
• 可以把双端队列看成栈底连在一起的两个栈。双端队列与共享栈的不同之处是，两个栈的栈顶指针是向两端延伸的。由于双端队列允许在两端插入和删除元素，因此需设立两个指针：end1和end2，分别指向双端队列中两端的元素。