栈(Stack)：后进先出(LIFO last in first out)。

队列(Queue)：先进先出(FIFO first in first out)。

栈(Stack)

1
2
3
4
5
6
7
8
typedef struct{

  int data[MAXSIZE];
  int top;
}Stack;

stack->data[stack->top--]; /* 弹出元素后，top-- */
stack->data[++stack->top]; /* top++后，增加一个元素 */

链式实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct Node{
  int data;
  struct Node* next;
}Node;

typedef struct{
  Node* top;
  int size;
}Stack;

stack->top = node;
stack->size++;


stack->top = stack->top->next;
stack->size--;

队列(Queue)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Queue{
  int front;
  int rear;
  int data[MAXSIZE];
};

if(sq->front == sq->rear){
  sq->front = sq->rear = 0;
  sq->data[sq->rear] = val;
  sq->rear++;
}else{
  sq->data[sq->rear] = val;
  sq->rear++;
}

int deldata = sq->data[sq->front];
sq->front++;

链式实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef struct Node{
  int data;
  struct Node* next;
}Node;

typedef struct{
  Node* front;
  Node* rear;
  int len;
}Queue;

if(IsEmpty(Queue)){
  Queue->front = pNode;
  Queue->rear = pNode;
}else{
  Queue->rear->next = pNode;
  Queue->rear = pNode;
}
Queue->len++;


Node* pNode = Queue->front;
Queue->front = Queue->front->next;
Queue->len--;

循环队列

在循环队列中约定：在循环队列中少用一个元素空间，当队尾标识rear在队头标示front的上一个位置时，队列为满。

  1. front == rear 队列空。
  2. (rear+1)%MAXSIZE == front 队列满。

循环队列中移动要对队列容量取模：front = (front+1) % MAXSIZE，rear = (rear+1) % MAXSIZE。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Insert(Queue q, int val){

  if((q->rear+1)%MAXSIZE == q->front){
    return;
  }

  if(IsEmpty(q)){
    q->front = q->rear = 0;
    q->data[q->rear] = val;
    q->rear++
  }else{
    q->data[q->rear]=val;
    q->rear = (q->rear+1) % MAXSIZE;
  }
}
1
2
3
4
5
6
7
8
9
10
int Delete(Queue q){
  
  if(IsEmpty(q)){
    return 0;
  }

  int val = q->data[q->front];
  q->front = (q->front+1) % MAXSIZE;
  return val;
}