栈和队列的基本介绍

本文主要是介绍一下栈和队列，其中包括顺序栈，双栈，链栈，循环队列，链队的结构和相关操作的实现。

顺序栈

1.基本结构：

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef int ElemType;
typedef struct
{
    ElemType data[MAXSIZE];
    int top;
}SqStack;

2.初始化操作：

void InitStack(SqStack *s)
{
    s->top = -1;
}

3.判断栈空，求栈的长度，清空栈：

int EmptyStack(SqStack *s)
{
    if(s->top == -1) {
        return 1;
    }
    return 0;
}

int StackLength(SqStack *s)
{
    return s->top+1;
}

void ClearStack(SqStack *s)
{
    s->top == -1;
}

4.入栈：

void Push(SqStack *s, ElemType e)
{
    if(s->top >= MAXSIZE - 1) {
        return ;
    } else {
        s->top++;
        s->data[s->top] = e;
    }
}

5.出栈：

void Pop(SqStack *s, ElemType *e)
{
    if(s->top == -1) {
        return ;
    } else {
        *e = s->data[s->top--];
    }
}

6.取栈顶：

void GetTop(SqStack *s, ElemType *e)
{
    if(s->top == -1) {
        return;
    } else {
        *e = s->data[s->top];
    }
}

双栈

1.基本结构：

typedef struct
{
    ElemType data[MAXSIZE];
    int top1;
    int top2;
}SqDoubleStack;

2.初始化：

void InitStack(SqDoubleStack *s)
{
    s->top1 = -1;
    s->top2 = MAXSIZE;
}

3.入栈：

void Push(SqDoubleStack *s,ElemType e,int stackNumber)
{
    if(s->top1+1 == s->top2) {
        return ;
    } else {
        if(stackNumber == 1) {
            s->data[++s->top1] = e;
        } else {
            s->data[--s->top2] = e;
        }
    }
}

4.出栈：

void Pop(SqDoubleStack *s, ElemType *e, int stackNumber)
{
    if(stackNumber == 1) {
        if(s->top1 == -1) {
            return ;
        } else {
            *e = s->data[s->top1--];
        }
    } else {
        if(s->top2 == MAXSIZE) {
            return ;
        } else {
            *e = s->data[s->top2++];
        }
    }
}

链栈

1.基本结构：

typedef struct StackNode
{
    ElemType data;
    struct StackNode *next;
}StackNode;

typedef struct
{
    StackNode *top;
    int count;
}LinkStack;

2.初始化操作：

void InitLinkStack(LinkStack *l)
{
    l->count = 0;
    l->top = NULL;
}

3.入栈：

void PushLinkStack(LinkStack *l, ElemType e)
{
    l->count++;
    StackNode *temp = (StackNode*)malloc(sizeof(StackNode));
    temp->data = e;
    temp->next = l->top;
    l->top = temp;
}

4.出栈：

void PopLinkStack(LinkStack *l, ElemType *e)
{
    if(l->top == NULL) {
        return ;
    } else {
        *e = l->top->data;
        StackNode *t;
        t = l->top;
        l->top = l->top->next;
        free(t);
        l->count--;
    }
}

循环队列

1.基本结构

typedef struct
{
    ElemType data[MAXSIZE];
    int front;
    int rear;
}Queue;

2.初始化操作

void InitQueue(Queue *q)
{
    q->front = 0;
    q->rear = 0;
}

3.入队操作

void EnQueue(Queue *q, ElemType e)
{
    if((q->rear+1)%MAXSIZE == q->front) {
        return ;
    } else {
        q->data[q->rear] = e;
        q->rear = (q->rear+1)%MAXSIZE;
    }
}

4.出队操作

void DeQueue(Queue *q, ElemType *e)
{
    if(q->rear == q->front) {
        return ;
    } else {
        *e = q->data[q->front];
        q->front = (q->front+1)%MAXSIZE;
    }
}

5.计算队的长度

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

链队

1.基本结构

typedef struct QNode
{
    ElemType data;
    struct QNode *next;
}QNode;

typedef struct
{
    QNode *front;
    Qnode *rear;
}LinkQueue;

2.初始化操作

void InitLinkQueue(LinkQueue *q)
{
    q->front = (QNode*)malloc(sizeof(QNode));
    q->rear = q->front;
    q->front->next = NULL:
}

3.入队

void EnLinkQueue(LinkQueue *q, ElemType e)
{
    QNode *temp = (QNode*)malloc(sizeof(QNode));
    temp->data = e;
    temp->next = NULL:
    q->rear->next = temp;
    q->rear = temp;
}

4.出队

void DeLinkQueue(LinkQueue *q, ElemType *e)
{
    if(q->front == q->rear){
        return;
    } else {
        QNode *temp = q->front->next;
        *e = temp->data;
        if(temp = q->rear) {
            q->rear = q->front;
            free(temp);
        } else {
            q->front->next = temp->next;
            free(temp);
        }
    }
}

以上就是栈和队列的一些基本操作。
下一次记录实验题目，表达式求值。