栈

定义

堆栈（Stack）：

具有一定操作约束的线性表，只在一端（栈顶，Top）做插入、删除

特点：后入先出

栈的操作：

1、Stack CreateStack( int MaxSize )： 生成空堆栈，其最大长度为MaxSize；

2、int IsFull( Stack S, int MaxSize )：判断堆栈S是否已满；

3、void Push( Stack S, ElementType item )：将元素item压入堆栈；

4、int IsEmpty ( Stack S )：判断堆栈S是否为空；

5、ElementType Pop( Stack S )：删除并返回栈顶元素；

栈的顺序存储实现

1
2
3
4
5
6
#define MaxSize /*储存数据元素的最大个数*/
typedef struct SNode *Stack;
struct SNode{
	ElementType Data[MaxSize];
	int Top;
};

入栈

1
2
3
4
5
6
7
8
9
void Push( Stack PtrS, ElementType item )
{
 	if ( PtrS->Top == MaxSize-1 ) {
 	printf(“堆栈满”); return;
    } else {
 	PtrS->Data[++(PtrS->Top)] = item;
 	return;
 }
}

出栈

1
2
3
4
5
6
7
8
ElementType Pop( Stack PtrS )
{
 	if ( PtrS->Top == -1 ) {
 	printf(“堆栈空”);
 	return ERROR; /* ERROR是ElementType的特殊值，标志错误*/
 	} else 
 	return ( PtrS->Data[(PtrS->Top)--] );
}

堆栈的链式存储实现

1
2
3
4
5
typedef struct SNode *Stack;
struct SNode{
	ElementType Data;
	struct SNode *Next;
} ;

建栈

1
2
3
4
5
6
7
8
9
10
11
Stack CreateStack() 
{ /* 构建一个堆栈的头结点，返回指针 */
 	Stack S;
 	S =(Stack)malloc(sizeof(struct SNode));
 	S->Next = NULL;
 	return S;
}
int IsEmpty(Stack S) 
{ /*判断堆栈S是否为空，若为空函数返回整数1，否则返回0 */
	return ( S->Next == NULL );
}

入栈

1
2
3
4
5
6
7
8
void Push( ElementType item, Stack S) 
{ /* 将元素item压入堆栈S */
	struct SNode *TmpCell;
	TmpCell=(struct SNode *)malloc(sizeof(struct SNode));
	TmpCell->Element = item;
	TmpCell->Next = S->Next;
	S->Next = TmpCell;
}

出栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ElementType Pop(Stack S)
{ /* 删除并返回堆栈S的栈顶元素 */
	struct SNode *FirstCell;
	ElementType TopElem;
	if( IsEmpty( S ) ) {
	printf(“堆栈空”); return NULL;
	} else {
	FirstCell = S->Next; 
    S->Next = FirstCell->Next;
	TopElem = FirstCell ->Element;
	free(FirstCell);
	return TopElem;
  }
}

队列

定义

队列(Queue)：具有一定操作约束的线性表，只能在一端插入，而在另一端删除

特点：先进先出

队列的操作：

1、Queue CreatQueue( int MaxSize )：生成长度为MaxSize的空队列；

2、int IsFullQ( Queue Q, int MaxSize )：判断队列Q是否已满；

3、void AddQ( Queue Q, ElementType item )： 将数据元素item插入队列Q中；

4、int IsEmptyQ( Queue Q )： 判断队列Q是否为空；

5、ElementType DeleteQ( Queue Q )：将队头数据元素从队列中删除并返回。

队列的顺序存储实现

1
2
3
4
5
6
7
#define MaxSize /*储存数据元素的最大个数*/
struct QNode {
	ElementType Data[ MaxSize ];
	int rear;
	int front;
}; 
typedef struct QNode *Queue;

入队列

1
2
3
4
5
6
7
8
9
void AddQ( Queue PtrQ, ElementType item)
{ 
 	if ( (PtrQ->rear+1) % MaxSize == PtrQ->front ) {
 	printf(“队列满”); 
 	return;
 }
 	PtrQ->rear = (PtrQ->rear+1)% MaxSize;
 	PtrQ->Data[PtrQ->rear] = item;
}

出队列

1
2
3
4
5
6
7
8
9
10
ElementType DeleteQ ( Queue PtrQ )
{ 
 	if ( PtrQ->front == PtrQ->rear ) { 
 	printf(“队列空”);
 	return ERROR;
 	} else {
 	PtrQ->front = (PtrQ->front+1)% MaxSize;
 	return PtrQ->Data[PtrQ->front];
 }
}

队列的链式存储实现

1
2
3
4
5
6
7
8
9
10
struct Node{
 	ElementType Data;
 	struct Node *Next;
}; 
struct QNode{ /* 链队列结构 */
 	struct Node *rear; /* 指向队尾结点 */
 	struct Node *front; /* 指向队头结点 */
}; 
typedef struct QNode *Queue;
Queue PtrQ;

出队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ElementType DeleteQ ( Queue PtrQ )
{	struct Node *FrontCell; 
 	ElementType FrontElem;
 	if ( PtrQ->front == NULL) {
 	printf(“队列空”); return ERROR;
 } 
 	FrontCell = PtrQ->front;
 	if ( PtrQ->front == PtrQ->rear) /* 若队列只有一个元素 */
 	PtrQ->front = PtrQ->rear = NULL; /* 删除后队列置为空 */
 	else 
 	PtrQ->front = PtrQ->front->Next;
 	FrontElem = FrontCell->Data;
 	free( FrontCell ); /* 释放被删除结点空间 */
 	return FrontElem;
}