스택

ppparkta·2022년 3월 29일
1
-22.01.13 스택 정리
스택이란?
스택의 구현
22.01.14 백준 에디터(연결리스트) 문제 풀이

자료구조

목록 보기
4/9
post-thumbnail

*이 글은 2022년 1월~2월 노션으로 진행한 스터디를 옮긴 글입니다.

-22.01.13 스택 정리

스택이란?

스택의 구현

  • 스택 관련 함수 1) is_empty(): 공백 여부 판단
    //배열
**bool is_empty_stack(){**
	/*if (top == -1)return true;
	else return false;*/
	return(top == -1);
}
    //연결리스트
bool is_empty_stack() {
	return(SP == NULL);
}
    2) is_full(): 스택이 꽉 찼는지 판단
    //배열
**bool is_full() {**
	/*if (top == MAX_SIZE - 1)return true;
	else return false;*/
	return(top == MAX_SIZE - 1);
}
    //연결리스트는 자료의 공간이 모자랄 일이 없음. 따라서 full 판단 함수도 존재하지 않음
    3) push(data): 스택에 데이터 삽입
    //배열
**void push(element data) {**
	if (is_full()) { cout << "error:stack full" << endl; }
	else { **Stack[++top] = data;** }
}
    //연결리스트
void push(element data) {
	Node* new_node = new Node;
	new_node->item = data;
	new_node->link = NULL;
	if (SP == NULL) {
		SP = new_node;
	}
	else {
		new_node->link = SP;
		SP = new_node;
	}
}
    4) pop(): 스택의 top 데이터 삭제
    //배열
**element pop() {**
	if (is_empty_stack()) { cout << "error:stack empty" << endl; return -1; }
	else return **Stack[top--]**;
}
    //연결리스트
element pop() {
	if (is_empty_stack()) { return-1; }
	else {
		element item = SP->item;
		SP = SP->link;
		return item;
	}
}
    5) peek(): 스택의 top 데이터 출력
    //배열
**element peek() {**
	if (is_empty_stack()) { cout << "error:stack full" << endl; return -1;}
	else { return Stack[top]; }
}
    //연결리스트
element peek() {
	if (is_empty_stack()) { return -1; }
	else {
		return SP->item;
	}
}
    6) print_stack(): 스택의 전체 데이터 출력
    //배열
**void print_stack() {**
	cout << "[stack status: top: "<<top<<"]" << endl;
	if (is_empty_stack()) { cout << "error:empty stack" << endl; }
	else {
		for (int i = 0; i <= top; i++) {
			cout << Stack[i] << endl;
		}
	}
}
    //연결리스트
void print_stack() {
	cout << "stack status" << endl;
	if (is_empty_stack()) { cout << "error: empty stack" << endl; }
	else {
		for (Node* list = SP; list != NULL; list = list->link) {
			cout << list->item << endl;
		}
	}
}

  • 배열을 이용한 스택 구현

    👉 배열만 사용한 스택 구현

    /*스택의 기본 함수 구현, 몇가지 간이 테스트*/
#include<iostream>
using namespace std;
#define element int//자료type이 중요하지 않다는 뜻
const int MAX_SIZE=1000;
element Stack[MAX_SIZE]; 
int top = -1; //초기화

bool is_empty_stack() {
	/*if (top == -1)return true;
	else return false;*/
	return(top == -1);
}
bool is_full() {
	/*if (top == MAX_SIZE - 1)return true;
	else return false;*/
	return(top == MAX_SIZE - 1);
}
void push(element data) {
	if (is_full()) { cout << "error:stack full" << endl; }
	else { Stack[++top] = data; }
}
element pop() {
	if (is_empty_stack()) { cout << "error:stack empty" << endl; return -1; }
	else return Stack[top--];
}
element peek() {
	if (is_empty_stack()) { cout << "error:stack full" << endl; return -1;}
	else { return Stack[top]; }
}
void print_stack() {
	cout << "[stack status: top: "<<top<<"]" << endl;
	if (is_empty_stack()) { cout << "error:empty stack" << endl; }
	else {
		for (int i = 0; i <= top; i++) {
			cout << Stack[i] << endl;
		}
	}
}
**//main함수 구성**
void main() {
	push(20);
	push(30);
	push(40);
	print_stack();
	pop();
	pop();
	print_stack();
	pop();
	print_stack();
}

    👉 배열과 객체를 사용한 스택 구현

    /*객체와 배열을 사용한 스택 구현. 여러개의 스택을 구현할수 있음*/
