2021-06-03 · 3분

数据结构 — 栈

algorithm

这篇文章发布已超过两年，内容可能已过时。

BOJ #10828 栈问题：https://www.acmicpc.net/problem/10828

什么是栈？

栈（Stack）是一种可受限访问的排列结构。它是只能在一端存取数据的 LIFO（Last In First Out）形式的数据结构。

栈的功能

有很多，但这些是最常用的。

pop()：删除栈最上面的项。
push(input)：把名为 input 的变量添加到栈的最上面。
size()：告知栈中所存的大小。
top()：返回栈最上面的部分（不删除）。
empty()：栈为空时返回 true。

为什么用栈？

根据问题的种类，把数据存进栈而非数组可能是更合适的方法。

与数组不同，无法访问某个位置。
在栈中添加或删除数据的运算可在常数时间内完成。
要把数组当栈用，每次从数组取出元素时都得往旁边挪，而栈不需要。

栈的实现

BOJ #10828 栈问题

#include<stdio.h>
#include<string.h>
 
#define TRUE 1            
#define FALSE 0           
#define MINUS -1          
#define MAX_SIZE 10000    
 
typedef struct _stack{    
    int arr[MAX_SIZE];
    int top;
} Stack;
 
void StackInit(Stack * sp){    
    sp->top = -1;
}
 
int IsEmpty(Stack * sp){    
    if(sp->top == -1) return TRUE;
        
    return FALSE;
}
 
int Size(Stack *sp){    
    return sp->top + 1;
}
 
 
int IsFull(Stack * sp){        
    if(sp->top + 1 >= MAX_SIZE) return TRUE;
    
    return FALSE;
}
 
void Push(Stack * sp, int data){    
    if(IsFull(sp)==TRUE) return;
    
    sp->arr[++(sp->top)] = data;    
}
 
int Pop(Stack * sp){    
    if(IsEmpty(sp) == TRUE) return MINUS;
 
    return sp->arr[(sp->top)--];
}
 
int Peek(Stack *sp){    
    if(IsEmpty(sp) == TRUE) return MINUS;
    
    return sp->arr[sp->top];
}
 
 
int main(void){
    int i;
    char str[6];
    Stack stack;
    int n, num;
    
    scanf("%d", &n);
    fgetc(stdin);    
    StackInit(&stack);    
    
    
    for(i=0; i<n; i++){
    
        scanf("%s", str);
        fgetc(stdin);    
 
        if(!strcmp(str, "push")){    
            
            scanf("%d", &num);
            fgetc(stdin);    
            Push(&stack, num);    
            
        }else if(!strcmp(str, "pop")){    
        
            printf("%d\n", Pop(&stack));
        
        }else if(!strcmp(str, "empty")){    
            
            printf("%d\n", IsEmpty(&stack));
            
        }else if(!strcmp(str, "size")){        
        
            printf("%d\n", Size(&stack));
        
        }else if(!strcmp(str, "top")){        
        
            printf("%d\n", Peek(&stack));
        
        }
    }
    
    
    return 0;    
}

也可以像这样直接自己写来用，但 c++ 里存在名为 stack 的头文件。

这不是上面问题的答案，只是使用 stack 头文件时可以这样做。

#include <stdio.h>
#include <string.h>
#include <stack>

using namespace std;

stack<int> Stack;

int main()
{
    int i;
    char str[7];
    int n, num;

    scanf("%d", &n);
    fgetc(stdin);

    for (int i = 0; i < n; i++)
    {
        scanf("%s", str);
        fgetc(stdin);

        if(!strcmp(str, "push")) {
            scanf("%d", &num);
            fgetc(stdin);
            Stack.push(num);
        }else if(!strcmp(str, "pop")) {
            if(Stack.empty()) printf("-1\n");
            else {
                printf("%d\n", Stack.top());
                Stack.pop();
            }
        }else if(!strcmp(str, "empty")) {
            if(Stack.empty()) printf("1\n");
            else printf("0\n");
        }else if(!strcmp(str, "size")) {
            printf("%ld\n", Stack.size());
        }else if(!strcmp(str, "top")) {
            printf("%d\n", Stack.top());
        }
    }
    
}

STL stack 的用法

// 添加 stack 头文件
#include <stack>

// 创建空的 stack
stack<int> Stack;

// 创建初始化为 {1, 2, 3, 4, 5} 的 stack
stack<int> Stack({ 1, 2, 3, 4, 5 });

stack 的函数们

以 stack<int> Stack 为准

Stack.push(n)：在最上面添加 n
Stack.pop()：删除最上面的元素
Stack.top()：返回最上面的元素
Stack.size()：返回栈的大小
Stack.empty()：确认是否为空

利用栈的解题：

**[算法] - BOJ #9012 括号**](https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html) 参考：https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D https://velog.io/@choiiis/C-STL-stack-%ED%81%B4%EB%9E%98%EC%8A%A4-%EC%A0%95%EB%A6%AC [https://gmlwjd9405.g — data-structure-stack.html

图片：http://www.incodom.kr/%EC%8A%A4%ED%83%9D