[ 자료구조 ] 스택 복습 ( Stack )

스택

스택의 정의 : 후입선출 ( Last In First Out : LIFO ) 의 자료구조.

기능 :  삽입( 입력 ) PUSH  / 출력( 삭제 )  POP / 참조 TOP

※ POP 에서 마지막 자료를 삭제만 하거나, 참조하면서 삭제하는 두 가지 종류가 있다.

    구현하는 사람 맘대로 ! 

키워드 : 탑 ( TOP ), 푸쉬 ( PUSH ), 팝 ( POP )

TOP : 가장 최근에 들어간 자료를 참조

PUSH : 어떤 자료를 스택에 넣는 것, = 삽입

POP : TOP 에 해당하는 자료를 참조하며 삭제 ( 혹은 삭제만 시킴 )

구현 : 배열 / 링크드 리스트

스택은 이 사진이라고 생각하면 된다. 

접시를 추가하고 싶으면 맨 위에 추가해야지 중간에 끼워넣을 수 없다.
접시를 빼고 싶어도 맨 위에서부터 빼야지 중간부터 뺄수는 없는 노릇

배열 : 간단하게 생각해서 인덱스만 조절하면, 구현하기 쉽다. 

이렇게 배열이 있을때 INDEX 가 0 에서 시작해서 PUSH가 일어날 때 마다 INDEX가 

증가하는 식으로 하면 되기 때문

반대로 POP 하면 INDEX 가 줄어들면 된다. 

10000

-

-

-

-

-

-

-

-

-

          INDEX

10000

20000

-

-

-

-

-

-

-

-

 INDEX

이런 식

링크드 리스트같은 경우엔

이런 식으로 싱글 링크드 리스트로 구현이 가능하다. 

여기서 삽입하면 탑이 가리키는 위치만 이동하고 추가된 노드가 기존 TOP 을 가리키면 되기때문에 매우 단순하다.

삭제는 TOP이 현재 TOP의 NEXT 를 가리키게 바꿔주면 끝이다.

구현 코드 - 배열 -

#include <iostream>
#include <string>
using namespace std;
int push(int p);
int pop();
int stack[1000];
int index = 0; 
int main() {
	int end = 1;
	int select;
	int p;
	string choice;
	while (end) {
		cout << "push n\npop n \nend" << endl;
		cin >> choice ;
		if (choice == "push" || choice == "PUSH") {
			cin >> p;
			if (push(p))
				cout << p << " push 성공 " << endl;
			else
				cout << " push 실패 " << endl;
		}
		else if (choice == "pop" || choice == "POP") {
			if (index > 0)
				cout << "pop 결과 : " << pop() << endl;
			else
				cout << "불가능하다 이 짜식아" << endl;
		}
		else
			end = 0;
		choice.clear();
	}
}
int push(int p) {
	stack[index++] = p;
	return 1;
}
int pop() {
	index--;
	if (index < 0)
		return 0;
	return stack[index];
}

구현 코드 - 링크드리스트 -

#include <iostream>
#include <string>
using namespace std;
int push(int p);
int pop();
struct Node {
	int n;
	Node* next;
};
Node* top = NULL;
Node* temp; 
int main() {
	int end = 1;
	int select;
	int p;
	string choice;
	while (end) {
		cout << "push n\npop n \nend" << endl;
		cin >> choice;
		if (choice == "push" || choice == "PUSH") {
			cin >> p;
			if (push(p))
				cout << p << " push 성공 " << endl;
			else
				cout << " push 실패 " << endl;
		}
		else if (choice == "pop" || choice == "POP") {
			if ( top != NULL )
				cout << "pop 결과 : " << pop() << endl;
			else
				cout << "불가능하다 이 짜식아" << endl;
		}
		else
			end = 0;
		choice.clear();
	}
}
int push(int p) {
	Node *newnode = new Node;
	newnode->n = p;
	newnode->next = top;
	top = newnode;
	return 1;
}
int pop() {
	int ret = top->n;
	top = top->next;
	return ret;
}