#include<iostream>
using namespace std;
#define element int
const int MAX_SIZE = 1000;

**//Stack class 생성**
class Stack {
public:
	element MyStack[MAX_SIZE];
	int top;
	//생성자
	Stack() { top = -1; }
	//공백스택 판단
	bool is_empty_stack() { return (top == -1); }
	//꽉찬스택 판단
	bool is_full() { return(top == MAX_SIZE - 1); }
	//삽입
	void push(element data) {
		if (is_full())cout << "error:full stack" << endl;
		else { MyStack[++top] = data; }
	} 
	//삭제
	element pop() {
		if (is_empty_stack()) { cout << "error:empty stack" << endl; return-1; }
		else { return MyStack[top--]; }
	}
	//top출력
	element peek() {
		if (is_empty_stack()) { cout << "error:empty stack" << endl; return-1; }
		else { return MyStack[top]; }
	}
	//스택출력
	void print_stack() {
		if (is_empty_stack()) { cout << "error:empty stack" << endl; }
		else {
			for (int i = 0; i <= top; i++) {
				cout << MyStack[i] << endl;
			}
		}
	}
};
**//main함수 구성**
void main() {
	Stack MS;
	Stack MP;
	MS.push(20);
	MS.push(30);
	MS.push(40);
	MP.push(105);
	MP.push(200);
	MP.push(320);
	MS.print_stack();
	cout << "---" << endl;
	MP.print_stack();
}
  • 연결리스트를 이용한 스택 구현
    /*연결리스트로 스택 구현*/
#include<iostream>
using namespace std;
#define element int

class Node {
public:
	element item;
	Node* link;
};

Node* SP = NULL;//stack pointer

bool is_empty_stack() {
	return(SP == NULL);
}

//연결리스트는 자료의 공간이 모자랄 일이 없음. 따라서 full 판단 함수도 존재하지 않음
//bool is_full() {} 

void push(element data) {
	Node* new_node = new Node;
	new_node->item = data;
	new_node->link = NULL;
	if (SP == NULL) {
		SP = new_node;
	}
	else {
		new_node->link = SP;
		SP = new_node;
	}
}

element pop() {
	if (is_empty_stack()) { return-1; }
	else {
		element item = SP->item;
		SP = SP->link;
		return item;
	}
}

element peek() {
	if (is_empty_stack()) { return -1; }
	else {
		return SP->item;
	}
}

void print_stack() {
	cout << "stack status" << endl;
	if (is_empty_stack()) { cout << "error: empty stack" << endl; }
	else {
		for (Node* list = SP; list != NULL; list = list->link) {
			cout << list->item << endl;
		}
	}
}

void main() {
	push(10);
	push(20);
	push(30);
	print_stack();
	pop();
	pop();
	push(40);
	print_stack();
}

22.01.14 백준 에디터(연결리스트) 문제 풀이

  • 수정전
    /*
2.01.14
에디터 구현(백준1406)
초기 연결리스트는
[공백리스트-문자열리스트-공백리스트] 형식으로 구현함
a-b-c형식의 문자열리스트가 있을 때 커서가 a를 가리키고 있으면 a와 b사이를 의미함.

22.01.14 P,L,D는 구현 완료-B가 iterator범위 벗어나는 오류 발생
detail: 커서가 begin가리킬 때 B 수행시 무시(정상), 그 외 문제발생
*/
#include<iostream>
#include<list>
using namespace std;

