数据结构--栈和队列

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
39
40
41
42
43
44
45
46
47
// 顺序栈
typedef struct
{
    int data[maxSize]
    int top;
}SqStack;

// 链栈
typedef struct LNode
{
    int data;
    struct LNode *Next;
}LNode;

// 顺序队列
typedef struct
{
    int data[maxSize];
    int front;
    int rear;
}SqQueue;

// 链队列
typdef struct QNode
{
    int data;
    struct QNode *next;
}QNode

typedef struct
{
    QNode *front;
    QNode *rear;
    
}LiQueue;

/*  栈插入和删除的常用操作
------------------------
int Stack[maxSize];int top =-1;
Stack[++p]= x;
x= Stack[p--];

BTNode *Stack[maxSize] ;int top =-1; 
Stack[++p]= x;
x= Stack[p--];
------------------------
*/

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

// 初始化
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;
}

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
39
40
41
42
43
44
45
46

// 栈空
lst-> next == NULL
// 进栈 //头插入
p->next =lst->next;lst->next =P;
// 出栈
q=lst->next;x=q->data; lst->next = q->next; free(q);

// 初始化
void initStack(LNode *&lst)
{
    lst =(LNode*)malloc(sizeof(LNode))
    lst-> next = NULL;
}

// 判断栈空
init 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->data = x;
    p->next = NULL;
    p->next = lst->next;
    lst->next = p;
}
//出栈
int pop(LNode *lst,int &x)
{
    LNode *q;
    if(lst->next == NULL)
        return 0;
    q = lst->next;
    x = q->data;
    lst->next = q->next;
    free(q);
    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
39
40
41
42
43
44
45
46
/* 顺序队列的常用操作
------------------------
int front,rear;
BTNode *que[maxSize];
front = rear =0
------------------------
*/
;
// 队空：qu.rear =qu.front
// 队满：(qu.rear+1)%maxSize ==qu.front
// 进队：qu.rear  = (qu.rear+1 )%maxSize; qu.data[qu.rear]  = x;
// 出队：qu.front = (qu.front+1)%maxSize; qu.data[qu.front] = x;

// 初始化
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 1;
    qu.rear = (qu.rear+1)%maxSize;
    qu.data[qu.rear] = x;
    return 1;
}

//出队
int deQueue(Squeue &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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// 空队：lqu->rear == NULL;或者lqu->front ==NULL;
// 不存在堆满
// 进队：lqu->rear->next = p; lqu->rear=p;
// 出队：p=lqu->front;lqu->front = p->next;x=p->data;free(p);

// 初始化
void initQueue(LiQueue *&lqu)
{
    lqu =(LiQueue*)malloc(sizeof(LiQueue));
    lqu->front = lqu->rear = NULL;
}
// 判断队空
int  isQueueEmpty(LiQueue *lqu)
{
    if(lqu->rear==NULL||lqu->front==NULL)
        return 1;
    else
        return 0;
}

// 入队
void enQueue(LiQueue *lqu,int x)
{
    QNode *p;
    p = (QNode*)malloc(sizeof(QNode));
    p->data = x;
    p->next = NULL;
    if (lqu->next == NULL)
        lqu->front = lqu->rear = p;
    else
    {
        lque=rear->next = p;
        lqu->rear=p;
    }
}

// 出队
int deQueue(QNode *lqu,int &x)
{
    QNode *p;
    if(lqu->rear=NULL)
        return 0;
    else
        p = lqu->front;
    if(lqu->front==lqu->rear)
        lqu->front = lqu->rear = NULL;
    else
        lqu->front =q->next;
    x = p->data;
    free(p);
    return 1;
}

/* 常用的定义
int  front,rear;
front = rear = 0;
BTNode *que[maxSize]

BTNode *Stack[maxSize];
int top= -1;
/*