栈和队列

ゝ一纸荒年。 2023-07-01 12:56 101阅读 0赞

栈是限定在表尾进行插入或删除的线性表.因此,对于栈来说,表尾端有其特殊的含义,称为`栈顶`,相应地,表头端称为`栈底`.不含任何元素的栈称为空栈.

和线性表类似,栈也有两种存储方法.

顺序栈,即栈的存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素.同时附设指针top指示栈顶元素在顺序栈中的位置.

`非空栈中的栈顶指针始终在栈顶元素的下一个位置上`.

#include<stdio.h>
    #include<stdlib.h>
    
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    #define INIT_SIZE 20
    #define INCREMENT_SIZE 5
    
    typedef int SElemType;
    typedef int Status;
    
    /* 存储结构 */
    
    typedef struct { 
    	SElemType *base;	// 栈尾指针
    	SElemType *top;		// 栈顶指针
    	int size;			// 栈的大小
    } SqStack;
    
    /* 初始化栈 */
    Status InitStack(SqStack *S)
    { 
    	S->base = (SElemType *)malloc(INIT_SIZE * sizeof(SElemType));
    	if (!S->base)
    	{ 
    		exit(OVERFLOW);
    	}
    	S->top = S->base;
    	S->size = INIT_SIZE;
    	return OK;
    }
    
    /* 销毁栈 */
    
    Status DestoryStack(SqStack *S)
    { 
    	free(S->base);
    	S->base = NULL;
    	S->top = NULL;
    	S->size = 0;
    	return OK;
    }
    
    /* 清空栈 */
    
    Status ClearStack(SqStack *S)
    { 
    	S->top = S->base;
    	return OK;
    }
    
    /* 判断栈是否为空 */
    Status IsEmpty(SqStack S)
    { 
    	if (S.top == S.base)
    	{ 
    		return TRUE;
    	}
    	return FALSE;
    }
    
    /* 获取栈的长度 */
    
    int GetLength(SqStack S)
    { 
    	return S.top - S.base;
    }
    
    /* 获取栈顶元素 */
    
    Status GetTop(SqStack S, SElemType *e)
    { 
    	if (S.top > S.base)
    	{ 
    		*e = *(--S.top);
    		return OK;
    	}
    	return ERROR;
    }
    
    /* 压栈 */
    
    Status Push(SqStack *S, SElemType e)
    { 
    	if ((S->top - S->base) / sizeof(SElemType) >= S->size)
    	{ 
    		S->base = (SElemType *)realloc(S->base, (S->size + INCREMENT_SIZE) * sizeof(SElemType));
    		if (!S->base)
    		{ 
    			exit(OVERFLOW);
    		}
    		S->top = S->base + S->size;
    		S->size += INCREMENT_SIZE;
    	}
    	*S->top = e;
    	++S->top;
    	return OK;
    }
    
    /* 弹栈 */
    Status Pop(SqStack *S, SElemType *e)
    { 
    	if (S->top == S->base)
    	{ 
    		return ERROR;
    	}
    	S->top--;
    	*e = *S->top;
    	return OK;
    }
    
    /* 访问元素 */
    
    void visit(SElemType e)
    { 
    	printf("%d ", e);
    }
    
    /* 遍历栈 */
    
    Status TraverseStack(SqStack S, void (*visit)(SElemType))
    { 
    	while (S.top > S.base)
    	{ 
    		visit(*S.base);
    		S.base++;
    	}
    
    	return OK;
    }

和栈相反,队列是一种`先进先出`的线性表.它只允许在表的一段进行插入,而在另一端删除元素.在队列中,允许插入的一端叫做`队尾`.  
  除了栈和队列之外,还有一种限定数据结构是`双端队列`(deque).

双端队列是限定插入和删除在表的两端.

和线性表类似,队列也有两种存储表示.  
  用链表表示的队列简称为链队列.一个链队列需要两个分别指示队头和队尾的指针才能唯一确定.链队列的操作即为单链表的插入和删除操作的特殊情况,只是尚需修改头指针和尾指针.

typedef struct QNode { 
        int data;
        struct QNode *next;
    } QNode, * QueuePtr;
    
    typedef struct { 
        QueuePtr front;     // 队头指针
        QueuePtr rear;      // 队尾指针
    } LinkQueue;

和顺序栈相类似,在队列的顺序存储结构中,除了一组地址连续的存储单元以此存放从队列头到队列尾的元素之外,需要设两个指针front和rear分别指示队列头元素及队列尾元素的位置.  
  初始化建空队列时,令front=rear=0,每当插入新的队列尾元素时候,尾指针加1,每当删除队列头元素时,头指针减1.因此,在非空队列中,头指针始终指向队列头元素,而尾指针始终指向队列尾元素的下一个位置.

#### 循环队列 ####

#define MAXSIZE 100; // 最大队列长度
    typedef struct { 
        int * base;             // 初始化动态分配存储空间基址
        int front;              // 头指针,若队列不空,则指向队列头元素
        int rear;               // 尾指针,若队列不空,窒息那该队列尾元素的下一个位置
    } SqQueue;