int main() {
	list<char>alpha;
	string a;
	int b;
	char input;
	cin >> a;
	cin >> b;
	**//초기 문자열 연결리스트**
	alpha.push_back(NULL);
	for (int i = 0; i < a.size(); i++) {
		alpha.push_back(a[i]);
	}
	alpha.push_back(NULL);
	**//커서 생성**
	list<char>::iterator iter = alpha.end();
	**//명령어 수행구문**
	for (int i = 0; i < b; i++) {
		cin >> input;
		**//L명령어:** 커서를 왼쪽으로 한 칸 옮김(맨 앞이면 무시)
		if (input == 'L') {
			if (iter == alpha.begin()) { continue; }
			else{
				--iter;
			}
		}
		**//D명령어:** 커서를 오른쪽으로 한 칸 옮김(맨 뒤면 무시)
		if (input == 'D') {
			if (iter == alpha.end()) { continue; }
			else {
				++iter;
			}
			continue;
		}
		**//B명령어**: 커서 왼쪽에 있는 문자를 삭제함. (맨 앞이면 무시)
		if (input == 'B') {
			if (iter != alpha.begin()) {
				//(+1)이게 작동 안되던 이유. 
				//erase가 return하는 값은 삭제한 노드의 오른쪽 노드임. 즉 노드를 반환함.
				//근데 반환을 받아주는 곳 없이 덜렁 코드만 있으니까 오류난듯?
				iter = alpha.erase(--iter);
			}
			else { continue; }
		}
		**//P명령어**: 커서 왼쪽에 in을 추가함
		//근데 insert함수는 커서의 왼쪽에 원소 삽입함.
		//(+2)여기에도 오류 있었음
		//insert가 반복자의 오른쪽에 노드 추가한다고 생각하고 짠 코드인데 왼쪽에 추가하는거였음.
		//논리적 오류가 생겨서 올바르게 수정함.
		if (input == 'P') {
			char in;
			cin >> in;
			if (iter == alpha.begin()) {
				alpha.insert(++iter, in);
			}
			else {
				alpha.insert(iter, in);
			}
		}
	}
	list<char>::iterator iter2 = alpha.begin();
	for (iter2 = ++alpha.begin(); iter2 != alpha.end(); iter2++) {
		cout << *iter2;
	}
	return 0;
}
  • 수정후(오류 검토 후 정답확인받음)
    /*
2022.01.14
에디터 구현(백준1406)
a-b-c형식의 문자열리스트가 있을 때 커서가 c를 가리키고 있으면 b와 c사이를 의미함.
22.01.14 P,L,D는 구현 완료-B가 iterator범위 벗어나는 오류 발생
detail: 커서가 begin가리킬 때 B 수행시 무시(정상), 그 외 문제발생
*/
#include<iostream>
#include<list>
using namespace std;

