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

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

栈(Stack)

1
typedef struct{
2
3
  int data[MAXSIZE];
4
  int top;
5
}Stack;
6
7
stack->data[stack->top--]; /* 弹出元素后，top-- */
8
stack->data[++stack->top]; /* top++后，增加一个元素 */

链式实现

1
typedef struct Node{
2
  int data;
3
  struct Node* next;
4
}Node;
5
6
typedef struct{
7
  Node* top;
8
  int size;
9
}Stack;
10
11
stack->top = node;
12
stack->size++;
13
14
15
stack->top = stack->top->next;
16
stack->size--;

队列(Queue)

1
struct Queue{
2
  int front;
3
  int rear;
4
  int data[MAXSIZE];
5
};
6
7
if(sq->front == sq->rear){
8
  sq->front = sq->rear = 0;
9
  sq->data[sq->rear] = val;
10
  sq->rear++;
11
}else{
12
  sq->data[sq->rear] = val;
13
  sq->rear++;
14
}
15
16
int deldata = sq->data[sq->front];
17
sq->front++;

链式实现

1
typedef struct Node{
2
  int data;
3
  struct Node* next;
4
}Node;
5
6
typedef struct{
7
  Node* front;
8
  Node* rear;
9
  int len;
10
}Queue;
11
12
if(IsEmpty(Queue)){
13
  Queue->front = pNode;
14
  Queue->rear = pNode;
15
}else{
16
  Queue->rear->next = pNode;
17
  Queue->rear = pNode;
18
}
19
Queue->len++;
20
21
22
Node* pNode = Queue->front;
23
Queue->front = Queue->front->next;
24
Queue->len--;

循环队列

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

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

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

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