Cracking the Coding Interview - 3장: 스택과 큐 - 제목 5
9767 단어 interview
제목: 두 개의 창고로 하나의 대열을 실현한다.
해법: 창고는 반대이고, 대열은 옳고, 반대면 반대다.그러니까 코드를 보세요.조작 중 시간의 복잡도는 O(1)의, O(n)의, 그러나 모두 분담하는 시간은 O(1)에 부합된다.
코드:
1 // 3.5 Implement a queue MyQueue using two stacks.
2 #include <climits>
3 #include <cstdio>
4 #include <cstring>
5 #include <stack>
6 using namespace std;
7
8 template<class T>
9 class MyQueue {
10 public:
11 bool empty() {
12 return s1.empty() && s2.empty();
13 }
14
15 void push(const T &val) {
16 s1.push(val);
17 }
18
19 void pop() {
20 if (s2.empty()) {
21 while (!s1.empty()) {
22 s2.push(s1.top());
23 s1.pop();
24 }
25 }
26 s2.pop();
27 }
28
29 T front() {
30 if (s2.empty()) {
31 while (!s1.empty()) {
32 s2.push(s1.top());
33 s1.pop();
34 }
35 }
36
37 return s2.top();
38 }
39
40 T back() {
41 if (s1.empty()) {
42 while (!s2.empty()) {
43 s1.push(s2.top());
44 s2.pop();
45 }
46 }
47
48 return s1.top();
49 }
50 private:
51 stack<T> s1, s2;
52 };
53
54 int main()
55 {
56 MyQueue<int> qq;
57 char s[100];
58 int op;
59
60 while (scanf("%s", s) == 1) {
61 if (strcmp(s, "end") == 0) {
62 break;
63 } else if (strcmp(s, "push") == 0) {
64 scanf("%d", &op);
65 qq.push(op);
66 } else if (strcmp(s, "pop") == 0) {
67 qq.pop();
68 } else if (strcmp(s, "front") == 0) {
69 printf("%d
", qq.front());
70 } else if (strcmp(s, "back") == 0) {
71 printf("%d
", qq.back());
72 }
73 }
74
75 return 0;
76 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
알고리즘 1000 개 노크 #2. Longest common substringsProblem Solution DP (다이나믹 프로그래밍) 중에서 고전적인 문제입니다. 두 문자열을 S1과 S2, 각각의 길이를 M, N으로 설정합니다. 총당으로 S1에서 모든 부분 문자열을 추출하고, 그것들이 S2...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