int main() {
	list<char>alpha;
	string a;
	int b;
	char input;
	cin >> a;
	cin >> b;
	//초기 문자열 연결리스트
	for (int i = 0; i < a.size(); i++) {
		alpha.push_back(a[i]);
	}
	//커서 생성
	list<char>::iterator iter = alpha.end();
	//명령어 수행구문
	for (int i = 0; i < b; i++) {
		cin >> input;
		//L명령어: 커서를 왼쪽으로 한 칸 옮김(맨 앞이면 무시)
		if (input == 'L') {
			if (iter == alpha.begin()) { continue; }
			else {
				--iter;
			}
		}
		//D명령어: 커서를 오른쪽으로 한 칸 옮김(맨 뒤면 무시)
		if (input == 'D') {
			if (iter == alpha.end()) { continue; }
			else {
				++iter;
			}
			continue;
		}
		//B명령어: 커서 왼쪽에 있는 문자를 삭제함. (맨 앞이면 무시)
		if (input == 'B') {
			if (iter != alpha.begin()) {
				//(+1)이게 작동 안되던 이유. 
				//erase가 return하는 값은 삭제한 노드의 오른쪽 노드임. 즉 노드를 반환함.
				//근데 반환을 받아주는 곳 없이 덜렁 코드만 있으니까 오류난듯?
				iter = alpha.erase(--iter);
			}
			else { continue; }
		}
		//P명령어: 커서 왼쪽에 in을 추가함
		//insert함수는 커서의 왼쪽에 원소 삽입함.
		//(+2)여기에도 오류 있었음
		//insert가 반복자의 오른쪽에 노드 추가한다고 생각하고 짠 코드인데 왼쪽에 추가하는거였음.
		//논리적 오류가 생겨서 올바르게 수정함.
		if (input == 'P') {
			char in;
			cin >> in;
			alpha.insert(iter, in);
		}
	}
	list<char>::iterator iter2 = alpha.begin();
	for (iter2 = alpha.begin(); iter2 != alpha.end(); iter2++) {
		cout << *iter2;
	}
	return 0;
}
  • 관련 STL 정리
      ---
  
  ### list 적용 예시
  
  ```cpp
  #include <iostream> 
  #include <list> 
  
  using namespace std; 
    
  int main() 
  { 
      // 리스트 생성 
      list<int> a;  
   
      // 원소 추가 
      a.push_back(22); 
      a.push_back(33); 
      a.push_front(11); 
      a.push_back(44); 
      a.push_back(55); 
    
      // 반복자 생성 
      list<int>::iterator iter = a.begin(); 
   
      // 리스트 출력 
      for(iter=a.begin(); iter!=a.end(); iter++) 
      { 
          cout << *iter << endl; // 원본 리스트: 11 22 33 44 55 
      } 
   
      cout << "" << endl; 
      cout << "" << endl; 
    
      // 원소 삭제 
      a.pop_front(); 
      a.pop_back(); 
       
      for(iter=a.begin(); iter!=a.end(); iter++) 
      { 
          cout << *iter << endl; // 원소 삭제후 리스트: 22 33 44 
      } 
    
      cout << "" << endl; 
      
      // 리스트 사이즈 출력 
      cout << a.size() << endl; // 3 출력( 22, 33, 44 이므로) 
    
      // 리스트가 비어있는가 
      cout << a.empty() << endl; // 비어있지 않으므로 0 반환 
        
      // 리스트 첫번째 원소 출력 
      cout << a.front() << endl; // 22 
    
      // 리스트 마지막 원소 출력 
      cout << a.back() << endl; // 44 
    
      cout << "" << endl; 
   
      // 반복자 2번째 위치로 이동 
      iter++; // 반복자가 두번째 원소(33)를 가리킴 
      iter++; // 반복자가 세번째 원소(44)를 가리킴 
      a.insert(iter, 55555); 
      for(iter=a.begin(); iter!=a.end(); iter++) 
      { 
          cout << *iter << endl; //세번째 원소(44) 전에 추가하는 것(22,55555,33,44) 
      }  
  }
  ```
  • 후기
    • list STL을 알게 됨. 처음 써보는데 STL정리할수 있는 좋은 기회였음.
    • 오류가 너무너무너무 많이 발생함. 멤버함수의 기능을 제대로 모르고 써서 발생한 오류가 대부분이었음. 기억나는 오류 몇가지 정리함
    1. erase(반복자)의 반환값이 반복자임!!!! 함수 내부에서 삭제연산 수행 후 삭제한 노드의 오른쪽에 있었던 노드를 반환함. 즉 이 함수만 덜렁 쓰면 오류남. 이 반복자를 받아줄 반복자가 또 필요함. (근데 반복자 생성이 이해가 잘 안되니까 그것도 다시 보기)
    2. insert(반복자, 삽입하려는 데이터)는 현재 반복자가 가리키고 있는 노드의 왼쪽에 생성됨. 왼쪽임. 오른쪽 아님.
    • 기억나는건 이정도고 사실 STL없이 직접 연결리스트를 짜서 구현하려고 했는데 그 방식으로 하니까 초기값 생성부터 막힘. 그래서 어쩔수없이 STL 썼는데 이번 스터디 끝나면 STL없이 다 하나씩 구현해보고 싶어서 킵함.
profile
ppparkta
겉촉속촉
이전 포스트

이중연결리스트

다음 포스트

스택으로 응용문제 풀기

0개의 댓글

관련 채용 정보

Powered by GraphCDN, the GraphQL CDN