알고리즘

2 min readDec 21, 2023

Stack

LIFO (last in first out)

use case: string reverse O(N)

#include <iostream>
#include <stack>
#include <string>

using namespace std;

struct Stack {
 int data[10000];
 int size;
 Stack() {
    size = 0;
 }

 void push(int num) {
    data[size] = num;
    size += 1;
 }

 bool empty() {
 if (size == 0) {
     return true;
 } else {
     return false;
   }
 }

 int pop() {
   if (empty()) {
     return -1;
 } else {
     size -= 1;
     return data[size];
   }
 }

 int top() {
 if (empty()) {
 return -1;
 } else {
 return data[size-1];
 }
 }
};

int main() {
   int n;
   cin >> n;

   Stack s;

 while (n--) {
   string cmd;
   cin >> cmd;
 if (cmd == "push") {
   int num;
   cin >> num;
   s.push(num);
 } else if (cmd == "top") {
   cout << (s.empty() ? -1 : s.top()) << '\n';
 } else if (cmd == "size") {
   cout << s.size << '\n';
 } else if (cmd == "empty") {
   cout << s.empty() << '\n';
 } else if (cmd == "pop") {
   cout << (s.empty() ? -1 : s.top()) << '\n';
   if (!s.empty()) {
   s.pop();
   }
  }
 }
 return 0;
}

Queue

#include <iostream>
#include <string>

using namespace std;
struct Queue {
 int data[10000];
 int begin, end;
 Queue() {
 begin = 0;
 end = 0;
 }
 void push(int num){
 data[end] = num;
 end += 1;
 }
 bool empty() {
 if (begin ==end ){
 return true;
 }else {
 return false;
 }
 }
 int size(){
 return end - begin;
 }
 int front(){
 return data[begin];
 }
 int back(){
 return data[end-1];
 }
 int pop(){
 if(empty()){
 return -1;
 }
 begin += 1;
 return data[begin-1];
 }
};
int main(){
 int n;
 cin >> n;
 
 Queue q;
 
 while (n - ){
 string cmd;
 cin >> cmd;
 if(cmd == "push"){
 int num;
 cin >> num;
 q.push(num);
 } else if (cmd == "pop"){
 if (q.empty()){
 cout << -1 << '\n';
 } else {
 cout << q.front() << '\n';
 q.pop();
 }
 } else if (cmd == "size"){
 cout << q.size() << '\n';
 } else if (cmd == "empty") {
 cout << q.empty() << '\n';
 } else if (cmd == "front") {
 if (q.empty()) {
 cout << -1 << '\n';
 } else {
 cout << q.front() << '\n';
 }
 } else if (cmd == "back") {
 if (q.empty()) {
 cout << -1 << '\n';
 } else {
 cout << q.back() << '\n';
 }
 }
 }
 return 0;
}