Data Structure — Stack

BOJ #10828 stack problem: https://www.acmicpc.net/problem/10828

---

What is a stack?

A stack is a list structure with restricted access. It's a LIFO (Last In First Out) data structure where data can be inserted and removed only from one end.

Stack operations

There are several, but these are the most commonly used.

• pop(): removes the topmost item from the stack.
• push(input): adds a variable called input to the very top of the stack.
• size(): tells you the size held in the stack.
• top(): returns the topmost part of the stack (does not delete it).
• empty(): returns true when the stack is empty.

Why use a stack?

Depending on the type of problem, storing data in a stack rather than an array may be a more suitable method.

• Unlike an array, you can't access an arbitrary position.
• Adding or deleting data in a stack can be done in constant time.
• To use an array like a stack, you'd have to shift elements over every time you remove one — with a stack there's no need.

Implementing a stack

BOJ #10828 stack problem

#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;    
}

You can make and use it directly like this, but C++ has a header called stack.

This isn't the answer to the problem above; it's just how you can do it when using the stack header.

#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());
        }
    }
    
}

How to use the STL stack

// add the stack header
#include <stack>

// create an empty stack
stack<int> Stack;

// create a stack initialized to {1, 2, 3, 4, 5}
stack<int> Stack({ 1, 2, 3, 4, 5 });

stack's functions

Based on stack<int> Stack

• Stack.push(n): adds n to the top
• Stack.pop(): removes the top element
• Stack.top(): returns the top element
• Stack.size(): returns the size of the stack
• Stack.empty(): checks whether it's empty

Problem solving using a stack:

**[Algorithm] - BOJ #9012 parentheses**](https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html) Reference: 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

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

---

Original (Korean): tistory — published 2021-06-03, migrated to this blog. This translation was generated with the help of AI.