栈和队列

发表于 | 更新于 | 阅读次数：

1. 栈

  • 什么是栈？

栈是限定仅在表头进行插入和删除操作的线性表。栈分为顺序栈和链式栈。

  • 栈的实现
  1. 顺序栈
1
2
3
4
5
6
7
8
9
10
11
12
13
int stack[100], sz = 0;
void push(int x) {//入栈
    stack[++sz] = x;
}
void pop() {//出栈
    sz--;
}
int top() {//返回栈顶元素
    return stack[sz];
}
bool empty() {//判断栈是否为空
    return sz >= 0 ? true : false;
}
  • 链式栈
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
//链式栈只会写一点
class list{
public:
    list *head;
    list *tail;
    list *next;
    int num;
    list(){
        head=tail=next=NULL;
    }
    virtual void push(int x)=0;
    virtual int pop()=0;
};
class stack:public list{
public:
    void push(int x);
    int pop();
};
void stack::push(int x){
    list *noww;
    noww=new stack;
    if(!noww)
        return ;
    noww->num=x;
    if(head)  noww->next=head;
    head=noww;
    if(!tail)  tail=head;
}
int stack::pop(){
    int x;
    list *p;
    if(!head)
        return 0;
    x=head->num;
    p=head;
    head=head->next;
    delete p;
    return x;
}

2. 队列

  • 什么是队列？

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。

  • 队列的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int queue[100], head = 0, tail = 0;
void push(int x) {
    queue[++tail] = x;
}
void pop() {
    head++;
}
int front() {
    return queue[head];
}
int size() {
    return tail - head;
}
bool empty() {
    return head > tail ? true : false;
}

实际上队列也可以用链表实现，这里不再赘述。

3. STL实现栈和队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//栈常用操作
#include <stack>
stack <int> s;
s.push(1);
s.pop();
s.top();
s.empty();
s.size();
//队列常用操作
#include <queue>
queue <int> q;
q.push(1);
q.pop();
q.front();
q.back();
q.empty();
q.size();

$\color{gray}{\mathcal{By}}$ $\color{gray}{\mathfrak{NULL}}$