stack (6) 썸네일형 리스트형 [코딩인터뷰 완전정복] 3.5 스택 정렬 Q : 가장 작은 값이 위로 오도록 스택을 정렬하는 프로그램을 작성하라. 추가적으로 하나 정도의 스택은 사용해도 괜찮지만, 스택에 보관된 요소를 배열 등의 다른 자료구조로 복사할 수는 없다. 스택은 push, pop, peek, isEmpty의 네가지 연산을 제공해야 한다. ...더보기 #include template class Stack { private: T *start; int nOfE; int size; public: Stack() { start = new T[10]; nOfE = 0; size = 10; } Stack(int N) { start = new T[N]; nOfE = 0; size = N; } void push(T n) { if (nOfE == size) { T *sizeIncreas.. [코딩인터뷰 완전정복] 3.4 스택으로 큐 Q : 스택 두 개로 큐 하나를 구현한 MyQueue 클래스를 구현하라. #include #include "Stack.h" class MyQueue {private: Stack in; Stack out; bool inputFlag;public: MyQueue() { inputFlag = true; } void push(int n) { if (!inputFlag) { while (out.Size > 0) { in.push(out.pop); } } inputFlag = true; in.push(n); } int pop() { if (inputFlag) { while (in.Size > 0) { out.push(in.pop); } } inputFlag = false; return out.pop(); }};pu.. [코딩인터뷰 완전정복] 3.3 접시 무더기 Q : 자료구조 SetOfStacks를 구현해 보라. SetOfStacks는 여러 개의 스택으로 구성되어 있으며, 이전 스택이 지정된 용량을 초과하는 경우 새로운 스택을 생성해야 한다. SetOfStacks.push()와 SetOfStacks.pop()은 스택이 하나인 경우와 동일하게 동작해야 한다. ...더보기 #include template class Stack { private: T *start; int nOfE; int size; public: Stack() { start = new T[10]; nOfE = 0; size = 10; } Stack(int N) { start = new T[N]; nOfE = 0; size = N; } void push(T n) { if (nOfE == size) {.. [코딩인터뷰 완전정복] 3.2 스택 Min Q : 기본적인 push와 pop 기능이 구현된 스택에서 최솟값을 반환하는 min함수를 추가하려고 한다. 어떻게 설계할 수 있겠는가? push, pop, min 연산은 모두 O(1) 시간에 동작해야 한다. #include class stack { private: int *start; int nOfE; int size; int *minStack; int minNofE; int minStackSize; public: stack() { start = new int[10]; nOfE = 0; size = 10; minStack = new int[10]; minNofE = 0; minStackSize = 10; } stack(int N) { start = new int[N]; nOfE = 0; size = N; .. [코딩인터뷰 완전정복] 3.1 한 개로 세 개 Q : 배열 한 개로 스택 3개를 어떻게 구현할지 설명하라. A : 임의접근이 가능하도록 스택을 구현 할 경우 시작 노드가 변하지 않는다. 배열을 3등분해서 각 스택의 공간을 정적으로 할당한다. 공간을 동적으로 사용하려면 스택에 넣을 공간이 부족할 때 스택의 공간을 늘려주고 그자리에 있던 원소들은 밀어준다. 스택을 노드로 구현한다면 공간을 정적으로 지정해 줄 필요없이 세 스택의 총 길이가 배열의 길이를 넘지 않도록만 해준다. [C++ STL] Stack 1. Stack - LIFO 자료형이다. - 가장 나중에 들어간 자료가 가장 먼저 나온다. - 임의 접근이 불가능하다. - 내부는 deque로 구성되어 있다. 2. Include #include 3. 선언 std::stack name; std::stack name(otherStack); std::stack name(otherDeque); namespace std를 사용함. 이미 만들어져있는 stack이나 deque를 사용하여 생성 가능. 4. function // stack의 제일 위에 새로운 data 삽입 void push(T) // stack의 제일 위에 있는 data를 제거(반환값 없음) void pop() // stack의 제일 위에 있는 원소의 값을 반환한다. reference top() // .. 이전 1 다음
